Тема 8. Рекурентні співвідношення. Біном Н'ютона.

Питання теми

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

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

3. Властивості біноміальних коефіцієнтів.

Основні терміни теми : перестановки, сполучення, біном Ньютона.

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

Метод рекурентних співвідношень, дозволяє знаходити значення деякої функції для заданої величини аргументу через менші значення аргументів. Стосовно комбінаторики цей метод дає можливість знаходити розв'язок комбінаторної задачі для n предметів через розв'язок аналогічної задачі з меншим числом предметів за допомогою деякого співвідношення, яке називається рекурент¬ним співвідношенням. Метод рекурентних співвідношень добре відомий з курсу шкільної математики, де він застосовувався при визначенні сум арифметичної і геометричної прогресій та при визначенні n-го члена цих прогресій. Розглянемо ще деякі приклади.

1. Ряд чисел Фібоначчі. Цей ряд для n > 2 задається такими

співвідношеннями:

а1 = а(1) = 1, а2 = а(2) = 1, аn = аn-1 + аn-2.

Користуючись ними, одержимо послідовність чисел, яка відома під назвою послідовності чисел Фібоначчі.

2. Квадрати натуральних чисел. Розглянемо послідовність

квадратів натуральних чисел а1 = а(1) = 12, а2 = а(2) = 22, ..., аn =

= а(n) = n2, ... . Користуючись формулою скороченого множення

(а + b)2 = а2 + 2ab + b2, одержимо таку рекурентну формулу: аn+1 =

= (n + 1)2 = n2 + 2n + 1 = аn+ 2n + 1.

Використовуючи її, можна знаходити квадрати чисел, не виконуючи складних обчислень. Наприклад, коли відомо, що 152 = 225, то легко знайти 162. Дійсно, 162 = 225 + 2 *15 + 1 = 225 + 31=256.

Аналогічно можна одержати формулу і для обчислення кубів натуральних чисел.

3. Для r- перестановок 

 

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

4. Для r-сполучень рекурентна формула має вигляд

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

де другий додаток  ураховує сполучення яке не має фіксованого елемента, а перший всі сполучення с цим елементом.

5. Так само, розбиваємо множину r- сполучень з повторенням з n елементів на дві непересічні множини, одна з котрих містить у собі всі такі сполучення, які не мають фіксованого елемента, а друга -  такі сполучення, які мають цей елемент. Отримуємо рекурентне співвідношення:

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

2. Біном Н’ютона

З елементарної математики добре відомі формули скороченого множення:

(a + b)2 = a2 + 2ab + b2 і (a + b)3 = а3 +3a2b + 3ab2 +b3.

Поставимо у відношення до кожного об’єкту з множини  двочлен виду 1+  (i=1,2,...n) та перемножимо їх:

 

Коефіцієнт  багаточлена являє собою суму добутків, кожна з яких  утворюється двома елементами з n (r- сполучень), причому  в купі в  є С(n,r) таких добутків. Якщо покласти  , тоді будь-який  добуток r- сполучень елементів дорівнює 1 та  .

Таким чином: 

Формула, яку ми отримали, має назву біном Ньютона, а сполучення з n різних елементів  називається біноміальним коефіцієнтом.

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

n

n=0               1         

n=1               1          1         

n=2               1          2          1         

n=3               1          3          3          1         

n=4               1          4          6          4          1         

n=5               1          5          10        10        5          1         

n=6   1          6          15        20        15        6          1         

...       ...          ...          ...          ...          ...          ...          ...          ...

ч

У n-му рядку трикутника Паскаля стоять коефіцієнти розкладу бінома Ньютона, причому кожний коефіцієнт, крім двох крайніх, які дорівнюють 1, - це сума відповідних коефіцієнтів із попереднього рядка.

3. Властивості біноміальних коефіцієнтів

Раніше ми вже встановили деякі властивості біноміальних коефіцієнтів.

Нагадаємо їх:

(а) формула симетрії

 

(б) формула додавання

 

(в) формула суми всіх біноміальних коефіцієнтів

 

Користуючись цими властивостями, неважко одержати іще ряд формул.

Наприклад, якщо покласти в біномі Ньютона а = 1, b = -1, то одержимо таку властивість:

(г)  .

Наступну формулу легко можна встановити, виконуючи обчислення.

(д) формула винесення за дужки:

 

Наведемо ще деякі корисні властивості біноміальних І коефіцієнтів:

(е) 

(і) 

(к) 

(л) 

(м) 

(н)