Загальні правила комбінаторики

Комбінаторика має справу із скінченими множинами і виникла як одна із теорій ігор.

Правило сум

Розглянемо потужність об’єднання двох множин

Якщо А і В є підмножинами множини С. так що

при чому , тобто кожен із об’єктів входить лише в одну множину. Тоді

Формуліровка:

Якщо деякий об’єкт х А можна вибрати “n” способами, а другий об’єкт у В можна вибрати “m” способами то об’єкт або “x” або “у” можна вибрати m + n способами (якщо переріз множин .)

Правило сум може бути застосовано і для більшої ніж 2 кількості множин.

Правило добутку

Нехай нам необхідно розрахувати кількість пар (а в ) таких що а А; b В при чому |A| = n; |B| = m і елемент “в” вибирається після того, як вибрано елемент “а”.

Якщо тоді з очевидністю і т.д. ця кількість буде

Формуліровка:

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

У деяких випадках необхідно обчислити число всеможливих способів вибрати впорядковані вибірки де і т.д. . Якщо потужність множин …, то загальна кількість можливих варіантів здійснення вибірки буде

Розміщення.

Приклад 1. Колесо велосипедиста після падіння має вигляд 8. Оскільки хазяїн Клубу – велосипедист, то здійснюється нову нумерація усіх квитків так, щоб число 8 у них не входило. Відомо, що число членів клубу тризначне число (як виявилось). Скільки членів клубу? Якщо допускається номер 0.0.0. (Розв’язок

Приклад 2: Система числення

В «n» – мірні системі числення використовується “n” чисел.

Скільки можна записати чисел, які записується “К” знаками.

. Використання тільки “n” чисел для кодування інформації приводить до так званих рівномірних кодів.

Одним з прикладів не рівномірного коду є Код Морзе. У ньому використовуються всього 2 символи: крапка та тире.

Однак довжина кодового слова різна.

Приклад 3 Яке найменше число знаків “∙” чи “–” повинна містити комбінація, щоб можна було передати довільну букву при використанні рівномірного коду? Виявляється, що 5. Чому?

Одно позиційне число дає можливість передати лише 2 різні сигнали.

Двох позиційні - “4”. 3^х позиційні - “8”. 4^х позиційні “16”, це менше ніж вміст алфавіту української мови (30).

Тому телеграфний код, код Бодо, містить 5^ти - символьне слово – код, для передачі тексту.

Аналогічно можна розглянути спосіб обчислення об’єму алфавіту кодів для морського семафору, що містить комбінації- таких варіантів кодів цілком достатньо для передачі усіх букв. (Усіх 33.)

Приклад 4. Генетичний код.

Наслідкова інформація записується з допомогою різних порядків азотистих основ: аденін, тіамін, гуанін, цітазин. Ці основи встановлюють порядок будови білків організму із амінокислот, яких кількість порядку 20. Причому кожна амінокислота кодується з допомогою 3х чисел. Чому?

не досить для побудови усіх необхідних білків.

досить з надлишком для створення усіх білків.

Як же природа використовує даний надлишок коду невідомо?

Розміщення, перестановки і сполуки без повторень.

З допомогою загальних правил комбінаторики можна розв’язувати різні задачі, при цьому виникають строго певні комбінації, яким присвоєно імена: розміщення, перестановки сполучення (комбінації).

Означення.

Скінчена множина називається впорядкованою, якщо кожному її елементу ставиться у відповідність натуральне число “к”, яке означає порядковий номер елементу в множині А де де . Якщо порядок елементів неістотній, то множина називається невпорядкованою.

Розглянемо підмножини , які утворюються за слідуючим правилом:

1) Перший крок вибираємо будь-який елемент ; із множини А

2) Із множини вибираємо

3) Із множини вибираємо

4) Із множини вибираємо

Із вибраних елементів складаємо

- це буде вибірка без повторень, вона впорядкована, якщо кожному вибраному елементу множини поставити у відповідність номер. Отримали впорядковану k вибірку без повторів. А якщо елементам множини не присвоювати номери, то отримана вибірка буде невпорядкованою, тобто невпорядкована “k” вибірка без повторів.

Позначається вибірка .

Якщо ж вибірку елементів брати з повної множини A весь час, то частина елементів буде повторюватись і стане “k” вибіркою з повторенням. Природньо, що отримана вибірка може бути як впорядкованою так і невпорядкованою.

Приклад з білетами, коли білет вибраний студентом вилучається (реалізується вибірка без повторів) і коли не вилучається – вибірка з повторами.

Означення 2. Розміщення з “n” по “к” називається впорядкована “к” вибірка без повторення із множини А, для якої . Загальна кількість різних розміщень позначається .

Доведення. Переконаємось (див. кодіровку без повторень) в вірності співвідношення приведеного співвідношення.

На першому місці можна встановити один із “n” елементів множини, на другому – один із “n-1 “ елементів, що залишились.

Тому, очевидно, що - згідно правила добутку. Даний вираз можна переписати у вигляді

де ; , зручному для користування.

Означення 3. “ n” перестановкою називається впорядкована n-мірна вибірка без повторень із множини А, причому . Позначається загальна кількість різних вибірок .Ясно, що будь-які n -перестановки відрізняються лише порядком елементів, і кожна вибірка містить усі елементи множини А.