Задачи для самостоятельного решения

19. Сколькими способами можно представить число 1000000 в виде произведения 3 сомножителей, если произведения, отличающиеся порядком множителей, считаются различными?

20. Решите эту же задачу, если порядок множителей не учитывается.

В рассмотренных ранее задачах не накладывалось никаких ограничений на число предметов, попадающих в каждый ящик − оно могло быть любым. Но во многих случаях число предметов, попадающих в каждый ящик четко оговорено. Рассмотрим некоторые примеры.

Примеры решения некоторых комбинаторных задач

Задача. При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?

Решение.Раздел костей можно выполнить следующим образом. Сначала каким-то образом положим все 28 костей в ряд. После этого первый игрок берет первые 7 костей, второй − вторые 7 костей, третий − следующие 7 костей, а четвертый забирает остаток. Ясно, что таким образом можно получить всевозможные разбиения костей.

Так как число всех перестановок из 28 элементов равно 28! то может показаться, что общее число всех способов раздела равно 28!. Но это неверно − ведь первому игроку совершенно безразлично, возьмет он сначала кость 6:6, а затем кость 3:4 или наоборот, сначала кость 3:4, а затем кость 6:6; ему важен лишь окончательный итог. Поэтому любая перестановка первых 7 костей не меняет существа дела. Не меняет его и любая перестановка вторых 7 костей, третьих 7 костей и последних 7 костей. В силу правила произведения получаем (7!) перестановок костей, не меняющих результата раздела.

Таким образом, 28! перестановок костей делятся на группы по (7!) перестановок в каждой группе, причем перестановки из одной группы приводят к одинаковому распределению костей. Отсюда следует, что число способов раздела костей равно

Это число приближенно равно 4,7 10 .

К тому же результату можно прийти иначе. Первый игрок должен выбрать 7 костей из 28. Так как порядок этих костей безразличен, то он имеет  способов выбора. После этого второй игрок должен выбрать 7 костей из оставшихся 21 кости. Это можно сделать  способами. Третий игрок выбирает из 14 костей, а потому имеет возможностей выбора. Наконец, четвертому игроку остается . По правилу произведения получаем, что полное число возможных способов выбора:

Ответ:  способами.

Задача о домино относится к комбинаторным задачам на раскладывание предметов по ящикам заданного объема. Общая постановка этих задач такова.

Даны п различных предметов и т ящиков. Надо положить в первый ящик п , предметов, во второй − п₂ предметов, ...

В задаче о домино роль ящиков выполняли игроки, а роль предметов − кости. Расставим все предметы в ряд (или занумеруем их), а потом надпишем над каждым предметом номер ящика, в который его кладут. Получившаяся последовательность номеров ящиков образует перестановку с повторениями, состоящую из п  чисел 1, п₂ чисел 2, ..., п_т чисел т.

Каждая раскладка предметов по ящикам определяет такую перестановку. И наоборот, каждая такая перестановка определяет свой способ раскладки − в первый ящик попадают те предметы, над которыми стоит 1, во второй − над которыми стоит 2 в т-й − над которыми стоит т. Тем самым устанавливается соответствие между перестановками с повторениями и раскладкой предметов по ящикам. Поэтому число различных раскладок по ящикам равно числу соответствующих перестановок с повторениями Р(п ,п₂,...,п_т). Получаем следующий вывод.

Число способов разложить п +п₂+...+п_т разных предметов по т различным ящикам так, чтобы в первый ящик легло п предметов, в второй ящик легло п предметов,…, в т ящик легло п  предметов, равно