- •Розділ 1. Множини та відношення.
- •1.1. Основні поняття теорії множин.
- •1.2. Операції над множинами. Тотожні перетворення множин.
- •1.3. Відношення та відображення.
- •Розділ 2. Елементи комбінаторики.
- •2.1. Місце комбінаторики в математиці. Правила суми та добутку.
- •2.2. Розміщення та сполучення.
- •2.3. Біном н’ютона. Властивості біноміальної формули. Поліноміальна формула.
- •2.5. Композиції та розбиття. Досконалі розбиття.
- •2.4. Формула включень та виключень.
- •2.6. Рекурентні співвідношення.
- •Розділ 3. Основи теорії графів. Деякі алгоритми на графах.
- •3.1. Основні визначення.
- •3.2. Алгоритми. Обходи графів. Побудова ейлеревих та гамільтонових циклів графа.
- •3.3. Пошук найкоротших відстаней та шляхів у зважених графах.
- •3.4. Пошук максимальної течії в мережах. Розрахунки у мережах.
- •Список використаної та рекомендованої літератури
2.3. Біном н’ютона. Властивості біноміальної формули. Поліноміальна формула.
Для дослідження властивостей чисел розглянемо
Твердження
2.5. Для будь-яких
дійсних
і
та натурального
виконується рівність
(2.5).
Доведення. Проведемо доведення методом математичної індукції.
1. Для
маємо
,
тобто база індукції виконується.
2.
Припустимо, що рівність має місце для
,
тобто
(і)
На основі
цього припущення доведемо, що рівність
виконується і для
.
Помножимо обидві частини рівності (і)
на
:
.
Враховуючи
рівність (2.2.2), а також рівності
та
,
остаточно маємо:
,
тобто
.
Таким чином рівність (і) виконується
для
.
На основі принципу математичної індукції
рівність
виконується для будь-якого натурального
.
■
Рівність (2.5) часто називають біномом Н’ютона або біноміальною формулою, а числа біноміальними коефіцієнтами.
Розглянемо основні властивості біноміальної формули.
Кількість всіх членів розкладу бінома Н’ютона на одиницю більша показника степеня бінома.
Сума показників степенів і кожного члена розкладу дорівнює показнику степеня бінома.
Біноміальні коефіцієнти членів розкладу, рівновіддалених від кінців розкладу, рівні між собою (див. 2.2.3), тобто
,
а) Якщо показник степеня бінома є парним числом (
),
то біноміальні коефіцієнти перших
членів розкладу зростають
,
і, за правилом симетрії, біноміальні коефіцієнти останніх членів розкладу зменшуються
.
У цьому
випадку розклад бінома має один найбільший
біноміальний коефіцієнт
.
б) Якщо
показник степеня бінома є непарним
числом (
),
то біноміальні коефіцієнти перших
членів розкладу зростають
,
і, за правилом симетрії, біноміальні коефіцієнти останніх членів розкладу зменшуються
.
У цьому
випадку розклад бінома має два найбільші
біноміальні коефіцієнти
та
,
які є рівними між собою.
Сума біноміальних коефіцієнтів всіх членів розкладу дорівнює
.
Дійсно,
якщо підставити у формулу бінома Н’ютона
,
то одержимо
.
Сума біноміальних коефіцієнтів членів розкладу, які стоять на непарних місцях, дорівнює сумі біноміальних коефіцієнтів, які стоять на парних місцях, і дорівнює
.
Дійсно,
якщо підставити у формулу бінома Н’ютона
та
,
то одержимо
.
Звідси
.
Узагальненням бінома Н’ютона у випадку декількох доданків є так звана поліноміальна формула.
Твердження
2.6. Для будь-яких
дійсних чисел
та натуральних
виконується рівність
(2.6).
Доведення. Проведемо доведення методом математичної індукції за кількістю доданків .
Для
маємо
.
Позначимо
,
,
тоді
та
,
тобто формула 2.6 виконується при .
Припустимо, що формула виконується для доданків. На основі цього припущення доведемо, що вона вірна і для
доданків. Для цього розглянемо вираз
і позначимо через
суму
.
Тоді
.
Позначимо
.
Тоді враховуючи, що
,
одержимо
та
.
Таким
чином рівність виконується для
.
На основі принципу математичної індукції
рівність 2.6 виконується для будь-якого
натурального
.
■
За допомогою поліноміальної формули можна швидко обчислювати частини великих виразів.
Приклад
2.2. Знайти коефіцієнт
при
в розкладі поліному
.
За поліноміальною
формулою виконується рівність
.
Для розв’язку задачі достатньо знайти
всі трійки значень
,
які після підстановки у поліноміальна
формулу дадуть
.
Оскільки всі степені
є невід’ємними, то
може приймати лише значення 0, 1, 2 (
і в цьому випадку
з поліноміальної формули одержати
неможливо). Далі, якщо це можливо, так
підбираємо значення
,
щоб
(з третього доданку поліному неможливо
одержати
у будь-якому степені). Якщо конфігурація
з
та
,
що дає
існує, то використовуючи рівність
легко знайти відповідне значення
.
Запишемо всі знайдені конфігурації у
вигляді таблиці.
|
|
|
0 |
6 |
15 |
2 |
1 |
18 |
Після
підстановки до поліноміальної формули
знайдені числа одержимо, що шуканий
коефіцієнт дорівнює
.
■
