Комбінації з повтореннями

Комбінації з повтореннями схожі на звичайні комбінації, лише ми дозволяємо елементам з основної множини M повторюватися.

Означення і формула

Почнімо з якогось гарного прикладу: ти приходиш до магазину й хочеш купити на похід дванадцять пляшок лимонаду. На полиці є чотири різні смаки. Тепер маєш кілька варіантів, як купити пляшки: можна, наприклад, купити 5 «Груш», 2 «Лимони», 1 «Апельсин» і 4 «Вишні», а можна купити кожного смаку рівно по три пляшки. Скільки всього існує різних способів купити пляшки так, щоб їх було рівно дванадцять?

Отже, маємо основну множину $M = {\text{Груша}, \text{Лимон}, \text{Апельсин}, \text{Вишня}}$ і запитуємо, скільки існує наборів із k елементів, де k = 12, які містять елементи з множини M і в яких порядок не важливий.

Виведення формули вже дещо складніше, ніж в інших комбінаторних задачах. Спершу уявимо нашу покупку як послідовність нулів та одиниць так, що кількість одиниць відповідає кількості куплених пляшок даного смаку, а нуль відокремлює окремі смаки. Тож 111011101111101 каже нам, що ми купили три «Груші» (перші три 1), потім три «Лимони» (0 — роздільник, ще три 1), потім п'ять «Апельсинів» (0 — роздільник, а потім п'ять 1) і нарешті одну «Вишню». Увесь принцип показано на рисунку нижче:

$$ \underbrace{111}_{\text{Гр}}0\underbrace{111}_{\text{Лим}}0\underbrace{11111}_{\text{Ап}}0\underbrace{1}_{\text{Виш}} $$

Якби ми хотіли купити 6 «Груш», 4 «Лимони», 2 «Вишні» і жодного «Апельсина», послідовність виглядала б так:

$$ \underbrace{111111}_{\text{Гр}}0\underbrace{1111}_{\text{Лим}}00\underbrace{11}_{\text{Виш}} $$

Зауважимо, що довжина цієї послідовності завжди дорівнює 15: має бути 12 одиниць, щоб купити разом 12 пляшок. І мають бути три роздільники, щоб відокремити чотири різні смаки. Залишається підрахувати, скільки всього існує таких послідовностей довжини 15, що містять рівно три нулі.

Досить підрахувати розташування нулів: щойно ми розмістили 3 нулі серед 12 одиниць, маємо якусь допустиму комбінацію пляшок. Іншими словами: маємо 15 клітинок, і 3 з них треба зайняти нулями. Решту клітинок автоматично займемо одиницями.

Це вже проста задача на комбінації без повторень. Пронумеруємо 15 клітинок числами {1, …, 15} і тепер із цієї множини щоразу вибираємо трійки чисел, і так отримуємо три індекси, де розмістимо нуль. Наприклад, для комбінації {2, 4, 7} отримаємо послідовність: 101011011111111. На 2-му, 4-му і 7-му місці стоїть нуль, решта — одиниці. Отже, існує всього

$$ {15\choose3} = 455 $$

різних способів розмістити в 15 клітинках нулі, а тому й 455 різних способів купити 12 пляшок, якщо є чотири різні смаки лимонаду.

Попередні міркування можна узагальнити. Якщо маємо множину елементів M з n елементів і вибираємо з неї набори з k елементів, причому окремі елементи можуть повторюватися, то складаємо послідовність нулів та одиниць довжини n + k − 1 (k одиниць і n − 1 нулів) і з'ясовуємо, скількома способами можна розмістити n − 1 нулів, тож кількість комбінацій з повтореннями, яку позначимо $\overline{C}_n^k$, дорівнює

$$ \overline{C}_n^k = {n+k-1 \choose n-1} = {n+k-1\choose k}. $$

Останнє перетворення ми могли собі дозволити завдяки основним співвідношенням між біноміальними коефіцієнтами.

Розв'язані приклади

1. Скількома способами можна розподілити 20 безкоштовних квитків на прем'єру вистави між 10 пенсіонерками? Це приклад на комбінації з повтореннями, бо одна пенсіонерка може отримати кілька, потенційно всі, безкоштовних квитків. Треба лише правильно усвідомити, що таке n і що таке k. Насправді ми вибираємо 20-елементні комбінації з повтореннями з 10 пенсіонерок, інакше кажучи, утворюємо послідовність нулів та одиниць так, що її довжина дорівнює 29, вона містить 20 одиниць і 9 нулів. Тож n = 10, k = 20. Отримуємо результат:

$$ \overline{C}_{10}^{20} = {10 + 20 - 1 \choose 20} = 10{,}015,005. $$