Рассмотрим задачу. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоёные. Сколькими способами можно купить 7 пирожных?
Эта задача не является задачей на размещения с повторениями, так как порядок, в котором укладывают пирожные в коробку, несуществен. Задача ближе к задачам на сочетания. Но она отличается тем, что в комбинации могут входить повторяющиеся элементы, например, можно купить 7 эклеров. Такие задачи называют задачами на сочетания с повторениями.
Чтобы решить эту задачу, поступим следующим образом. Зашифруем каждую покупку с помощью нулей и единиц. Именно, сначала напишем столько единиц, сколько куплено наполеонов. Потом, чтобы отделить наполеоны от эклеров, напишем нуль, а затем – столько единиц, сколько куплено эклеров. Далее снова напишем нуль. Если не было куплено ни одного эклера, то в записи появятся два следующих друг за другом нуля. Далее напишем столько единиц, сколько куплено песочных пирожных, снова напишем нуль, и наконец, напишем столько единиц, сколько куплено слоёных пирожных. Например, если куплено 3 наполеона, 1 эклер, 2 песочных пирожных и 1 слоёное, то получим такую запись: 1110101101. Если же куплено 2 наполеона и 5 песочных, то получится запись: 1100111110.
Таким образом, число различных покупок равно числу перестановок с повторениями, которые можно составить из 7 единиц и 3 нулей. В результате получим:
.
Общая формулировка таких задач такова: имеются предметы 
различных типов. Сколько -комбинаций можно сделать из них, если не принимать во внимание порядок элементов в комбинации?
Эта задача в общем виде решается точно так же, как и задача и пирожных. Именно, надо зашифровать каждую комбинацию с помощью нулей и единиц: для каждого типа написать столько единиц, сколько предметов этого типа входит в комбинацию, а различные типы отделять друг от друга нулями, при этом ели предметы какого-нибудь типа совсем не вошли в комбинацию, то надо писать подряд два или большее число нулей. При этом мы получим столько единиц, сколько предметов входит в комбинацию, т.е. 
, а число нулей будет на 1 меньше, чем число типов предметов, т.е. 
. Таким образом, мы получим перестановки с повторениями из единиц и нулей.
|
|
Число сочетаний с повторениями из элементов типов обозначается 
и равно числу перестановок с повторениями из нулей и единиц. Таким образом:
.
Заметим, что 
.
Пример 11. В почтовом отделении продаются открытки 10 сортов. Сколькими способами можно купить 8 открыток? Сколькими способами можно купить 8 различных открыток?
Р е ш е н и е. В первом случае в покупке могут быть открытки одного и того же сорта и, так как порядок покупки не играет роли, то 
. Во втором случае открытки одного и того же сорта быть не могут, поэтому 
.
Пример 12. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоёные. Сколькими способами можно купить 7 пирожных?
Пример 13. Сколькими способами можно разделить 40 яблок между 4 мальчиками так, чтобы каждый получил по крайней мере 3 яблока (все яблоки считаются одинаковыми)?