Дискретная математика. Азарнова Т.В - 31 стр.

UptoLike

Комбинаторика
31
Его корни 11
=
n
и 20
=
n
. При 20
=
n
и левая, и правая части уравнения
не имеют смысла. При 11
=
n
для любого
k
такого, что ,110
k
справедливо равенство
.240
3
14
11
16
+
=
k
k
A
P
P
Итак, 11
=
n
.
Задача 8.
Сколько различных перестановок можно образовать из букв
словазадача” ?
Решение. Образовать какую-либо перестановку из букв словазадача
это значит на шесть занумерованных мест каким-либо образом поставить
одну буквуз”, одну буквуд”, одну буквучи три буквыа”. Если буквы
з”, “дич как-то поставлены, то остальные места заполняются буквами
а”. Но сколькими способами можно поставить три различные буквы на
шесть мест? Очевидно, что число способов равно числу всех трехэлементных
упорядоченных подмножеств шестиэлементного множества, т.е. равно
120456
3
6
==
A
.
Можно рассуждать и иначе. Если бы все шесть букв слова были
различны, то число перестановок было бы равно 6!. Но букваавстречается
в данном слове 3 раза, и перестановки только этих трех буква не дают
новых способов расположения букв. Поэтому число перестановок букв
словазадачабудет не 6!, а в 3! раза меньше, т.е.
.120456
123
123456
!3
!6
==
=
3.
Сочетания.
Сочетания без повторения
.
Пусть имеется множество, состоящее из
n
элементов. Каждое его подмножество, содержащее
k
элементов,
называется
сочетанием из n элементов по k элементов.
Таким образом, сочетания из
n
элементов по
k
элементов - это все
k
-
элементные подмножества
n
-элементного множества, причем различными
подмножествами считаются только те, которые имеют неодинаковый состав
элементов. Подмножества, отличающиеся друг от друга только порядком
следования элементов, не считаются различными. Например, для
четырехэлементного множества
dcba
,,, сочетаниями по 3 элемента
являются следующие подмножества:
.,,,
bcdacdabdabc
Число всех сочетаний из
n
элементов по
k
элементов обозначается
символом
k
n
C
, где
C
- первая буква французского слова
combinasion
сочетания. Только что было показано, что
.4
3
4
=
C