Рекурентні співвідношення

Підрахунок числа перестановок і співвідношень можна визначити за допомогою рекурентних співвідношень, що важливі у комбінаториці.

Рекурентні співвідношення. Множину r-перестановок з n різних елементів можна розбити на два класи так, що перестановки одного з них не містять деякого фіксованого елемента вихідної множині, а всі перестановки іншого класу обов'язково містять цей елемент. Очевидно, перший клас складається з
P(n-1, r)-перестановок, а другий – з r(n-1, r-1), тому що фіксований елемент може займати одне з r положень у кожній з P(n-1, r-1) підстановок. Звідси випливає рекурентна формула

P(n, r) = P(n-1, r) + r(n-1, r-1)

Символ P(k, 0), що не має комбінаторного змісту, прийнято вважати дорівнюючим одиниці. P(k, 1) = k для будь-якого цілого додатнього k і P(k, s) = 0 при k < s. Ці співвідношення служать граничними умовами для одержання рекурентного співвідношення. Якщо покласти r = n, маємо: P(n, n) = P(n-1, n) + n(n-1, n-1) = n(n-1, n-1) = n(n-1) P(n-2, n-2) =... =
= n(n-1)... 2 1 = n!

Приклад. Рекурентне співвідношення для числа r-сполучень з n різних елементів має вигляд

С(n, r) = C(n-1, r-1) + C(n-1, r), n r,

де другий доданок враховує сполучення, що не містять фіксованого елемента, а перший – усі сполучення з цим елементів. Граничні умови для цього співвідношення C(n, 0) = C(1, 1) = 1 і C(k, s) = 0 при k < s.

Приклад. Якщо розбивати множину r-сполучень з повтореннями з
n елементів на дві непересічних підмножини, одна з яких містить всі такі сполучення, що не містять фіксованого елемента, а інша – такі сполучення, що містять цей елемент, одержуємо рекурентне співвідношення

F(n, r) = f(n-1, r) + f(n, r-1)

При цьому n і r безпосередньо не зв'язані між собою і допускаються як n r, так і n r. Граничні умови в цьому випадку наступні

f(n, 1) = n; f(n, o) = f(1, r) = 1.

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