53. 2. Комбінаторні конфігурації. Біноміальна та поліноміальна теореми.

На практиці зустрічаються задачі, в яких необхідно підрахувати число всеможливих способів розміщення деяких предметів скінченої множини або число всіх можливих способів виконання певної дії, маючи в арсеналі скінчену множину таких дій. Оскільки при розв’язанні задачі доводиться комбінувати з наборами предметів чи методів, то задачі такого типу називають комбінаторними, а методи їх розв'яз­ку – методами ком­бінаторного аналізу.

Більшість комбінаторних задач можна розв’язати, використовуючи на­ступні правила:

Правило суми. Якщо об’єкт А можна вибрати m способами, а інший об’єкт В – іншими n способами, то вибір або А, або В можна здійснити m+n способами.

Правило добутку. Якщо об’єкт А можна вибрати m способами і після кожної такої вибірки об’єкт В можна вибрати n способами, то вибір пари об’єктів А і В в заданому порядку можна здійснити mn способами.

Правила суми та добутку, в якійсь мірі, є в якійсь мірі універсальними при розв’язанні комбінаторних задач. Разом з тим ряд задач зводиться до часткових випадків, де використовують формули обчислення, які відразу дають розв’язок задачі. Такими частковими випадками є розміщення, перестановки та комбінації.

Означення 1. Розміщенням з n по k елементів з повторенням називається будь-яка впорядкована k‑елементна підмножина n-елементної множини, елементи якої можуть повторюватись.

Число всіх розміщень з повторенням з n по k елементів позначають і обчислюють за формулою = n^k. Наприклад, кількість різних трицифрових чисел, які складаються лише з непарних цифр, обчислюється за формулою =5³=125.

Означення 2. Розміщенням з n по k елементів без повторень називається будь-яка впорядкована k‑елементна підмножина n-елементної множини.

Число всіх розміщень з n по k елементів позначають і обчислюють за формулою = n(n—1)(n—2)...(n—k+1). Наприклад, число різних варіантів прогнозування переможців турніру серед десяти учасників (1-ше, 2-ге та 3-тє місця) обчислюється за формулою: 10  9  8 =720.

Означення 3. Упорядковані множини, які відрізняються одна від одної ли­ше поряд­ком своїх елементів (тобто можуть бути одержані з од­нієї і тієї ж множини перестановкою своїх елементів), на­зиваються перестановками. Очевидно, що перестановка – це розміщення з n по n елементів.

Число всіх перестановок n-елементної множини позначають Р_n і обчислюють за формулою Р_n = n!.

Цю формулу отримуємо з формули розміщень:

Р_n = = n(n–1)(n–2)...(n–n+1) = 12...n = n!.

Згідно цієї формули п’ятеро гостей за столом можна розмістити 5! = 120 способами.

Існують задачі на перестановки, в яких всі елементи множини розрізняються між собою та задачі, в яких можна виділити набори (кортежі), в яких деякі елементи співпадають. Наприклад, повторюються окремі літери в слові “мама”, цифри в числі 122 і т.д. Такі задачі називають задачами на перестановки з повтореннями.

При обчисленні перестановок з повторенням елементи, що співпадають, групують по типах. Тоді число різних перестановок, які можна утворити з n елементів, серед яких є k₁ елементів першого типу, k₂ елементів другого типу, ..., k_m елементів m-го типу, дорівнює Р_n(k₁,k₂,...,k_m)= . Якщо елемент не повторюється, то відповідний кортеж складається лише з одного елементу.

Отже, переставляючи літери в слові “мама”, можна утворити = 6 різних слів, чисел, переставляючи цифри в числі 122, можна одержати = 3.

Означення 4. Комбінацією без повторень з n по k елементів називається будь-яка k-елементна підмножина n-елементної множини.

Комбінації відрізняються від розміщення лише тим, що відсутня умова впорядкованості підмножини. Число всіх комбінацій з n по k елементів позначають і обчислюють за формулою: .

Мають місце рівності та , які часто використовують на практиці.

Означення 5. Комбінацією з повтореннями з n по k елементів називається будь-яка k-елементна підмножина n-елементної множини, елементи якої можуть повторюватись.

Число всіх комбінацій з повторенням з n по k елементів позначають і має місце формула .

Так, утворити букет з 5-ти квіток трьох сортів можна .

Біноміальна теорема. Для будь-якого натурального числа n має місце формула (a+b)ⁿ= aⁿb⁰+ a^n–1b¹+ a^n–2b²+…+ a⁰bⁿ.

Доведення. Доведення проведемо методом математичної індукції.

1) При n=1 маємо:

2) Припустимо, що формула справедлива для деякого натурального числа k, тобто, що має місце рівність (a+b)^k= a^kb⁰+ a^k–1b¹+ a^k–2b²+…+ a⁰b^k.

3) Доведемо справедливість формули для числа k +1.

(a+b)^k+1=(a+b)^k(a+b)=( a^kb⁰+ a^k–1b¹+ a^k–2b²+…+ a⁰b^k )(a+b)=

= a^k+1b⁰+ a^kb¹+ a^k–1b²+…+ a¹b^k +

+ a^kb¹+ a^k–1b²+ a^k–2b³+…+ a⁰b^k+1 =

= a^k+1b⁰+( + )a^kb¹+( + )a^k–1b²+…+ a⁰b^k+1=

= a^k+1b⁰+ a^kb¹+ a^k–1b²+…+ a¹b^k .

Тоді в силу методу математичної індукції теорема має місце для всіх натуральних чисел n.

Теорема доведена.

Наступна теорема є узагальненням біному Ньютона і дає від­повідь на те, як розкривати дужки при обчисленні виразу виду (a₁ + a₂ + ... + a_k)ⁿ.

Поліноміальна теорема. Вираз (a₁ + a₂ + ... + a_k)ⁿ дорівнює сумі всіх можливих доданків виду , де , тобто

(a₁ + a₂ + ... + a_k)ⁿ =

Доведення. Перемножимо послідовно суму a₁ + a₂ + ... + a_k на себе n раз. Тоді одержимо kⁿ доданків виду d₁d₂…d_n, де кожен множник d_i дорівнює або a₁, або a₂ ,…, або a_k. Позначимо через B(r₁, r₂,…, r_k) сукупність всіх тих доданків, де a₁ зустрічається множником r₁ раз, a₂ – r₂ раз,…, a_k – r_k раз. Число таких доданків дорівнює P_n(r₁, r₂,…, r_k). Відомо, що P_n(r₁, r₂,…, r_k) = .

Отже, (a₁ + a₂ + ... + a_k)ⁿ = Теорема доведена.

Білет 28