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

                                    31
Комбинаторика
Его корни n =11 и n =−20 . При n =−20 и левая, и правая части уравнения
не имеют смысла. При n =11 для любого k такого, что 0 ≤k ≤11,
справедливо равенство
                             P16
                                  =240 A14k +3 .
                            P11−k
Итак, n =11.

      Задача 8. Сколько различных перестановок можно образовать из букв
слова “задача” ?
      Решение. Образовать какую-либо перестановку из букв слова “задача”
– это значит на шесть занумерованных мест каким-либо образом поставить
одну букву “з”, одну букву “д”, одну букву “ч” и три буквы “а”. Если буквы
“з”, “д” и “ч” как-то поставлены, то остальные места заполняются буквами
“а”. Но сколькими способами можно поставить три различные буквы на
шесть мест? Очевидно, что число способов равно числу всех трехэлементных
упорядоченных подмножеств шестиэлементного множества, т.е. равно
A63 =6 ⋅ 5 ⋅ 4 =120 .
      Можно рассуждать и иначе. Если бы все шесть букв слова были
различны, то число перестановок было бы равно 6!. Но буква “а” встречается
в данном слове 3 раза, и перестановки только этих трех букв “а” не дают
новых способов расположения букв. Поэтому число перестановок букв
слова “задача” будет не 6!, а в 3! раза меньше, т.е.
6 ! 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅1
   =                     =6 ⋅ 5 ⋅ 4 =120.
3!        3 ⋅ 2 ⋅1


3. Сочетания.
       Сочетания без повторения. Пусть имеется множество, состоящее из
n элементов. Каждое его подмножество, содержащее k элементов,
называется сочетанием из n элементов по k элементов.
       Таким образом, сочетания из n элементов по k элементов - это все k -
элементные подмножества n -элементного множества, причем различными
подмножествами считаются только те, которые имеют неодинаковый состав
элементов. Подмножества, отличающиеся друг от друга только порядком
следования элементов, не считаются различными. Например, для
четырехэлементного множества       a, b, c, d сочетаниями по 3 элемента
являются следующие подмножества:
                             abc, abd , acd , bcd .
       Число всех сочетаний из n элементов по k элементов обозначается
символом C nk , где C - первая буква французского слова combinasion –
сочетания. Только что было показано, что C 43 =4.