Материал: discrete_mathematics

них – m + n. У слові w існує n + m + 1 позицій, на які можна записувати по одному символу c, щоб вони не опинились поруч. Це можна зробити C(n + m + 1, k) способами. Отже, шукана кількість – C(n + m + 1, k)(n + m)!/(n!m!). ◄

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

1.Скількома способами можна розподілити k екзаменаційних білетів між n студентами?

2.Скількома способами з 6 інженерів і 14 робітників можна створити бригаду, яка складалася б із 2 інженерів і 5 робітників?

3.Визначити, скількома способами можна вибрати з натуральних чисел від 1 до 100 три натуральні числа так, щоб їх сума:

(а) була непарною; (б) ділилася на три.

4.Скількома способами можна вибрати з n чоловік групу людей для роботи, якщо група має складатися не менше ніж із p чоловік?

5.Скільки є перестановок цифр 0, 1, 2, …, 9, у яких цифра 2 займає друге місце, а цифра 5 – п'яте або шосте?

6.Скількома способами можна посадити за круглий стіл n чоловіків і m жінок так, щоб жодні дві жінки не сиділи поруч?

7.Скількома способами можна роздати 28 кісток доміно чотирьом гравцям так, щоб кожний одержав 7 кісток?

8.Нехай дано n символів a, m символів b. Визначити кількість різних слів,

(а) які можна скласти зі всіх цих символів; (б) які складаються зі всіх цих символів і у яких жодні два

символи b не стоять поруч.

9.Скільки різних слів можна утворити, переставляючи літери

вслові?

10.Скількома способами можна переставити літери слова кавоварка так, щоб голосні та приголосні чергувалися? Розв'язати ту саму задачу для слова палеонтолог.

11.Визначити, скількома способами можна переставити літери наведеного слова так, щоб приголосні йшли за абеткою:

(а) абракадабра; (б) монолог; (в) амальгама.

151

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