Борисенко О.А. Дискретна математика
Подождите немного. Документ загружается.
Дискретна математика
п-к. У ній останній її елемент буде мати значення біноміального
коефіцієнта, який визначається.
З вищенаведеного випливає, що для того, щоб обчислити з
допомогою розглянутих вище операцій біноміальний коефіцієнт С
к
п
,
потрібно здійснити такі кроки:
1. Побудувати відповідно до розглянутого вище правила п-к
числових послідовностей, починаючи з послідовності 1, 2,..., к+ 1.
2. В останній (п - &)-й послідовності знайти (к + 1)-е число, яке й
буде значенням біноміального коефіцієнта С*.
Приклад 1. Дано к = 4, п= 10. Треба знайти величину
біноміального коефіцієнта С*
0
.
Рішення. З умови задачі випливає, що п - к = 6. Тому потрібно
збудувати 6 послідовностей, які мають по к + 1 = 5 біноміальних
коефіцієнтів: 1, 2, 3, 4, 5; 1, 3, 6, 10, 15; 1, 4, 10, 20, 35; 1, 5, 15, 35, 70;
1, 6, 21, 56, 126; 1, 7, 28, 84,210. Коефіцієнт С,
4
0
= 210, оскільки
останній елемент послідовності з номером 6 є число 210.
5. Обчислення С* на основі біноміальних квадратів і прямокутників
Біноміальні квадрати можна отримати з трикутника Паскаля.
Щоб отримати біноміальний квадрат, треба повернути трикутник
Паскаля вправо на 45° і доповнити його числами, які отримуються з
допомогою встановлених вже раніше правил для побудови чисел
цього трикутника, до форми квадрата. Побудований таким чином
біноміальний квадрат зображено в табл. 3.2.
143
Борисеико О.А.
Таблиця 3.2. Біноміальний квадрат
9
8 7
6 5 4 3 2
1 0
0 1
1
1
1 1 1
1
1
1 1
1 10 9 8
7 6 5
4
3
2 1
2
55 45
36
28 21 15 10 6
3 1
3 220 165
120
84 56 35 20
10 4 1
4 715
495 330
210 126
70 35
15 5 1
5 2002 1287 792
462
252 126 56 21 6 1
6
5005 3003
1716
924
462 210
84
28 7 1
7 1144 6435 3432 1716
792 330 120 36
8 1
8 2431
1287 6435 3003 1287
495 165 45 9 1
9
4862 2431
1144 5005 2002
715 220 55
10 1
Однією з властивостей цього квадрата є те, що з його
допомогою можна обчислювати будь-які біноміальні коефіцієнти С
к
п
з величинами параметрів к< К і п<К
+
к, де К - максимальне
значення параметра к. Відповідно, кожна сторона біноміального
квадрата має К + 1 стовпчиків і стільки ж рядків.
З метою знаходження величини біноміального коефіцієнта
треба спочатку знайти значення різниці п - к, а потім вибрати
відповідний отриманому значенню рядок. На перетині цього рядка й
стовпчика, який відповідає числу к, буде знаходитись необхідне
число.
Наприклад, треба обчислити біноміальний коефіцієнт з к = 5 і
п = 7. Для цього спочатку обчислюємо різницю л-Л = 7- 5 = 2і потім
знаходимо перетин другого рядка з п'ятим стовпчиком. Там
знаходиться число 21. Це означає, що біноміальний коефіцієнт С
7
5
має
значення 21, що легко перевіряється з допомогою формули для
біноміального коефіцієнта, яка подана в явному вигляді:
144
Дискретна математика
Можна обчислити біноміальний коефіцієнт С
7
5
й інакше.
Будемо виходити з того, що С
7
5
=С
7
2
. ТОДІ п-к
=
7-2
= 5,
і
відповідно отримаємо значення О] =
21
на перетині другого
стовпчика і п'ятого рядка.
ДОСТОЇНСТВОМ біноміального квадрата є те, що обчислення
біноміальних коефіцієнтів з його допомогою не потребує, крім
знаходження різниці п-к, інших арифметичних операцій. Це, у свою
чергу, дозволяє отримати велику швидкодію пристроїв, які
обчислюють величину біноміальних коефіцієнтів.
Якщо продовжити ту чи іншу сторону біноміального квадрата,
то отримаємо біноміальний прямокутник.
Наприклад, у табл. 3.2 збільшимо кількість рядків з 9 до 18. Це
вже буде біноміальний прямокутник. Його особливістю є те, що він
дозволяє знаходити значення С* для параметра п, який змінюється
від 0 до 18.
Кращий спосіб вивчити будь-що - це відкрити самому.
Д. Пойа
145
Борисенко О. А.
Лекція 26
БІНОМ НЬЮТОНА
1. Загальні положення
Біном Ньютона — це досить відома формула в математиці.
Вона подає вираз (х - а)", де п - ціле додатне число, в вигляді
многочленна.
Теорема 1.
(.х-а)
п
= ±(г\)
к
С
к
п
а
к
х
п
-
к
.
А=0
Доведення. Візьмемо добуток п двочленів
Р
=
(х-а
х
)(х-а
2
).Дх-а
н
)
і, якщо розкриємо в ньому дужки та згрупуємо члени з однаковими
показниками степеня, одержимо многочлен, розташований за
значеннями показників степені, які зменшуються
Р-х"
— лг"
-І
(аГ|
+а
2
+...
+
а
п
)
+
х"~
2
{а^а
2
+
а
]
а
3
...
+
а„_,а„)-
-х""
3
(а
1
д
2
а
3
н-
а,а
2
а
4
+...
+
а
п
_
2
а
пА
а„) + ... + (-1 )"{а
х
а
2
...а„).
Неважко побачити, що в дужках виразу, який одержано вище,
приведені всілякі сполучення к = 1, 2, ..., п елементів множини
{а,,й
2
,...,а„} з п, кількість яких дорівнює С*.
У випадку, коли а, = а
2
=...
=
а
п
=
а,
Р
=
(х-а)" =х" -С\ах"~
х
+ С
2
„а
2
х"~
2
-С\а
г
х+...
+
+(-1)
к
С
к
п
а
к
х"-
к
+ ...
+
(-\)"а
п
.
У цій формулі к-й член буде мати вигляд:
Т
к
=(-1 )
к
С
к
а
к
х"-
к
.
146
Дискретна математика
Тоді за умови, що
= (-1)° С°а°х"~° = С°х" - х"
і
7
/
Л\П
п п-п /
ҐУП „п
0 /
л
=(-1) С
п
а х =(-1) С
п
а х =(-1) а ,
Р
=
{х-а)
п
= ±(-\)
к
С
к
п
а
к
х
п
"
к
.
к=0
Теорему доведено.
Як бачимо з бінома Ньютона, кількості сполучень біля кожного
з його членів відіграють важливу роль. Тому ці кількості були названі
біноміальними коефіцієнтами.
Приклад 1. Знайти біном Ньютона для виразу (х - а)
2
.
Розв 'язання. Знайдемо добуток двох двохчленів
(х -
а,
)(х - а
2
) = х
2
- (а,
+
а
2
)х + а
ї
а
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
=10
3
+ 3'2-10
2
+ 3-2
2
-10 + 2
3
=1728.
Приклад 6. Обчислити з допомогою бінома Ньютона вираз
(10 + 0,1)
3
.
Розв 'язання.
(10 + 0,1)
3
= 10
3
+ 3• 0,1-Ю
2
+ 3• ОД
2
• 10
+ 0,1
3
= 1030,301.
2. Властивості бінома Ньютона
Спочатку зазначимо деякі очевидні властивості бінома
Ньютона:
1. Кількість членів розкладу на
1
більше за показник п.
148
Дискретна математика
2. Показники степеня числа х зменшуються, а числа а
збільшуються від члена до члена на 1.
3. Сума показників х і а в кожному члені дорівнює п.
Далі доведемо дві важливі властивості біноміальних
коефіцієнтів бінома Ньютона у вигляді теорем 2 і 3.
Теорема 2.
£с*=2«.
*=о
Доведення. Виходячи з того, що, при х = а - 1, з одного боку,
(х + а)"
=(1
+
1)"
= 2",
а з іншого,
(х
+
аУ = £сУх"~
к
= £сї,
к=0 к=о
то
±С
к
=Г.
к= о
Теорему доведено.
Теорема 3. Сума біноміальних коефіцієнтів бінома
Ньютона, які займають парні місця, дорівнює сумі біноміальних
коефіцієнтів, які займають непарні місця, і кожна з них дорівнює
2
«-і
Доведення. Припустимо, що для бінома Ньютона х = 1 і а = -1.
Тоді
(х
+
а)"
= (1
-1)"
= (0)" =
0,
і оскільки
(х
+
а)
п
= ±С
к
а
к
х"-
к
,
4=0
то і
£с
к
а
к
х"~
к
=0.
і=0
149
Борисенко О. А.
Доданки С
к
п
а
к
х
п
~
к
у наведеному вище виразі приймають у
випадку, якщо к парне, додатні значення, які дорівнюють С^ , а у
випадку, якщо к непарне, від'ємне: - С
к
", де к' = 0,2,4,...; к" = 1,3,5,...;
-значення верхнього параметра коефіцієнтів, які стоять на парних
місцях, як" - значення верхнього параметра коефіцієнтів, які стоять
на непарних місцях. Тоді
£ С
к
а
к
х"-
к
= £
С
к
п
- X С„
г
=
0,
А-0 і'=0 Г=0
де п - максимальне значення к';
п" - максимальне значення
А:".
З одержаної рівності випливає, що
Оскільки з виразу, який наведений вище, виходить, що вказані в
ньому суми дорівнюють одна одній, а з теореми 2 при х
=
а = 1, що
<=0 *'=0 к'=0
то кожна з наведених сум повинна дорівнювати
2
Тобто £ =
к'=0
І
ЕсГ = 2"-'.
Теорему доведено.
150
Дискретна математика
3. Історична довідка
Біном Ньютона для цілих додатних значень п знали до Ньютона
(1643-1727) ще середньоазіатські математики, зокрема, Омар Хайям
(1048-1131), а в Західній Європі - Паскаль (1623-1662). Цей вираз ще
називають біноміальною формулою, або біноміальною теоремою.
Заслуга Ньютона полягає в тому, що він вперше узагальнив цю
формулу для дробових та від'ємних показників п. Про це відкриття
Ісаак Ньютон повідомив у 1676 р., але повноцінного доказу формули
розкладу (х - а)" для нецілих та від'ємних п він не мав, хоча саме про
це його просив Лейбніц. Доказ Ньютона базувався більше на
прикладах і аналогіях, ніж на теорії. У 1774 році цю теорему
намагався довести Леонард Зйлер і тільки в 1812 році її довів Карл
Фрідріх Гаус з допомогою теорії нескінченних сум.
Як бачимо, розкладення виразу (х
+
а)", яке носить назву біному
Ньютона для цілих, дробових, додатних і від'ємних п, має довгу
історію, що свідчить про його велике значення в науці.
Доведення це є творча задача науки
В. Ф. Асмус
151
Борисенко О. А.
КОНТРОЛЬНІ ЗАВДАННЯ 1 ПИТАННЯ ДО ЧАСТИНИ III
Питання для самоконтролю
1. Дайте визначення комбінаторних задач і наведіть їх
класифікацію.
2. Сформулюйте правило суми для комбінаторних задач.
3. Сформулюйте правило добутку для комбінаторних задач.
4. Що таке сполучення і біноміальні коефіцієнти?
5. Доведіть формулу для обчислення кількості сполучень к
елементів з п.
6. Доведіть, що для п, к * 0 С**
1
= С*
+1
+ С*.
п-к
7. Доведіть, що для п, к * 0 С
к
п
= ^ .
(=0
к
8. Доведіть, що для п, к* 0 С* = ^С'
п
_
к+І
,
у
/=о
17
9. Доведіть, що для п, к * 0 С* - — .
к
10. Доведіть, що для п, к * 0 С* = —-— С^,.
п-к
И. Як виконується обчислення біноміальних коефіцієнтів з
допомогою явних формул?
12. Як виконується обчислення біноміальних коефіцієнтів з
допомогою рекурентних формул?
13. Як виконується обчислення біноміальних коефіцієнтів на
основі побудови числових послідовностей?
14. Як виконується обчислення біноміальних коефіцієнтів на
основі біноміальних квадратів і прямокутників?
15. В чому полягають властивість симетрії для біноміальних
коефіцієнтів?
16. В чому полягають властивості додавання для біноміальних
коефіцієнтів?
17. В чому полягають властивості винесення за дужки для
біноміальних коефіцієнтів?
152