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

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

Отже,

P(n, r) = P(n – 1, r) + rP(n – 1, r – 1),

де P(k, 0) = 1, P(k¸1) = k, P(k, s) = 0 при k < s.

Поклавши r = n, дістанемо:

P(n, n) = P(n – 1, n) + nP(n – 1, n – 1) = 0 + nP(n – 2, n – 1) +

+ n(n – 1)P(n – 2, n – 2) = n(n – 1)P(n – 3, n – 2) +

+ n(n – 1)(n – 3)P(n – 3, n – 3) = … = n(n – 1)(n – 2) … 2  1 = n!

Для кількості r-сполучень з n елементів маємо

C(n, r) = = + =

= C(n – 1, r) + = C(n – 1, r) + C(n – 1, r – 1),

C(n, 0) = C(1, 1) = 1, C(k, s) = 0  k < s.

Основні властивості кількості сполук

1. = , k  n.

Доведення. = = = .

2. = , k  n.

Доведення.

= = = .

3. = + , k  n.

Доведення.

+ = + =

= = = .

Біном Ньютона

Поставимо у відповідність кожному об’єкту з множини {₁, ₂, …, _n} двочлен вигляду 1 + _ix (i = 1, 2, …, n), перемножимо їх і зведемо подібні члени:

(1 + ₁x)(1 + ₂x) … (1 + _nx) = 1 + a₁x + a₂x² + … + a_nxⁿ.

Коефіцієнт a_r множини є сумою добутків, кожен з яких утвориться r-елементами з n (r-сполучення), причому a_r таких добутків C(n, r). Якщо покласти ₁ = ₂ = … = _n = 1, то будь-який добуток r-сполучень елементів дорівнює 1 і, отже, a_r = C(n, r) = . Отже,

(1 + x)ⁿ = + x + x² + … + x^{n – 1} + xⁿ.

Поклавши x = 1, маємо = 2ⁿ.

При x = –1 знаходимо = 0.

Назвемо вираз (a + x)ⁿ = a^{n – k}x^k біномом Ньютона.

Властивості розкладу бінома Ньютона і біномних коефіцієнтів

1. Кількість доданків в розкладі бінома (x + a)ⁿ дорівнює n + 1.

2. У кожному доданку сума показників букв a і x дорівнює n.

3. Загальний член розкладу T_{k + 1} = a^{n – k}x^k.

4. Коефіцієнти розкладу, рівновіддалені від його кінців, рівні між собою:

= , k = .

5. Середній член розкладу при n = 2p має найбільший біноміальний коефіцієнт. Якщо n = 2p – 1, то є два „середніх” члени розкладу з найбільшим коефіцієнтом.

Оскільки = , то послідовність сполук при фіксованому n буде зростаючою, якщо > 1, або k < . Якщо n = 2p, то k < p + і найбільшим буде коефіцієнт = . При n = 2p – 1 маємо k < p, тобто k = p – 1 = і найбільшим буде , а також .

6. Сума біноміальних коефіцієнтів з парним k дорівнює сумі значень з непарним k:

= ,

де [x] – ціла частина x, яка є найбільшим цілим числом, що не перевищує x.

Поліномні твірні функції

Добуток (1 + ₁x) … (1 + _nx) породжує r­-сполучення з n різних елементів, в яке кожний об’єкт із множини може входити не більше як один раз. Щоб одержати інші вигляди сполучень, треба брати й інший вигляд співмножників.

Якщо об’єкт _I може входити в сполучення 0, 1, …, k разів, то замість 1 + _іx потрібно взяти співмножник 1 + _ix + … x^k. Тоді при ₁ = ₂ = … = _n = 1 коефіцієнти a_l мночолена A(x) = 1 + a₁x + … + a_nxⁿ будуть r­-сполученням з n різних елементів із повтореннями.

Приклад 1. Знайти за наведеною схемою для сполучення з трьох елементів {a, b, c} зі специфікацією {3, 1, 2} добуток: (1 + x + x² + x³)(1 + x)(1 + x + x²) = 1 + 3x + 5x² + 5x² + 6x³ + 5x⁴ + 3x⁵ + x⁶.

Тут коефіцієнт при x⁴ дає шукане число n-сполучень, тобто:

3 – кількість 1-сполучень (це a, b, c);

5 – кількість 2-сполучень (це aa, ab, ac, bc, cc);

6 – кількість 3-сполучень (це aaa, aab, aac, abc, acc, bcc).

Многочлен A(x) = a₀ + a₁x + … + a_nxⁿ називається поліномною твірною функцією для послідовності a₀, a₁, …, a_n.

У випадку, що розглядається, ця послідовність є r-сполученням з n елементів із повтореннями. Біном Ньютона – це твірна функція для сполучень без повторень.

Для сполучень із необмеженими повтореннями елементів n типів твірною функцією буде вираз (1 + x + x² + … + xⁿ + …)ⁿ, який можна записати у вигляді 1 + x + x² + … + xⁿ + … = = (1 – x)^–1.

Розглядаючи вираз (1 – x)^–n як біном Ньютона з від’ємним показником (–n) формально дістанемо

(1 – x)^–n = = =

= = = .

Отже, .

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

(x + x² + x³ + …)ⁿ = xⁿ(1 + x + x² + …)ⁿ = xⁿ(1 – x)^–n = =

= .