5.5. Сочетания с повторениями

Имеем n классов (или видов) элементов. Из них осуществляется r-выборка (r>n). В выборке элементы будут повторяться (это очевидно).

В этом случае сочетания называются сочетаниями с повторениями.

эклеры песочные слоеные наполеон

Т.е. 4 вида. Из них выбирают 7 предметов для покупки. Это не задача на перестановки: порядок выбора элементов не важен. Это не задача на сочетания: в комбинацию могут входить повторяющиеся элементы.

Закодируем покупку

111 о 111 о о 1

3 эклера 3 песочных 0 слоеных 1 наполеон

Пишем столько единиц, сколько куплено предметов 1-го класса. Затем пишем разделительный ноль, и т.д.

Очевидно, что предложенный способ кодирования покупки позволяет поставить взаимооднозначно

к аждой покупке шифр из 0 и 1

и обратно!

Число покупок равно числу различных вариантов комбинаций, которые можно составить из 7 единиц и 3-х нулей.

В общем случае:

число сочетаний с неограниченными повторениями.

где k – число предметов,

r – число предметов, которые выбираем.

Вывод. Числа сочетаний и перестановок существенно зависят от спецификации элементов, из которых осуществляется комбинация.

5.6. Производящие функции для сочетаний

Изучая свойства сочетаний (на таблице) было показано, что числа сочетаний совпадают с биномиальными коэффициентами, т.е.

функцию называют перечисляющей производящей функцией для сочетаний из n различных элементов или энумератором.

Пример.

а) t=1

б) t=-1

Рассмотрим а) + б).

Пусть i – четное. Тогда

…………………………….

Пусть i – нечетное.

…………………………….

Тогда а) + б) даст

Вычтем из а) б). Тогда:

а) Пусть i – четное, тогда

……………

……………………………….

б). Пусть i – нечетное, тогда

…………………

………………………………

перемножим и суммируем члены при t.

…………………………………………….

Вывод. Приведенные примеры показывают, что с помощью энумераторов легко получаются различные комбинаторные формулы, которые раскрывают свойства чисел сочетаний.

5.7. Производящие функции для перестановок

1. Воспользуемся связью

Тогда производящая функция для перестановок имеет вид:

Числа перестановки появляются в форме коэффициентов при

Воспользуемся производящими функциями для подтверждения ранее полученных результатов.

Перестановки с повторениями.

n элементов

n₁ n₂ n_l

В этом случае производящая функция имеет вид:

число перестановок из n элементов (выборка n=r)

А если надо найти число перестановок из r элементов? (r<n)

Тогда надо найти коэффициенты при и т.д.

2. Рассмотрим r перестановок из n различных элементов с неограниченными повторениями.

(известное соотношение)

(известное соотношение)

искомое число перестановок

Производящие функции, возникающие при изучении перестановок называют экспоненциальной производящей функцией, т. к.