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

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

n!определение1dot.gif (51 bytes)2dot.gif (51 bytes)3dot.gif (51 bytes)...dot.gif (51 bytes)n.

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

0! = 1.

(2.19)

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

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

Pk = kPk-1.

(2.20)

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

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

Pn = n!.

(2.21)

начало Докажем теорему методом математической индукции. Если n = 1, то, очевидно, Pn = 1 = 1!. Если для некоторого k принадлежит N имеет место формула Pk = 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 по два.
    Из определения сочетаний вытекают следующие два свойства.
    1o. Имеет место формула

, k = 0, 1, 2, ..., n,

(2.22)
где определение1. (2.23)

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

k = 0, 1, 2, ..., n-1

(2.24)

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

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

(2.25)

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

Pn = PmPn-m,

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

(2.26)

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

1

1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

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

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


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