Комбинаторика

Рассмотрим n различных предметов. То есть, группу из n предметов. Начнем брать из этой группы по одному предмету и складывать из них новую группу. Группу, из которой берем предметы, назовем старой группой. А группу, которую составляем из выбранных предметов, назовем новой. Предмет, который мы выбираем в первый раз, назовем первым выбранным предметом. Предмет, выбранный во второй раз - вторым выбранным предметом и т.д.

В первый раз можно выбрать любой из n предметов старой группы. То есть в качестве первого выбранного предмета может выступать любой из n предметов старой группы. После того как мы выберем первый предмет, в старой группе останется n - 1 предметов. В новой группе будет 1 предмет.

Берем еще один предмет из старой группы - это будет второй выбранный предмет. Второй выбранный предмет может быть одним из n - 1 оставшихся предметов. После того как мы выберем его, в старой группе останется n - 2 предмета. В новой группе будет 2 предмета.

То есть, что получается, до первого раза у нас было 0 выбранных предметов и мы могли взять в качестве первого любой из n имеющихся предметов. Вариантов составления новой группы по крайней мере n. При втором выборе мы имеем 1 выбранный до этого предмет, n -1 оставшихся предметов. Теперь, для каждого из n вариантов составления новой группы, которые различаются первым предметом, имеется n-1 вариант добавления второго предмета. Всего вариантов n*(n - 1) пока. Когда выбираем предмет в третий раз, уже выбранных предметов 2 (их поместили в новую группу) и оставшихся n - 2. То есть, для каждого из n(n-1) вариантов новой группы, различающихся первым и вторым предметами, можно взять любой из n-2 оставшихся предметов старой группы. Тогда общее число вариантов составления новой группы из трех предметов будет n (n - 1) (n - 2) - для каждого из n первых предметов можно взять n - 1 оставшихся предметов в качестве второго, потом останется n- 2 предмета, которые можно взять в качестве третьего.

Если выбираем k-й предмет, то уже выбрано k - 1 предметов. Значит осталось n - (k - 1) = n - k + 1 вариантов для k-го предмета. А всего вариантов составления новой группы из k предметов будет A(n, k) = n(n - 1)(n - 2)...(n - k + 1). Такую комбинацию (новую группу) из n предметов (из какой-то старой группы) по k предметов (для этой новой группы) называется размещением без повторений.

Если брать предметы до полного исчерпания старой группы получим новую группу из n предметов. Такая группа может быть получена n(n - 1)(n - 2)...1 = n! различными способами расположения предметов. Такие группы, которые состоят из одних и тех же предметов, но составленных в различном порядке, называются перестановками. Перестановки важны для понимания определителей матриц. Очень показательный пример и теория есть в книге Виленкина "Комбинаторика" 1969 года про ладьи на шахматной доске (можно скачать здесь).

Сделаем размещения по k предметов из n. Ясно, что среди них будут группы, состоящие из одинаковых элементов, но стоящих в различном порядке друг за другом. Посчитаем число групп, одинаковых только по составу (без учета порядка следования предметов в группе). Для каждого размещения, различающегося только составом предметов, имеется k! вариантов их следования друг за другом - то есть перестановок. Число комбинаций C(n, k) по k предметов, различающихся только составом, умноженное на число перестановок в каждой из них (оно для всех равно k!), дадут число размещений без повторения A(n, k):

C(n, k) k! = A(n, k). Тогда число размещений, различающихся только составом, равно C(n, k) = A(n, k) / k!. Размещения, различающиеся только составом, называются сочетаниями.

Для размещения можно использовать формулу A(n,k) = n! / (n - k)!. При сокращении получится та же A(n, k) = n(n - 1)(n - 2)...(n - k + 1).