Теорема 8. Число різних можливих сполучень з повтореннями і з n елементів по m елементів при довільних натуральних n іm обчислюється за формулою
(1)
Доведення. Сполучення з повтореннями з n елементів по m елементів можна записати, користуючись тільки цифрами 0 і 1. Це можна зробити так: спочатку запишемо стільки одиниць, скільки елементів першого типу входить у комбінацію, потім напишемо нуль, після нього напишемо стільки одиниць, скільки елементів другого типу входить у комбінацію, потім знову нуль і т.д., тобто нуль ставиться між двома групами одиниць елементів двох різних типів. Якщо елементи якого не будь типу зовсім не входять у дану комбінацію, то пишемо підряд два нулі. Наприклад, якщо розглядаються комбінації з чотирьох елементів а, b, с, d по шість, то запис (100110111) відповідає такій комбінації {а,с,с,d,d,d}, а запис (110111001) зображує таку комбінацію {а,c,c,d,d,d}.
Впорядкована множина, складена з одиниць і нулів, відповідна сполученню з повтореннями з n елементів по m елементів, буде мати рівно m одиниць і n-1 нулів, бо кількість одиниць дорівнює числу елементів у сполученні, а число нулів на одиницю менше числа типів елементів, оскільки нуль вживається лише для розділення типів елементів. Тому мiж так утвореними впорядкованими множинами з нулів та одиниць i сполученнями з повтореннями встановлюється взаємно однозначна відповідність. Але оскільки кожна така впорядкована множина складається з m одиниць і n-1 нулів,. то кількість усіх сполучень з повтореннями з n елементів по m елементів дорівнюй кількості різних способів упорядкування (n+m-1)-елементної множини, що містить m одиниць і n-1 нулів, тобто
=
=
Наслідок. Якщо зіставити одержану формулу з формулою сполучень без повторень з n+m-1 елементів по n-1 елементу, тобто з формулою
=
то побачимо, що праві частини цих формул однакові, тому
==== (2)
Отже, число сполучень з повтореннями з n елементів по m елементів дорівнює числу сполучень без повторень з n+m-1 елементів по n-1 елементів.
Приклад 1. У поштовому відділенні продаються листівки 8 різних видів. Скількома способами можна купити в ньому 10 листівок?
Розв'язання. Оскільки порядок покупки листівок не істотний, а купити їх не можна всі різними (10>8), то маємо сполучення з повтореннями з 8 елементів по 10 елементів. Число їх дорівнює
=
Відповідь. 19448.
Приклад 2.Шість пасажирів сідають на вокзалі в електропотяг, який складається з5 вагонів. Скільки можливих способів посадки пасажирів у вагони, якщо істотним є лише кількість пасажирів?
Розв’язання. Тут маємо сполучення з повтореннями з 5 елементів по 6. Число їх дорівнює
=
Відповідь. 210.