Математика и информатика. Исаченко Н.А. - 11 стр.

     2.1.3. Элементы комбинаторики                                         Умножив и разделив это выражение на                   ( n − k )! ,   получим
     Решение задач по теории вероятностей часто требует уме-                   n!
ния вычислять количества различных комбинаций. В параграфе         Ank =              .
мы познакомимся с некоторыми из таких комбинаций.                          ( n − k )!
     Перестановки. Пусть имеется упорядоченный набор из n                Сочетания. Если порядок выбранных k элементов не ва-
элементов. Изменение порядка в этом наборе называют переста-       жен, то говорят, что осуществлено сочетание (комбинация) из n
новкой. Количество различных перестановок обозначают Pn .          элементов по k . Число сочетаний обозначают Cnk .
     Утверждение. Pn = 1⋅ 2 ⋅ 3 ⋅ K ⋅ n .
                                                                                                           n!
     Доказательство. Если имеется n элементов, то при измене-              Утверждение. Cnk =                        .
нии их порядка есть n возможностей поставить на первое место                                          k !( n − k ) !
элемент. После того как выбран первый элемент, остается ( n − 1)         Доказательство. Размещения отличаются от сочетаний толь-
                                                                   ко наличием порядка выбранных элементов. Таким образом, при
возможностей выбрать второй. Итого: на каждый выбор первого        подсчете количества сочетаний все размещения, отличающиеся
есть ( n − 1) способ выбрать второй. Следовательно, имеем          только порядком, нужно считать как одно. Но, как уже доказано,
n ( n − 1) возможностей выбрать первые два элемента. Аналогич-     Pk = k ! . Следовательно
но: после того, как выбраны первые два, есть (n – 2) способов                                           Ank      n!
                                                                                                Cnk =       =
выбрать третий. Продолжая эти рассуждения до тех пор, пока не                                           k ! k !( n − k ) !
кончатся элементы, получим доказательство утверждения.
      Число, равное произведению первых n натуральных чисел              Пример 9. В отделении 10 солдат. Необходимо составить
называют n -факториал и обозначают n ! . Таким образом,            наряд из 4-х человек. Сколько существует способов составления
                                                                   такого наряда?
Pn = n ! .
                                                                         Р е ш е н и е . Поскольку порядок, в котором мы выбираем
      Размещения. Пусть все также имеется n элементов. Из них      участников наряда, не важен, то мы имеем дело с сочетаниями их
нужно выбрать k элементов, причем расположить их в заданном        10 по 4. Итак,
порядке. В этом случае говорят, что нужно осуществить размеще-                         10!         10! 1⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6 ⋅ 7 ⋅ 8 ⋅ 9 ⋅10
ние из n элементов по k . Число таких различных размещений             C104 =                    =       =                                   = 210
                                                                                 4! ⋅ (10 − 4 ) ! 4! ⋅ 6! 1⋅ 2 ⋅ 3 ⋅ 4 ⋅1⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋅ 6
обозначают Ank .
                                                                         Пример 10. Сколько существует четырехзначных чисел, со-
                             n!                                    стоящих из различных цифр?
      Утверждение. Ank =            .
                         ( n − k )!                                      Р е ш е н и е . Ноль не может быть первой цифрой, следова-
                                                                   тельно, есть 9 возможностей выбрать первую цифру. Далее может
     Доказательство. Повторяя рассуждения из доказательства        следовать любая упорядоченная тройка оставшихся цифр, а для
предыдущего утверждения, видим что
                                                                   этого есть A93 способов. Итого, получаем
            Ank = n ⋅ ( n − 1) ⋅ ( n − 2 ) ⋅ K ⋅ ( n − k + 1) .
                                                                                                      9!
                                                                                         9 ⋅ A93 = 9 ⋅ = 9 ⋅ 7 ⋅ 8 ⋅ 9 = 4536 .
                                                                                                      6!

                                21                                                                           22