4.4. Деякі комбінаторні тотожності

Під час розв’язування комбінаторних задач часто використовуються різні комбінаторні тотожності. Наведемо окремі з тих, у яких задіяні кількості комбінацій:

1) ;

2) ;

3) ;

4) ;

5)

Довести ці тотожності можна, спираючись на формулу для числа або на інші міркування. Зокрема, тотожність 2) випливає з теореми 3. Справді,

А можна міркувати й так. Кожній k-елементній підмножиніn-елементної множини відповідає(n – k)-елементна підмножина, до якої входять ті n – k елементів, що залишилися. Тому числу різних k-елементних комбінацій, а їх буде відповідає стільки ж різних (n – k)-елементних комбінацій, а їх буде Отже,

Доведемо тотожність 4) методом математичної індукції. ЇЇ можна прочитати так: «Кількість усіх підмножин n-елементної множини дорівнює 2ⁿ».

При n1 це твердження істинне, оскільки одноелементна множина має лише дві підмножини — порожню множинута саму задану множину. Двоелементна множинаМ{а,b} має чотири підмножини:, {a}, {b} та {а,b}. Це узгоджується з тим, що

Припустимо, що кожна множина з k елементів має 2^k підмножин. Приєднаємо до цієї множини ще один елемент x і одержимо (k + 1)-елементну множину. Відберемо всі ті підмножини, до яких не входить елемент x. Їх, відповідно до припущення, буде 2^k. Приєднаємо до кожної із цих підмножин елемент x. Дістанемо ще 2^k різних підмножин. Тому кількість усіх підмножин (k + 1)-елементної множини дорівнює 2^k + 2^k  2  2^k  2^{k +1}. Тотожність 4) доведено.

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

Розглянемо кілька прикладів.

Приклад 1.Довести тотожність

■

■

Приклад 2.Спростити вираз

■ Спочатку спростимо кожний доданок даної суми:

Тоді ■

Приклад 3.Розв’язати рівняння

■Спростимо вираз у лівій частині рівняння:

Рівняння x(х+ 1)30 має два кореніх₁– 6,х₂5. Зі змісту задачі зрозуміло, щохмає бути натуральним числом, причому наявність у рівнянні виразунакладає на невідоме ще одне обмеження:Отже,x5 — єдиний корінь заданого рівняння. ■

§5. Сполуки з повторенням елементів

Розглядаючи задачу про те, скільки різних буквосполучень можна дістати, переставляючи букви слова ранок, легко отримати відповідь: їх будеР₅120. Якщо аналогічне запитання поставити стосовно словаматематика,то ситуація зміниться, бо в цьому слові букваазустрічається 3 рази, і по два рази зустрічаються буквиміт. Для проведення підрахунку різних буквосполучень у цьому разі, уявімо собі, що всі букви даного слова різні за написом. Нехай, наприклад, букви, що повторюються, записані з індексами:м₁а₁т₁е₁м₂а₂т₂ика₃. Тоді кількість можливих буквосполучень, одержаних перестановкою усіх цих букв, дорівнюватиме 10!. Серед них для кожного конкретного розміщення буквм₁,м₂,т₁,т₂,е,и,кматимемо по 3!6 таких буквосполучень, у яких міняються місцями лише буквиa₁,а₂,а₃. Зрозуміло, що в традиційному написанні (без індексів) ці буквосполучення тотожні між собою. Так само, для кожного конкретного розміщення буква₁,а₂,а₃,т₁,т₂,е,и,кматимемо по 2!2 буквосполучення, у яких міняються місцями лише буквим₁ім₂. Аналогічний висновок справджується і стосовно буквт₂,т₁. Тому, згідно з правилом множення, при кожному фіксованому розміщенні букве,и,кматимемо по 322буквосполучень, які відрізняються між собою лише відповідною перестановкою буква₁,а₂,а₃;т₁,т₂;м₁,м₂і які, отже, ідентичні у традиційному написанні. Отже, якщо черезРпозначимо кількість усіх насправді різних перестановок букв у словіматематика, то, згідно з тим самим правилом множення, матимемо:Р(3!2!2!)10!. Звідси