Комбинации с повторение

Комбинациите с повторение приличат на обикновените комбинации, само че позволяваме елементите на основното множество M да се повтарят.

Определение и формула

Ще започнем с един нагледен пример: влизаш в магазин и искаш да купиш дванайсет бутилки бира за излет. На рафта има общо четири различни вида бира. Сега имаш няколко възможности как да купиш бирите – например можеш да купиш 5 Загорка, 2 Каменица, 1 Шуменско и 4 Пиринско или можеш да купиш по точно три бутилки от всеки производител. Колко са общо различните възможности да купиш бирите така, че да са точно дванайсет?

Имаме основното множество M = {Загорка, Каменица, Шуменско, Пиринско} и питаме колко са k-торките, където k = 12, които съдържат елементи от множеството M и при които редът няма значение.

Извеждането на формулата е доста по-сложно, отколкото при останалите комбинаторни задачи. Първо си представяме покупката като редица от нули и единици, така че броят на единиците съответства на броя на купените бутилки от дадения производител, а нулата разделя отделните производители. Така 111011101111101 ни казва, че сме купили три Загорка (първите три 1), после три Каменица (0 е разделител, следват още три 1), после пет Шуменско (0 разделител и после пет 1) и накрая едно Пиринско. Целият принцип е показан на следната фигура:

$$\underset{\text{Заг}}{\underbrace{111}}0\underset{\text{Кам}}{\underbrace{111}}0\underset{\text{Шум}}{\underbrace{11111}}0\underset{\text{Пир}}{\underbrace{1}}$$

Ако искахме да купим 6 Загорка, 4 Каменица, 2 Пиринско и нито едно Шуменско, редицата щеше да изглежда така:

$$\underset{\text{Заг}}{\underbrace{111111}}0\underset{\text{Кам}}{\underbrace{1111}}00\underset{\text{Пир}}{\underbrace{11}}$$

Забелязваме, че дължината на тази редица винаги е 15 – трябва да има 12 единици, за да купим общо 12 бири. И трябва да има три разделителя, за да можем да отделим четирите различни производителя. Остава да пресметнем колко са всички такива редици с дължина 15, които съдържат точно три нули.

Достатъчно е да пресметнем разположението на нулите – щом между 12-те единици разположим 3 нули, имаме някаква валидна комбинация от бири. С други думи: имаме общо 15 клетки и 3 от тях трябва да заемем с нула. Останалите клетки автоматично заемаме с единици.

Това вече е проста задача за комбинации без повторение. Номерираме 15-те клетки с числата {1, …, 15} и сега от това множество избираме всеки път тройки числа, като така получаваме три индекса, където ще поставим нула. Напр. за комбинацията {2, 4, 7} ще получим редицата: 101011011111111. На 2., 4. и 7. място има нула, останалите са единици. Така съществуват общо

$$(\genfrac{}{}{0ex}{}{15}{3})=455$$

различни начина да разположим нулите в 15-те клетки и следователно има 455 различни възможности да купим 12 бири, ако има четири различни вида бира.

Предишните разсъждения можем да обобщим. Ако имаме множество от елементи M с големина n и избираме от него k-торки, като отделните елементи могат да се повтарят, то съставяме редица от нули и единици с дължина n + k − 1 (k единици и n − 1 нули) и търсим по колко начина можем да разположим n − 1 нули, така че броят на комбинациите с повторение, който ще означим с ${\bar{C}}_n^k$, е равен на

$${\bar{C}}_n^k=(\genfrac{}{}{0ex}{}{n+k-1}{n-1})=(\genfrac{}{}{0ex}{}{n+k-1}{k}).$$

Последното преобразуване си позволихме благодарение на основните зависимости между биномните коефициенти.

Решени примери

1. По колко начина могат да се разпределят 20 безплатни билета за премиера на театрален спектакъл между 10 пенсионерки? Това е пример за комбинации с повторение, защото една пенсионерка може да получи повече, потенциално всички безплатни билети. Трябва само да осъзнаем правилно какво е n и какво е k. Всъщност избираме комбинации от 20-ти клас от 10 пенсионерки, с други думи, съставяме редица от нули и единици така, че редицата има дължина 29, съдържа 20 единици и 9 нули. Така n = 10, k = 20. Получаваме резултата:

$${\bar{C}}_{10}^{20}=(\genfrac{}{}{0ex}{}{10+20-1}{20})=10015005.$$