Комбінаторний аналіз

1.

Комбінаторний аналіз
1. Деякі властивості трикутника Паскаля. Біноміальна
формула
2. Задачі про розміщення предметів
3. Поліноміальна формула
4. Комбінаторні задачі і теорія чисел

2.

1. Деякі властивості трикутника Паскаля
Зі школи пам'ятаємо трикутну таблицю
1
1 1
1 2 1
1 3 3 1
1 4 6
4 1
. . . . . . . . . . . .

3.

яку називають трикутником Паскаля:
1
n=0
1 1
n=1
1 2 1
n=2
1 3 3 1
n=3
1 4 6 4 1
n=4
1 5 10 10 5 1
n=5
……………… ……
У n-му рядку трикутника Паскаля стоять біномні
коефіцієнти

4.

У n-му рядку трикутника Паскаля стоять біномні коефіцієнти розкладу
(a + b)n, причому кожний коефіцієнт (окрім крайніх двох, які дорівнюють 1)
дорівнює сумі двох відповідних коефіцієнтів з попереднього рядка.
Формулу
а в
n
C ( n ,0 )a n C ( n ,1 )a n 1b C ( n ,2 )a n 2b 2 ... C ( n , n )b n
називають біномом Ньютона, відповідне твердження – біномною теоремою, а
числа C(n, k) – біномними коефіцієнтами.

5.

Щоб переконатись у справедливості цієї рівності, для будь-яких
чисел a, b і n розглянемо добуток
(a + b)(a + b)(a + b)…(a + b) (n множників).
Розкриваючи дужки, отримаємо суму двочленів вигляду akbn – k.
Причому двочлен akbn – k дістанемо тоді й тільки тоді, коли із k
співмножників у добутку оберемо доданок a, а з решти n – k
множників – доданок b. Цей вибір можна здійснити C(n, k)
способами.
Отже, двочлен akbn – k входить до розкладання виразу C(n, k)
разів, що й доводить справедливість формули.

6.

Приклади.
1. Знайти розкладання бінома (1 – x3)5.
1 – 5x3 + 10x6 – 10x9 + 5x12 – x15.
2. Знайти коефіцієнти при x3 та x5 у многочлені
(1 + x)3 + (1 + x)4 + (1 + x)5 + … + (1 + x)15.
Коефіцієнт при x3 дорівнює C(3, 3) + C(4, 3) + ... + C(15, 3), а
при x5 дорівнює C(5, 5) + C(6, 5) + ... + C(15, 5).

7.

3. Обмежившись двома членами в розкладанні бінома, наближено
обчислити (0,997)8.
(0,997)8 = (1 – 0,003)8 = 1 – 8⋅0,003 = 0, 976.
• Наведемо деякі важливі співвідношення для біномних
коефіцієнтів, які називають біномними тотожностями.

8.

• 1) C(n, k) = C(n, n – k);
• 2) C(n, k + 1) = C(n, k) + C(n, k – 1);
• 3) C(n, 0) + C(n, 1) + C(n, 2) + … + C(n, n – 1) + C(n, n) = 2n;
• 4) C(n, 0) – C(n, 1) + C(n, 2) – … + (–1)nC(n, n) = 0;
• 5) C(n, 0) + C(n, 2) + C(n, 4) + … + C(n, k) = 2n – 1, де k = 2[n/2];
• 6) C(n, 1) + C(n, 3) + C(n, 5) + … + C(n, m) = 2n – 1, де m = 2[(n – 1)/2].

9.

Ще кілька властивостей наведемо без доведення:
C C
... C
C
7.
С
8.
Сnn Cnn 1 Cnn 2 ... Cnn m 1 Cnn m1
0
n 1
1
n
2
n 1
m
n m 1
m
n m
Звідси :
m( m 1 )
2
1 2 3 ... m
Сm 1
2
m( m 1 )( 2m 1 )
2
2
2
2
1 2 3 ... m
6
13 23 33 ... m3
m 2 ( m 1 )2
4

10.

* ( С ) ( C ) ... ( C ) C
0
n
*
2
1
n
2
n
n
m k
n k
C C
С C
k
n
k
m
2
n
2n
m
n

11.

Приклади.
1. Знайти n, коли відомо, що: у розкладанні (1 + x)n
коефіцієнти при x4 та x10 однакові:
*Маємо C(n, 4) = C(n, 10). Звідси, скориставшись
тотожністю, дістанемо n = 14.*
2.Розв'язати рівняння C(k + 3, k + 1) = C(k + 1, k – 1) + C(k, k
– 2) + C(k + 1, k) відносно натурального k.
*Скориставшись (*), отримаємо рівносильне рівняння
(k + 3)(k + 2) = (k + 1)k + k(k – 1) + 2(k + 1).
Коренями останнього будуть числа 4 та –1. Отже, k = 4.*

12.

3. Довести тотожність C(n, 1) + 2C(n, 2) +…+ nC(n, n) = n2n – 1.
Використавши рівність kC(n, k) = nC(n – 1, k – 1),
перетворимо ліву частину до вигляду
nC(n – 1, 0) + nC(n – 1, 1) + … + nC(n – 1, n – 1)
і застосуємо тотожність 3.

13.

2. Задачі про розміщення предметів

14.

15.

16.

17.

18.

3. Поліноміальна формула

19.

Приклади.
1.Користуючись поліномною формулою, обчислити (x + y + z)3.
• x3 + y3 + z3 + 3x2y + 3x2z + 3xy2 + 3y2z + 3xz2 + 3yz2 + 6xyz. *
2. Знайти коефіцієнт при x8 у розкладанні полінома (1 + x2 – x3)9.
* Довільний член розкладання полінома має вигляд
* C9(k1, k2, k3)1k1(x2)k2(–x3)k3 = C9(k1, k2, k3)(–1)k3x2k2+3k3,
де k1, k2, k3 – невід'ємні цілі числа, а k1 + k2 + k3 = 9.
Потрібно знайти ті з них, для яких виконується 2k2 + 3k3 = 8.
Ці умови задовольняють тільки дві трійки чисел: k1 = 5, k2 = 4, k3 = 0 і
k1 = 6, k2 = 1, k3 = 2. Отже, шуканий коефіцієнт
C9(5, 4, 0)(–1)0+ C9(6, 1, 2)(–1)2 = C9(5, 4, 0) + C9(6, 1, 2) = 378. *

20.

4. Комбінаторні задачі і теорія чисел