Елементи комбінаторики.

Тема 1. Перестановки, розміщення, сполучення без повторень. Теоретичні відомості

Правило суми. Якщо множина М – це об’єднання множин М₁, М₂, М₃,...,М_k, які не перетинаються попарно, тоді кількість елементів множини зв’язані співвідношенням , де - кількість елементів множини М.

Нехай предмет можна обрати способами, предмет - способами, ..., предмет - способами. Тоді вибір предмета або ,..., або може бути зроблений способами.

Приклад 1. З міста А у місто В вирушають 3 потяги, 2 літаки і 1 автобус. Скількома способами можна дістатися з А в В?

За правилами суми всього існує 3+2+1=6 способів.

Правило добутку. Якщо М₁, М₂, М₃,...,М_k – скінчені множини і – їх декартів добуток, то .

Нехай предмет можна обрати способами, предмет - способами, ..., предмет - способами і нехай вибір предмета не впливає на кількість способів вибору предметів , ,..., ; вибір предмета не впливає на кількість способів вибору предметів , ,..., тощо. Тоді вибір упорядкованої множини предметів ( , ,..., ) у вказаному порядку можна здійснити способами.

Приклад 2. В групі 13 хлопців та 12 дівчат. Скільки танцювальних пар вони можуть утворити?

Розв’язання:

Спочатку оберемо, наприклад, парубка – це можна зробити 13 способами, кожному з цих 13 хлопців партнершу можна обрати 12 способами. Зрозуміло, шо пару (хлопець, дівчина) можна обрати 13·12=156 способами.

Зауваження. Якщо нам треба побудувати множину з n символів, кожен з яких вибирається з можливих m символів незалежно один від одного, то кількість упорядкованох множин з n символів буде дорівнювати .

Приклад 3. Скільки різних символів з трьох знаків можна записати кодом Морзе ( )?

Розв’язання:

Перший символ можна вибрати двома способами, другий – теж двома способами і третій – теж двома. За правилом добутку різних символів можна одержати способами (символи в коді можуть повторюватись). Наприклад (---).

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

Нехай М=( ) – фіксована множина.

Визначення. Упорядковані підмножини з елементів ( ) множини М називаються перестановками елементів або розміщеннями з елементів по .

Позначається кількість розміщень з елементів по : (читається А з по ). За правилом добутку або

.

Приклад 4.

Множина Е складаеться з 10 перших літер українського алфавіту. З них обирається 4 літери, які не повертаються, та записується слово. Скільки слів з 4 літер можно скласти в результаті даного випробування? Скільки з цих слів будуть закінчуватись літерою а?

Розв’язання:

Кількість всіх слів з 4 літер в даному випробуванні – дорівнює кількості упорядкованих множин з 4 елементів, вибраних з 10 елементів, тобто

=10∙9∙8∙7=5040.

Нехай випадковим чином складене з 4 літер множини Е слово закінчується літерою а. Кількість таких слів дорівнює кількості способів розмістити на три місця, що залишилися по одному символу з 9 (символ а не розглядаеться, так як його місце вже зайнято); таким чином,

Якщо у перестановці беруть участь всі елементи множини ( -перестановка), то використовують термін перестановка. Кількість перестановок позначають .

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

Приклад 5.

10 варіантів контрольної роботи, які написані на окремих карточах, викладач випадковим чином роздає завдання 10 студентам, кожному по одному варіанту. Скільки існує способів роздати ці картки?

Розв’язання:

Кількість всіх способів роздати 10 карток в даному випробуванні – дорівнює кількості упорядкованих множин з 10 елементів, тобто