Материал: discrete_mathematics

12.Скільки слів довжиною 5 можна утворити з літер a, b, c,

якщо:

(а) кожна із літер зустрічається у слові без обмежень; (б) літеру a можна використати в слові лише один раз;

(в) літеру a можна використати в слові не більше двох разів?

13.У скількох перестановках літер a, a, a, a, b, b, b, c, c не зустрічається жодне з підслів aaaa, bbb, cc?

14.У скількох перестановках літер a, a, b, b, c, c жодна літера не збігається з літерою, що стоїть на такому самому місці у сло-

ві aabbcc?

3.3.Біном Ньютона та поліномна формула

Має місце рівність

(a + b)n = C(n, 0)an + C(n, 1)an – 1b + C(n, 2)an – 2b2 + … + C(n, n)bn

Щоб переконатись у справедливості цієї рівності, для будь-

ефіцієнтами.

Приклад 3.7.

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).

152

3. Обмежившись двома членами e розкладанні бінома, наближено обчислити (0,997)8.

(0,997)8 = (1 – 0,003)8 = 1 – 8 0,003 = 0, 976. ◄

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

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.

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] + 1.

У справедливості тотожностей 1) і 2) легко переконатися, застосовуючи (3.3).

Тотожність 3) дістанемо, якщо в біномі Ньютона (3.5) покладемо a = b = 1. Вона випливає також із того, що C(n, k) – це кількість k-елементних підмножин множини з n елементів, тому сума в лівій частині тотожності 3) дорівнює кількості всіх підм-

ножин множини з n елементів. За теоремою 1.1 ця кількість дорівнює 2n.

Якщо в біномі Ньютона покласти a = 1 і b = – 1, то дістанемо тотожність 4). Тотожності 5) і 6) можна отримати за допомогою відповідно додавання й віднімання тотожностей 3) та 4).

Тотожність 2) дає змогу обчислювати біномні коефіцієнти для n + 1, виходячи з біномних коефіцієнтів для n. Цю процедуру часто виконують за допомогою трикутної таблиці, яку нази-

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

153

a1k1 a2k2 ...amkm

такі, що ki ≥ 0, i = 1, 2, …, m і k1 + k2 + … + km = n.

Кількість членів типу a1k1 a2k2 ...amkm дорівнює кількості варіан-

тів вибору k1 множників із (3.9) першого типу (із цих множників до одночлену ввійде k1 множників a1), відтак вибору із решти n – k1 множників із (3.9) k2 множників другого типу (із цих множників до одночлену увійде k2 множників a2) і т. д.

Отже, шукана кількість дорівнює кількості розбиттів n множників у добутку (3.9) на m класів, кількість елементів у яких дорівнює відповідно k1, k2, …, km. За (3.4) ця кількість становить

154

n!

Cn(k1, k2, …, km) = k1!k2!... km! .

Для m = 2 тотожність (3.8) перетворюється на біном Ньютона (3.5).

Приклад 3.9.

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. ◄

Завдання для самостійної роботи

1. Знайти розкладання бінома:

(а) (2x – 4)4; (б) (a/2 + 2b)5; (в) (2 – x4)5; (г) (a + 2b)7.

2.Знайти коефіцієнти при x3 та x5 у многочлені x(2 – 3x)5 + x3(1 + 2x2)7 – x2(5 + 3x3)4.

3.Знайти коефіцієнт при xm у розкладанні

(1 + x)k + (1 + x)k + 1 + … + (1 + x)n.

Розглянути випадки m < k і m ≥ k.

4.Обмежившись двома членами у розкладанні бінома, наближено обчислити (2,003)10.

5.Знайти n, коли відомо, що:

(а) у розкладанні (1 + x)n коефіцієнти при x5 та x12 однакові; (б) восьмий член розкладання (2x + 3)n має найбільший кое-

фіцієнт.

6.Розв'язати рівняння відносно натурального k: (а) C(k, k – 3) + C(k, k – 2) = 15(k – 1);

(б) C(k + 1, k – 1) + C(k, k – 2) = 9k + 10; (в) C(k, 3) + C(k, 4) = 11C(k + 1, 2).

7.Розв'язати систему рівнянь відносно натуральних n і m:

155

(а) C(n, m) = C(n, m + 2), C(n, 2) = 153; (б) C(n + 1, m – 1) : C(n + 1, m) = 3 : 5; (в) C(n + 1, m) = C(n + 1, m + 1).

8. Довести тотожність:

(а) C(n, 1) + 6C(n, 2) + 6C(n, 3) = n3;

(б) 1 + 7C(n, 1) + 12C(n, 2) + 6C(n, 3) = (n + 1)3; (в) C(n, 1) + 14C(n, 2) + 36C(n, 3) + 24C(n, 4) = n4;

(г) C(n, 0) + 2C(n, 1) + 22C(n, 2) + … + 2nC(n, n) = 3n; (д) C(n, 1) – 2C(n, 2) + … + (–1)n – 1nC(n, n) = 0.

9. Користуючись поліномною теоремою, обчислити

(x + 2y + 3z)3.

10. Знайти коефіцієнт при xk у розкладі полінома: (а) (1 + x2 + x3)7, k = 11;

(б) (1 + 2x2 – 3x4)10, k = 8.

3.4. Урнова модель. Сполуки із повтореннями

Розглянемо одну важливу й популярну в комбінаториці модель, яку називатимемо урновою моделлю.

Нехай є k урн і n однакових предметів (наприклад куль). Підрахуємо, скількома способами можна розподілити ці предмети по урнах. Для цього розташуємо урни послідовно та занумеруємо їх від 1 до k. Тоді кожному розподілу предметів в урнах можна поставити у відповідність кортеж (m1, m2, …, mk) довжиною k, i-та координата якого дорівнює кількості предметів, що потрапили в урну з номером i. Ця відповідність є, безумовно, взаємно однозначною. Тому шукана кількість розподілів збігається із кількістю таких кортежів. Для підрахунку останньої виконаємо перетворення (теж взаємно однозначне) кортежів. Кортеж (m1, m2, …, mk) замінимо на кортеж із нулів і одиниць за таким правилом. Спочатку запишемо послідовність, що складається з m1 одиниць, за нею запишемо нуль, далі – послідовність із m2 одиниць, знову нуль і т. д. Закінчується кортеж послідовністю з mk одиниць. Кожен отриманий таким способом кортеж складатиметься з n одиниць (оскільки m1 + m2 + … + mk = n) і k – 1 нулів, і множина цих кортежів взаємно однозначно відповідатиме множині розподілів n предметів по k урнах.

156