Комбинаторика. Число сочетаний, число разбиений.

Задача 26.

В олимпиаде участвовало 20 человек.

1) Сколько может быть различных списков победителей олимпиады (1,2,3 место)?

2) Сколько может быть различных команд по 3 участника на следующий тур может быть?

Решение.

1) Число размещений  =  = 6840.

2) Число сочетаний  =  = . = 1140.

 

Задача 27.

Сколько способов составить команду из 4 человек, если есть 7 спортсменов?

Решение.

Число сочетаний  = .  

 

Контрольная работа из 2 задач.  

Практика 6.

Задача 28.

Сколько способов разложить 4 шара по 2 ящикам так, чтобы в каждом ящике оказалось ровно по 2 шара?

Решение. Сначала из 4 выбрать 2 шара для 1 ящика, способов .

Затем из оставшихся 2, выбрать 2 во второй ящик,  способ.

 =   =  = 6. 

Теперь учтём тот факт, что эти пары шаров равнозначны, то есть мы могли сначала заполнять 2-й ящик, затем 1-й. Всего 2 множества по 2 шара, число перестановок равно , поэтому 6 делим на 2, получаем 3. Ответ. 3.  

Конкретно: 

12 34 13 24 14 23    23 14  24 13 34 12    

Но 6-й случай уже учтён (см. 1-й). 5-й соответствует 2-му, 4-й 3-му.

То есть разбиений в 2 раза меньше.

 

Разбиение множества, числа Стирлинга, числа Белла.

Задача 29. Сколько способов разложить 4 шара по 2 ящикам так, чтобы в каждом ящике был по крайней мере один шар?

Решение. Здесь мы имеем дело просто с разбиением 4-элементного множества на 2 непустых подмножества, то есть нужно найти число Стирлинга 2-го рода  = 7.

 

Конкретно эти 7 вариантов: 

1 234 2 134 3 124 4 123  

12 34 13 24 14 23  

 

Задача 30 (РП).

Сколько существует разбиений множества ?

Решение.   Число всех разбиений равно числу Белла , то есть сумме всех чисел Стирлинга в строке матрицы при :

Таких разбиений всего 5. В данном случае их немного, можем все перечислить:

1) на одно подмножество

2) на 2 подмножества , , .

3) на 3 подмножества . 

Задача 31.    Имеется 7 шаров. Сколько способов разложить их в 4 коробки, так, чтобы в каждой коробке был хотя бы один шар?

Решение.   Нужно узнать число разбиений 7-элементного множества на 4 непустых подмножества, то есть .

 = 350.

Вспомним 2 способа вычислить это: 

1) . 

2)  =  =  =

.

Например, 12 34 5 67    или 1  2    3   4567 

(1,1,1,4) (1,1,2,3) (1,2,2,2) 

 

Задача 32. Сколько существует способов разложить 12 шаров по 4 ящикам так, чтобы в каждом ящике оказалось ровно по 3 шара?

Решение.

Сначала из 12 выбрать 3 шара для 1 ящика, способов .

Затем из оставшихся 9, выбрать 3 во второй ящик,  и так далее.

 =  =  =  =

 =  =  =  =  = 369600.

Теперь учтём тот факт, что эти тройки шаров равнозначны, то есть мы могли сначала заполнять 2-й ящик, затем 1-й и т.д. Всего 4 множества по 3 шара, число перестановок равно , поэтому 369600. Делим на 24, получаем 15.400. Ответ. 15.400

 

Задача 33. Доказать свойство (= ещё одну формулу) для чисел Стирлинга 2 рода: . 

(Другими словами, числа из столбца слева можно будет умножать не на степени , а на числа из треугольника Паскаля, и получится то же самое).

Решение.

1) Пусть подмножество из  элемента разбито на  подмножеств. Тогда -й элемент образует -е подмножество.

Таких случаев суммарно .

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

Итак, уже имеется сумма + ,

что можно представить как .

3) Если новый -й элемент образует -е подмножество вместе с какими-то двумя элементами старого подмножества, то число таких случаев , и в каждом из таких случаев оставшееся -элементное множество может быть разбито на   подмножеств, число таких случаев . Итак, добавляется слагаемое

. 

4) Мы дойдём до того, что станет , далее значения будут 0. Это  вычисляется так: . Последнее слагаемое .

Таким образом,  (доказывали сначала для бОльших номеров, потом для меньших, а сумму удобнее записать от меньшего к большему).  

Нужно отступить по диагонали влево и вверх, и умножать числа столбца на числа из треугольника Паскаля, для числа сочетаний из , как скалярное произведение векторов. Посмотрим, как это будет. Например, . 

Тогда  =  

В одном крайнем слагаемом в таком случае всегда один сомножитель   равен 1, в последнем . 

 =

= . 

Здесь , соответственно выбираем эту строку из треугольника Паскаля.

 

 =  =

 =  = 90.

Перерыв

Напомним формулы: 

	Без повторений	С повторениями
Перестановки
Размещения
Сочетания