43. Покупка пирожных

В кондитерском магазине продаются пирожные 4 сортов: наполеоны, Эклеры, песочные и слоеныЕ. Сколькими СПособами можно купитЬ 7 пирожных?

Если записывать порядок, в котором продавец кладет пирожные в коробку, то получится кортеж длины 7 из 4 элементов — сортов пирожных. Однако два кортежа одного и того же состава, например (н, Н, Э, п, с, с, Э) И (э, н, с, н, э, П, с) (здесь записаны первые буквы названий пирожных), означают по сути дела одну н ту же покупку; 2 наполеона, 2 эклера, 2 слоеных пирожных и 1 песочное. Поэтому два способа сделать покупку надо считать различными лишь в случае, когда соответствующИЕ кортежи отличаются своим составом. Итак, мы ПришЛи к следующей ЗАдаче.

Сколько различных составов могут иметь кортежи ДЛины K из п элементов?

По-другому эту же задачу можно сформулировать и ТАк: назовем два кортежа Эквивалентными, если они имеют одинаковый состав. На сколЬКо классов эквивалентности раЗБивается при этом вся совокупность кортежей длины K из п элемЕНтов? Такие классы эквивалентности назыВают Сочетаниями с повторЕНиями из П элементов по K, А их число обозначают .

Чтобы стало ясно, как вычислять в ОбщеМ случае вернемся к задаче о пирожных. Каждую Покупку Пирожных можно задать кортежем длины 4, состоящим ИЗ неотрицательных целых чисел, сумма которых Равна 7. Например, кортеж (3, 2, 0, 2) означает, что куПлеНо 3 наполеона, 2 эклера, НИ одного песочного пирожного и 2 слоеных. Конечно, прежде чем задавать покупки кортежами чисел, сНАчала надо договориться, в КакоМ Порядке Мы называем сорта пирожных; иначе можно ОказатьсЯ в положении мужа, который никаК не мог вспомнить, Что Ему поручила купить жена: 6 бутылок молока и 2 БУтылки пива или 2 бутылки молока и 6 бутылок Пива. Но каждый кортеж из неотрицательных целых чИСеЛ можно записать, пользуясь лишь единицами и нулями: для этого достаточнО Заменить Каждое число столькими Единицами, чему равно этО число, а единИЦы, СоответсТвующими различным числам, Отделить друг От Друга Нулями. Например, кортеж (3, 2, 0, 2) запишется с поМоЩЬю едИНиц и нулей так:

(1, 1, 1, 0, 1, 1, 0, 0, 1, 1),

А ЗапиСи (1, 1, 0, 1, 1, 1, 0, 1, 0, 1) Соответствует кортеЖ (2, 3, 1, 1). Поскольку числовые кортежи, задающие РаЗличные варианты покуПКи пирожНЫх, имеют дЛиНу 4, а Сумма входящих в них чисел равна 7, то КоличестВо нулей в их записях будет равно 3, а количестве единиц равно 7. Но чиСЛо перестановок из 3 нулей и 7 единиц РАвно

Значит, покупку можно совершить 120 способами.

В общем случае формула для выводится Точно Так же. Любой состав кортежа длины K из П ЭлемЕнтов имеет вид , где — НеотрецательНые целые числа, сумма которых равна K. Заменяя Каждое из чисел J, соответствующим количеством ЕдиниЦ И Разделяя нулями единицы, отвечающие Различным ЧИслам, получаем кортеж из N-1 нулей и K едИНиц. При этом каждому составу отвечает одна и только одНА Запись с помощью нулей и единиц, а кажДАя такая запись Задает один и толЬКо один состав. Поэтому число различных составов равно числу перестановок с Повторениями иЗ N-1 нулей и K единиц, т. Е. . Итак, Мы доказали, что

(6)

< Предыдущая		Следующая >