ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     1.5. КОМБІНАЦІЇ З ПОВТОРЕННЯМ

      Нехай маємо множину, що вміщуєпредметів різного виду. Число елементів кожного виду необмежене. Поставимо задачу визначити кількість наборів довжиною, які не залежать від порядку. Такі набори називають комбінаціями з повторенням, кількість яких та позначення наступне
.
Виведемо дану формулу. Нехай- вихідні довільні типи елементів, загальне число яких.Розглянемо довільні комбінації з повторенням:
з даних елементів.
З урахуванням того, що порядок елементів в комбінаціях нас не цікавить, побудуємо їх наступним чином:
,
де елементи кожного типу впорядковані і відділені один від одного вертикальною рискою, за виключенням останньої серії елементів. З урахуванням рисок, довжина такого набору становить
,
де
- кількість елементів в наборі,
- число вертикальних рисок. Такий набір можна задати вибором ізмісця-чином для положення вертикальних ліній.
Це можна зробитиспособами, тобто- число комбінацій з повторенням ізпо.

      Приклад 7. Скількома способами четверо дітей можуть поділити між собою 80 цукерок?
Розв'язання. Поставимо у відповідність кожному розподілу цукерок комбінації з повторенням наступним чином. Нехай типами елементів будуть діти - , тобто,для яких треба скласти всі комбінації довжиною.Належність в наборі будь-якого елементу відповідає належності даної цукерки відповідній дитині,причому порядок в такому наборі не має значення, все одно яка з цукерок дістанеться тій чи іншій дитині. За таких умов, число способів розподілу цукерок між дітьми рівне.

      Приклад 8. Скількома способами можна розсадитиприбулих гостей серед гостей, що вже сидять за круглим столом?
Розв'язання. Очевидно, що міжгостями, що сидять за столом, існуютьпроміжків, в яких можна розміститиприбулих гостей. Це можна зробити
способами.

ЗМІСТ