borisenko_o_a_diskretna_matematika

допомогою розглянутих вище операцій біноміальний коефіцієнт Скп,

збудувати 6 послідовностей, які мають по к + 1 = 5 біноміальних

5. Обчислення С* на основі біноміальних квадратів і прямокутників

Біноміальні квадрати можна отримати з трикутника Паскаля. Щоб отримати біноміальний квадрат, треба повернути трикутник Паскаля вправо на 45° і доповнити його числами, які отримуються з допомогою встановлених вже раніше правил для побудови чисел цього трикутника, до форми квадрата. Побудований таким чином біноміальний квадрат зображено в табл. 3.2.

143

Однією з властивостей цього квадрата є те, що з його допомогою можна обчислювати будь-які біноміальні коефіцієнти Скп з величинами параметрів к< К і п<К + к, де К - максимальне значення параметра к. Відповідно, кожна сторона біноміального квадрата має К + 1 стовпчиків і стільки ж рядків.

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

Наприклад, треба обчислити біноміальний коефіцієнт з к = 5 і п = 7. Для цього спочатку обчислюємо різницю л - Л = 7 - 5 = 2 і потім знаходимо перетин другого рядка з п'ятим стовпчиком. Там знаходиться число 21. Це означає, що біноміальний коефіцієнт С75 має значення 21, що легко перевіряється з допомогою формули для біноміального коефіцієнта, яка подана в явному вигляді:

144

стовпчика і п'ятого рядка.

ДОСТОЇНСТВОМ біноміального квадрата є те, що обчислення біноміальних коефіцієнтів з його допомогою не потребує, крім знаходження різниці п - к , інших арифметичних операцій. Це, у свою чергу, дозволяє отримати велику швидкодію пристроїв, які обчислюють величину біноміальних коефіцієнтів.

Якщо продовжити ту чи іншу сторону біноміального квадрата, то отримаємо біноміальний прямокутник.

Наприклад, у табл. 3.2 збільшимо кількість рядків з 9 до 18. Це вже буде біноміальний прямокутник. Його особливістю є те, що він дозволяє знаходити значення С* для параметра п, який змінюється від 0 до 18.

Кращий спосіб вивчити будь-що - це відкрити самому.

Д. Пойа

145

А =0

Доведення. Візьмемо добуток п двочленів

Р = (х-ах)(х-а2).Дх-ан)

і, якщо розкриємо в ньому дужки та згрупуємо члени з однаковими показниками степеня, одержимо многочлен, розташований за значеннями показників степені, які зменшуються

Р-х" — лг"-І(аГ| +а2 +... + ап) + х"~2{а^а2 + а]а3... + а„_,а„)- -х""3(а1д2а3 н- а,а2а4 +... + ап_2апАа„) + ... + (-1 )"{аха2...а„).

Неважко побачити, що в дужках виразу, який одержано вище, приведені всілякі сполучення к = 1, 2, ..., п елементів множини {а,,й2,...,а„} з п, кількість яких дорівнює С*.

У випадку, коли а, = а2 =... = ап = а,

У цій формулі к-й член буде мати вигляд:

Тк =(-1 )кСкакх"-к.

146

Дискретна математика

Тоді за умови, що

Теорему доведено.

Як бачимо з бінома Ньютона, кількості сполучень біля кожного з його членів відіграють важливу роль. Тому ці кількості були названі біноміальними коефіцієнтами.

Приклад 1. Знайти біном Ньютона для виразу (х - а)2. Розв 'язання. Знайдемо добуток двох двохчленів

(х - а, )(х - а2 ) = х2 - (а, + а2 )х + аїа2.

Припустимо, що а, = а2 = а . Тоді

Приклад 2. Знайти біном Ньютона для виразу (х - а)3. Розв'язання. Візьмемо добуток трьох двохчленів:

(х - а, )(х - а2 )(х - а3) = х3 - (а, + а2 + а3 )х2 + +а,й3 +а2 а3 )х-а|а2 а3 .

Якщо а, = а2 = а3 = а , то

(х - а)(х - а)(х - а) = (х - а)3 = х3 - Зах2 + За2х - а3.

Під х та а можна розуміти будь-яке число, чи будь-який алгебраїчний вираз.

147

Борисенко О.А.

Приклад 3. Знайти розклад виразу (Зх - 2а)5 на основі формули бінома Ньютона.

Розв 'язання.

(Зх - 2а)5 = (Зх)5 - 5 • 2а(3х)4 +10(2а)2 (Зх)3 -10(2а)3(Зх)2 +

+5(2я)4 3х-(2а)5 =243х5 -810ах4 +1080а2х3 -720а3 х2 +240а4 х-32а5 .

Увипадку, якщо а є додатним числом, то

