Задачи о размещении различимых шаров по ячейкам

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

.

Задача 6. «Преферанс».

При игре в преферанс каждому из 3 игроков раздают по 10 карт, а 2 карты кладут в прикуп (игра ведется колодой из 32 карт). Сколько различных сдач возможно в этой игре?

Решение. По сути это та же задача, только теперь число карт в группах разное (10, 10, 10 и 2).

Чтобы решить эту задачу, разложим все карты в определенном порядке (например, сначала все пики от семерки до туза, потом в том же порядке все трефы, все бубны, все черви). А затем над каждой картой надпишем номер того игрока, которому она досталась (над картами, идущими в прикуп, пишем цифру 4). Так как каждый из игроков должен получить по 10 карт, то надписанные сверху цифры образуют перестановку с повторениями, состоящую из 10 цифр 1, 10 цифр 2, 10 цифр 3 и 2 цифр 4. Эта перестановка с повторениями имеет состав (10, 10, 10, 2). А число перестановок с повторениями Р (10, 10, 10, 2) равно 2 753 294 408 504 640. Этим 16-значным числом и выражается количество различных сдач при игре в преферанс.

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

Задача 7. «Раскладка по ящикам».

Даны n различных предметов и m ящиков. Надо положить в первый ящик n1 предметов, во второй — n2 предметов, …, в m-й — nm предметов, где n=n1+n2+…+nm. Сколькими способами можно сделать такое распределение?

Решение. В задачах о домино и преферансе роль ящиков выполняли игроки, а роль предметов — кости или карты. Рассуждая точно так же, как в задаче о преферансе, расставим все предметы в ряд (или занумеруем их), а потом надпишем над каждым предметом номер ящика, в который его кладут. Получившаяся последовательность номеров ящиков образует перестановку с повторениями, состоящую из n1 чисел 1, n2 чисел 2, …, nm чисел m. Каждая раскладка предметов по ящикам определяет такую перестановку. И наоборот, каждая такая перестановка определяет свой способ раскладки — в первый ящик попадают те предметы, над которыми стоит 1, во второй — над которыми стоит 2, …, в mй — над которыми стоит m. Тем самым устанавливается соответствие между перестановками с повторениями и раскладкой предметов по ящикам. Поэтому число различных раскладок по ящикам равно числу соответствующих перестановок с повторениями Р (n1, n2, …, nm). Получаем следующий вывод.

Число способов разложить n1 + n2 + … + nm разных предметов по m различным ящикам так, чтобы в первый ящик легло n1 предметов, во второй — n2 предметов, …, в mй — nm предметов, равно

. (19)

В рассмотренных ранее примерах ящики были различимыми. Но это не всегда так. Рассмотрим задачу о сушке грибов.

Задача 8. «Сушка грибов».

Из 60 различных белых грибов хотят сделать 4 связки по 15 грибов в каждой. Сколькими способами это можно сделать?

Решение. На первый взгляд эта задача относится к разобранному выше типу, и ответ дается числом 60!/(15!)4. Но здесь есть одна тонкость. При разделе костей домино важно, кому из игроков достанется данный набор костей, а при составлении связок грибов порядок связок роли не играет — в кладовой все они будут висеть вместе. Поэтому ответ надо еще разделить на 4! — число перестановок связок между собой. Поэтому здесь ответ такой: .

Вообще если надо разделить mp различных предметов на m групп по p предметов в каждой группе, причем порядок групп не учитывается, то число способов раздела равно:

(20)

Задача 9.

Более общей является такая задача: n различных элементов надо распределить на m групп так, чтобы m1 групп содержали по р1 элементов, m2 групп — по р2 элементов, …, mk групп — по рk элементов (m = m1 + … + mk и n = m1 p1 + … + mk pk). Сколькими способами может быть произведен раздел, если:

а) группы различимы, б) группы неразличимы (например, предметы кладутся в одинаковые ящики, которые потом перемешиваются)?

Решение. В первом случае задача аналогична решенной в предыдущем пункте и ответ имеет вид:

. (21)

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

. (22)

Заключение

В курсовой работе рассматриваются производящие функции и способы их использования при решении комбинаторных задач. Приводятся примеры решения задач о размещении различимых шаров по ячейкам, в том числе находится количество способов распределения шаров по ячейкам (лузам), вероятности попадания определенного количества шаров в ячейки (ящики). Разбираются случаи деления шаров (цветов) на нескольких разных видов, задачи о раскладывание шаров (домино, карт) по ячейкам (игрокам) заданного объема и или по не различимым ячейкам (связкам грибов).

Список литературы

Бронштейн, Е. М. Производящие функции // Соросовский образовательный журнал. — 2001. — № 2. — с. 103−108.

Виленкин, И. Я. Комбинаторика / И. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин. — М.: «Фима» — МЦНМО, 2006. — 400 с.

Виленкин, И. Я. Популярная комбинаторика. — М.: Наука, 1975. — 208 с.

Ежов, И. И. Элементы комбинаторики / И. И. Ежов, А. В. Скороход, М. И. Ядренко. — М.: Наука, 1977. — 80 с.

Павский, В. А. Лекции по теории вероятностей и элементам математической статистики: учебное пособие. — Кемеровский технологический институт пищевой промышленности. — Кемерово, 2004. — 184 с.