4.Сколькими способами можно разложить 19 различных предметов по 5-тиразличным ящикам так, чтобы в 4 ящика легли по 4 предмета, а в оставшийся ящик – 3 предмета?
Решение. В первый ящик 4 предмета можно положить числом
способов, равным C194 =3876. Во второй ящик 4 предмета можно положить,
следовательно, числом способов, равным C154 =1365; в третий ящик – числом способов, равнымC114 =330 , в четвертый – числом способов, равнымC74 =35. Далее предметы для последнего ящика определяются однозначно. Наконец, мы должны учесть, что при распределении групп по 4 предмета используются 4 ящика из 5. Число различных комбинаций по 4 ящика из 5 равноC54 =5.
Таким образом, искомое число способов равно
C194 C154 C114 C74 C54 =305 540 235 000.
Следующие несколько примеров более сложны, но имеют важное прикладное значение.
5. Распределение r шаров по n ящикам. Сколькими способами можно r
неразличимых между собой шаров распределить по n различным ящикам?
34 То есть число способов, которыми можно выбрать три числа из шести без учета порядка, ибо каждой неупорядоченной тройке различных чисел соответствует один и только один упорядоченный набор, в котором эти числа идут по возрастанию.
76
При этом предполагается, что число шаров в каждом ящике может принимать любое значение от 0 до r.
Решение. Будем представлять ящики как промежутки между n +1 черточками (черточки имитируют стенки ящиков), а шары условимся обозначать звездочками. Так, символ
|***|*| | | |****|
означает, что r = 8 шаров размещено поn = 6 ящикам, причем эти ящики содержат последовательно 3, 1, 0, 0, 0, 4 шаров. Такие символы всегда начинаются и кончаются черточками, но оставшиесяn −1 черточку иr звездочек можно разместить в произвольном порядке. Число таких различимых размещений будет равно числу способов выбораr мест средиn + r −1 мест (или, что то же, числу способов выбораn −1 мест средиn + r −1 мест), то есть будет равно числу сочетаний изn + r −1 элементов поr (или, соответственно, поn −1):
Cnr+r−1 =Cnn+−r1−1 .
Замечание. Если ящики считать неразличимыми, то число искомых размещений будет вn! раз меньше (почему?).
5.1. В условиях предыдущей задачи указать число способов, которыми можно r неразличимых между собой шаров распределить поn различным ящикам с условием, что ни один ящик не будет пустым. Очевидно, что при этом должно бытьr ≥ n.
Решение. Условие отсутствия пустых ящиков приводит к следующему ограничению: каждая черточка (кроме крайних) должна быть заключена между двумя звездочками. Это соответствует числу способов, которыми можно разместить n −1 черточку вr −1 промежуток между звездочками. Это число равно, очевидно,
Crn−−11.
