ВУЗ:
Составители:
Рубрика:
1.2. КОМБИНАТОРНЫЙ АНАЛИЗ
Ос нов ная за да ча ком би на то ри ки — пе ре счет и пе ре чис ле ние эле -
мен тов в ко неч ных мно же ст вах. Ес ли нас ин те ре су ет сколь ко эле мен -
тов, при над ле жа щих за дан но му ко неч но му мно же ст ву, об ла да ет не ко -
то рым свой ст вом или за дан ным на бо ром свойств, то это за да ча пе ре сче -
та. Ес ли для ка ких-ли бо це лей не об хо ди мо вы де лить все эле мен ты
мно же ст ва, удов ле тво ряю щие за дан ным свой ст вам, то это за да ча пе ре -
чис ле ния.
1.2.1 Пра ви ла сум мы и про из ве де ния
1) Пусть Х — ко неч ное мно же ст во, со стоя щее из n эле мен тов.
То гда го во рят, что объ ект x из X мо жет быть вы бран n спо со ба ми, и пи -
шут |x|= n.
Пусть X
1
,...,X
k
— по пар но не пе ре се каю щие ся мно же ст ва, то есть
X
i
Ç X
j
= Æ при i ¹ j. То гда, оче вид но вы пол ня ет ся ра вен ст во:
| |
X X
i
i
k
i
i
k
=
=
=
å
1
1
U
.
В ком би на то ри ке этот факт на зы ва ет ся пра ви лом сум мы. Для
k = 2 оно фор му ли ру ет ся сле дую щим об ра зом: Ес ли объ ект x мо жет
быть вы бран m спо со ба ми, а объ ект y — дру ги ми n спо со ба ми, то вы бор
«ли бо x, ли бо y» мо жет быть осу ще ст в лен (m + n) спо со ба ми.
2) Дру гим час то при ме няе мым в ком би на то ри ке пра ви лом яв ля -
ет ся пра ви ло про из ве де ния. Ес ли объ ект x мо жет быть вы бран m спо со -
ба ми и по сле ка ж до го из та ких вы бо ров объ ект y в свою оче редь мо жет
быть вы бран n спо со ба ми, то вы бор упо ря до чен ной па ры <x, y> мо жет
быть осу ще ст в лен (m + n) спо со ба ми.
В об щем слу чае пра ви ло про из ве де ния фор му ли ру ет ся сле дую -
щем об ра зом. Ес ли объ ект x
1
мо жет быть вы бран n
1
спо со ба ми, по сле
че го объ ект x
2
мо жет быть вы бран n
2
спо со ба ми и для лю бо го i, где
2 1£ £ -i m
, по сле вы бо ра объ ек тов x
1
, ..., x
i
объ ект x
i+1
мо жет быть вы -
бран n
i+1
спо со ба ми, то вы бор упо ря до чен ной по сле до ва тель но сти из
m объ ек тов, <x
1
, x
2
, ..., x
m
> мо жет быть осу ще ст в лен (n
1
n
2
... n
m
) спо со -
ба ми.
42
1.2. КОМБИНАТОРНЫЙ АНАЛИЗ
Основная задача комбинаторики — пересчет и перечисление эле-
ментов в конечных множествах. Если нас интересует сколько элемен-
тов, принадлежащих заданному конечному множеству, обладает неко-
торым свойством или заданным набором свойств, то это задача пересче-
та. Если для каких-либо целей необходимо выделить все элементы
множества, удовлетворяющие заданным свойствам, то это задача пере-
числения.
1.2.1 Правила суммы и произведения
1) Пусть Х — конечное множество, состоящее из n элементов.
Тогда говорят, что объект x из X может быть выбран n способами, и пи-
шут |x|= n.
Пусть X1,...,Xk — попарно непересекающиеся множества, то есть
Xi Ç Xj = Æ при i ¹ j. Тогда, очевидно выполняется равенство:
k k
UX
i =1
i = å| X i |.
i =1
В комбинаторике этот факт называется правилом суммы. Для
k = 2 оно формулируется следующим образом: Если объект x может
быть выбран m способами, а объект y — другими n способами, то выбор
«либо x, либо y» может быть осуществлен (m + n) способами.
2) Другим часто применяемым в комбинаторике правилом явля-
ется правило произведения. Если объект x может быть выбран m спосо-
бами и после каждого из таких выборов объект y в свою очередь может
быть выбран n способами, то выбор упорядоченной пары может
быть осуществлен (m + n) способами.
В общем случае правило произведения формулируется следую-
щем образом. Если объект x1 может быть выбран n1 способами, после
чего объект x2 может быть выбран n2 способами и для любого i, где
2 £ i £ m -1, после выбора объектов x1, ..., xi объект xi+1 может быть вы-
бран ni+1 способами, то выбор упорядоченной последовательности из
m объектов, может быть осуществлен (n1 n2 ... nm) спосо-
бами.
42
Страницы
- « первая
- ‹ предыдущая
- …
- 40
- 41
- 42
- 43
- 44
- …
- следующая ›
- последняя »
