Page 201 - 4496

= F(1, 2; 0) + F(1, 2; 3) + F(1, 2, 3, 5, 10; 8) + F(1, 2, 3, 5,
10; 23) =
=1 + F(1; 1) + F(1; 3) + F(1, 2, 3, 5; 8) + F(1, 2, 3, 5, 10;
23).
Очевидно, що F(1, 2; 0) = 1; F(1, 2; 3) = F(1; 1)= 1; F(1; 3)
= 0; F(1, 2, 3, 5, 10; 23) = 0. Тому права частина перепишеться
у вигляді:
1 + 1 + 0 + F(1, 2, 3, 5; 8) + 0 = 2 + F(1, 2, 3; 3) + F(1, 2, 3;
8) = 2 + 2 + 0 = 4.
Таким чином, задача має 4 різні рішення.
Підкреслимо ще раз, що в цій задачі порядок монет не
важливий.
3. Задача про розмін гривеника (10 копійок). Розглянемо
задачу, в якій зняті обмеження, як на порядок предметів, так і
на їх кількість: розмін гривеника монетами гідністю в 1, 2, 3, 5
копійок. Для цього випадку рекурентне співвідношення має
вигляд

S(1, 2, 3, 5; 10) = S(1, 2, 3; 10) + S(1, 2, 3; 5) + S(1, 2, 3; 0).
Таким чином вся безліч рішень розбивається на
підмножини залежно від числа монет старшої гідності,
використаних для розміну. Знаходимо всі 20 способів розміну:
5∙2 5+1∙5 3+2∙3+1 2∙4+1∙2
5+3+2 3∙3+1 3+2∙2+1∙3 2∙3+1∙4
5+3+1∙2 3∙2+2∙2 3+2+1∙5 2∙2+1∙5
5+2∙2+1 3∙2+2+1∙2 3+1∙7 2+1∙8
5+2+1∙3 3∙2+1∙4 2∙5 1∙10

5.19 Звязок комбінаторики з іншими розділами
дискретної математики
5.19.1 Теорія груп
Розглянемо групу обертань правильного n – кутника.
Породжуючим елементом якого є перестановка:

198