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

Август 20, 2022

Главная
Математика
Комбінаторний аналіз

Содержание

2. 1. Деякі властивості трикутника Паскаля Зі школи пам'ятаємо трикутну таблицю 1 1 1 2 1 1
3. яку називають трикутником Паскаля: 1 n = 0 1 1 n = 1 1 2 1
4. У n-му рядку трикутника Паскаля стоять біномні коефіцієнти розкладу (a + b)n, причому кожний коефіцієнт (окрім
5. Щоб переконатись у справедливості цієї рівності, для будь-яких чисел a, b і n розглянемо добуток (a
6. Приклади. 1. Знайти розкладання бінома (1 – x3)5. 1 – 5x3 + 10x6 – 10x9 +
7. 3. Обмежившись двома членами в розкладанні бінома, наближено обчислити (0,997)8. (0,997)8 = (1 – 0,003)8 =
8. 1) C(n, k) = C(n, n – k); 2) C(n, k + 1) = C(n, k)
9. Ще кілька властивостей наведемо без доведення: Звідси :
11. Приклади. 1. Знайти n, коли відомо, що: у розкладанні (1 + x)n коефіцієнти при x4 та
12. Довести тотожність C(n, 1) + 2C(n, 2) +…+ nC(n, n) = n2n – 1. Використавши рівність
13. 2. Задачі про розміщення предметів
18. 3. Поліноміальна формула
19. Приклади. 1.Користуючись поліномною формулою, обчислити (x + y + z)3. x3 + y3 + z3 +
20. 4. Комбінаторні задачі і теорія чисел
37. Скачать презентацию

Слайд 2

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)
дорівнює сумі двох відповідних коефіцієнтів з попереднього рядка.
Формулу
називають біномом Ньютона, відповідне твердження – біномною теоремою, а числа 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

Ще кілька властивостей наведемо без доведення:
Звідси :

Слайд 10

Слайд 11

Приклади.
1. Знайти n, коли відомо, що: у розкладанні (1 + x)n

коефіцієнти при x4 та x10 однакові:
*Маємо C(n, 4) = C(n, 10). Звідси, скориставшись тотожністю, дістанемо n = 14.*
Розв'язати рівняння 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

Довести тотожність 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