2.4. Перестановки и сочетания

    Пусть задано конечное множество элементов. Выясним, сколькими различными способами можно упорядочить элементы этого множества.
    Определение 3. Группы элементов, состоящие из одних и тех же элементов и отличающиеся друг от друга только их порядком, называются перестановками этих элементов.
    Число всевозможных перестановок n элементов обозначается P_n. Как это будет ниже показано, оно равно произведению всех натуральных чисел от 1 до n. Для краткости это произведение обозначают символом n! (читается "эн факториал"), т. е.

n!123...n.

Для удобства полагают

    Пример1. Группы {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}и {3, 2, 1} являются всевозможными перестановками элементов 1, 2 и 3.

    Лемма. Если P_k - число всех перестановок из k элементов и k > 1, то

Множество всех перестановок из заданных k элементов разбивается на группы, в каждой из которых на первом месте стоит один и тот же элемент. Число таких групп равно k - числу всех элементов.
    В перестановках, входящих в одну и ту же группу, на последующих k - 1 местах могут располагаться оставшиеся k - 1 элементов в любом порядке. Поэтому число перестановок в каждой группе равно P_k-1.
    Каждая перестановка из k элементов попадает в одну из описанных групп и в точности один раз. Поэтому для числа P_k всех перестановок из k элементов имеет место соотношение (2.20). 

    Теорема 1. Число всевозможных перестановок из n элементов равно n!:

Докажем теорему методом математической индукции. Если n = 1, то, очевидно, P_n = 1 = 1!. Если для некоторого k  N имеет место формула P_k = k!, то согласно лемме

Pk	=	(k + 1)k! = (k + 1)!.
	(2.20)

    Выясним теперь, сколько подмножеств, содержащих m элементов, имеет множество, состоящее из n элементов, 1 < m < n.

    Определение 4. Каждое множество, содержащее m элементов из числа n заданных, называется сочетанием из n элементов по m.
    Подчеркнем, что сочетание определено как множество некоторых элементов без рассмотрения порядка, в котором они расположены.
    Число всех сочетаний из n элементов по m обозначается .
    Пример 2. Множества {1, 2}, {1, 3}и {2, 3} образуют всевозможные сочетания из трех элементов 1, 2, 3 по два.
    Из определения сочетаний вытекают следующие два свойства.
    1^o. Имеет место формула

, k = 0, 1, 2, ..., n,		(2.22)
где	1.	(2.23)

Действительно, если из n элементов выбрать какое-либо сочетание, содержащее k элементов, то элементы, не вошедшие в него, составят сочетание из n - k элементов. Причем, таким путем получатся все сочетания из n элементов по k и каждое по одному разу. Поэтому число сочетаний из n элементов по k, т. е. , равняется числу сочетаний из n элементов по n - k, т. е. числу . 
2^o.  Имеет место формула

    Пусть дано n + 1 элементов. Зафиксируем один из элементов и разобьем все сочетания по k + 1 элементов на две группы: содержащие этот элемент и не содержащие его. Число первых равно (ибо если удалить фиксированный элемент из каждого содержащего его сочетания по k + 1 элементов, то получатся всевозможные сочетания из n элементов по k и каждое по одному разу), число вторых равно  (ибо они образуют всевозможные сочетания по k + 1 элементов из n элементов, получающихся удалением фиксированного элемента из n + 1 заданных). Это и означает справедливость формулы (2.24). 
    Докажем теперь формулу для числа всевозможных сочетаний из n элементов по m.

    Теорема 2. Для числа сочетаний имеет место формула

  Множество всех перестановок из заданных n элементов разбивается на группы, в каждой из которых на m первых местах стоят одни и те же элементы (в том или ином порядке), а следовательно, и на последних n - m местах также находятся одни и те же элементы. Число таких групп равно числу способов, которыми из данных n элементов можно выбрать m элементов, т. е равно числу .
    В перестановках, входящих в одну и ту же группу, на m первых местах выбранные элементы могут быть расположены любым способом, а число таких способов равно числу P_m всевозможных перестановок из m элементов. Элементы же, стоящие на n - m последних местах, также могут находиться в любом порядке, т. е. из них может быть образована любая перестановка из n - m элементов, а число таких перестановок равно P_n-m.
    Таким образом, число перестановок в каждой группе равно P_mP_n-m, и поскольку число всех групп равно , причем каждая перестановка из n заданных элементов входит только один раз в одну из указанных групп, то для числа всех перестановок P_n получаем формулу

P_n = P_mP_n-m,

из которой и следует формула (2.25). 
    Следствие.

Формула (2.26) вытекает из формулы (2.25) в силу равенства (2.21). 
    Отметим, что формулы (2.22) и (2.24) можно доказать, подставив в них значения сочетаний согласно формуле (2.26) и проведя в случае формулы (2.24) нужные вычисления. Однако приведенные выше доказательства раскрывают смысл формул и дают возможность получить их, не зная заранее, как они выглядят.
    Числа можно последовательно находить с помощью следующей треугольной таблицы, называемой треугольником Паскаля, в которой первые и последние числа во всех строчках равны единице, и, начиная с третьей строчки, каждое число в строчке, отличное от первого и последнего, получается сложением двух ближайших к нему чисел предшествующей строчки:

В силу формулы (2.24) в n-й строчке будут стоять числа

, , ..., , ...,.

  Комплексные числа  Оглавление  Формула бинома Ньютона