Р = (х + а)" =(х-(-а))" = £ Скпакх"'к. к=0

Приклад 4. Знайти біном Ньютона для виразу (х + а)3, якщо а є додатним числом.

Розв'язання.

(х + а)3 = (х + а)(х + а)(х + а) = хі +3ах2 +За2х + а3.

Приклад 5. Обчислити з допомогою бінома Ньютона вираз (10 +2)3.

Розв'язання.

(10 + 2)3 =103 + 3'2-102 + 3-22 -10 + 23 =1728.

Приклад 6. Обчислити з допомогою бінома Ньютона вираз (10 + 0,1)3.

Розв 'язання.

(10 + 0,1)3 = 103 + 3• 0,1-Ю2 + 3• ОД2 • 10 + 0,13 = 1030,301.

2. Властивості бінома Ньютона Спочатку зазначимо деякі очевидні властивості бінома

Ньютона:

1. Кількість членів розкладу на 1 більше за показник п.

148

Дискретна математика

2.Показники степеня числа х зменшуються, а числа а збільшуються від члена до члена на 1.

3.Сума показників х і а в кожному члені дорівнює п.

Далі доведемо дві важливі властивості біноміальних коефіцієнтів бінома Ньютона у вигляді теорем 2 і 3.

Теорема 2.

£ с * = 2 « . *=о

Доведення. Виходячи з того, що, при х = а - 1, з одного боку,

(х + а)" =(1 + 1)" = 2",

149

Борисенко О.А.

Доданки Скпакхп~к у наведеному вище виразі приймають у випадку, якщо к парне, додатні значення, які дорівнюють С^ , а у випадку, якщо к непарне, від'ємне: - Ск", де к' = 0,2,4,...; к" = 1,3,5,...;

-значення верхнього параметра коефіцієнтів, які стоять на парних місцях, я к " - значення верхнього параметра коефіцієнтів, які стоять на непарних місцях. Тоді

де п - максимальне значення к'; п" - максимальне значення А:".

З одержаної рівності випливає, що

Оскільки з виразу, який наведений вище, виходить, що вказані в ньому суми дорівнюють одна одній, а з теореми 2 при х = а = 1, що

<=0 *'=0 к'=0

то кожна з наведених сум повинна дорівнювати

150

Дискретна математика

3. Історична довідка

Біном Ньютона для цілих додатних значень п знали до Ньютона (1643-1727) ще середньоазіатські математики, зокрема, Омар Хайям (1048-1131), а в Західній Європі - Паскаль (1623-1662). Цей вираз ще називають біноміальною формулою, або біноміальною теоремою.

Заслуга Ньютона полягає в тому, що він вперше узагальнив цю формулу для дробових та від'ємних показників п. Про це відкриття Ісаак Ньютон повідомив у 1676 р., але повноцінного доказу формули розкладу (х - а)" для нецілих та від'ємних п він не мав, хоча саме про це його просив Лейбніц. Доказ Ньютона базувався більше на прикладах і аналогіях, ніж на теорії. У 1774 році цю теорему намагався довести Леонард Зйлер і тільки в 1812 році її довів Карл Фрідріх Гаус з допомогою теорії нескінченних сум.

Як бачимо, розкладення виразу (х + а)", яке носить назву біному Ньютона для цілих, дробових, додатних і від'ємних п, має довгу історію, що свідчить про його велике значення в науці.

Доведення це є творча задача науки

В. Ф. Асмус

151

Борисенко О.А.

КОНТРОЛЬНІ ЗАВДАННЯ 1 ПИТАННЯ ДО ЧАСТИНИ III

Питання для самоконтролю

1.Дайте визначення комбінаторних задач і наведіть їх класифікацію.

2.Сформулюйте правило суми для комбінаторних задач.

3.Сформулюйте правило добутку для комбінаторних задач.

4.Що таке сполучення і біноміальні коефіцієнти?

5.Доведіть формулу для обчислення кількості сполучень к елементів з п.

6. Доведіть, що для п, к * 0 С**1 = С*+1 + С*.

10. Доведіть, що для п, к * 0 С* = —-— С^,.

п-к

И. Як виконується обчислення біноміальних коефіцієнтів з допомогою явних формул?

12.Як виконується обчислення біноміальних коефіцієнтів з допомогою рекурентних формул?

13.Як виконується обчислення біноміальних коефіцієнтів на основі побудови числових послідовностей?

14.Як виконується обчислення біноміальних коефіцієнтів на основі біноміальних квадратів і прямокутників?

15.В чому полягають властивість симетрії для біноміальних коефіцієнтів?

16.В чому полягають властивості додавання для біноміальних коефіцієнтів?

17.В чому полягають властивості винесення за дужки для біноміальних коефіцієнтів?

152