![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Підрахунок числа перестановок і співвідношень можна визначити за допомогою рекурентних співвідношень, що важливі у комбінаториці.
Рекурентні співвідношення. Множину 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.
Застосування рекурентних співвідношень разом із граничними умовами дозволяє обчислити число відповідних вибірок елементів з даної множині. За допомогою цих співвідношень можна вивести формули, отримані раніше для перестановок і сполучень.
Дата публикования: 2014-11-18; Прочитано: 1001 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!