Page 199 - 4496

P (n 1 , s ) 1 P (n 2 , s 1 )...P (n k , s ) 1

Розглянутий спосіб розділу містить комбінації, при яких
в якій-небудь купці взагалі може не виявитися жодного
предмету, тому його можна назвати несправедливим. Для
забезпечення більш справедливого розділу можна наперед
розкласти частину предметів по куnkах (ящикам, корзинам), а
потім предмети, що залишилися, розкладати описаним
несправедливим способом.

5.17 Задача: Прапори на щоглах

Є n прапорів і k щогл. Скільки різних повідомлень
можна передати, розвішавши прапори на щоглах? В цій задачі
важливим є не тільки кількість прапорів, вивішених на кожній
щоглі, але і їх порядок.
Спочатку вважатимемо, що всі прапори однакові. Тоді:
Р(n, k -1)= (n + k - 1)!/(n!(k - 1)!)
Остаточне рішення - одержаний результат потрібно
помножити на п! оскільки після того, як прапори розвішені
яким-небудь чином, можна ще їх поміняти п! способами,
зберігаючи кількість прапорів на кожній щоглі.
Кількість різних сигналів, одержуваних шляхом
розвішування прапорів на щоглах, можна ще збільшити, якщо
враховувати варіанти, при яких вивішуються не всі прапори,
а, наприклад, 5 прапорів з тих, що є п. Тоді загальне число
розстановок буде
n
 s! P( s, k  )1
 i 1

5.18 Рекурентні співвідношення в комбінаториці
1. Задача про наклейку марок.
Є марки гідністю в 4, 6, 10 копійок. На конверт потрібно
наклеїти марки так, щоб сума складала 18 копійок.
Вважатимемо, що порядок наклеюваних марок важливий,
тобто способи наклейки марок гідністю в 4, 10, 4 копійки і 10,
4, 4 різні способи. Тоді можна написати наступне рекурентне
співвідношення:
196