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

Впорядкована множина

• Множина, кожному елементу якої поставлений у відповідність певний номер називається впорядкованою.
• Будь-яку впорядковану множину, що містить більше одного елемента можна впорядкувати декількома способами.
• Впорядковані множини вважаються різними, якщо вони складаються з різних елементів або мають різний порядок одних і тих же елементів.
• Різні впорядковані множини, що відрізняються лише порядком елементів (тобто можуть бути отримані з однієї множини) називаються перестановками цієї множини.

Задача 1

Скількома різними способами можна розставити 3 різнокольорових кубики?

1

2

3

4

5

6

• Розділ математики, який досліджує можливі способи утворення різних підмножин з елементів деякої множини за певних умов, називається комбінаторикою.

• Задачі, в яких потрібно знайти кількість можливих способів утворення таких підмножин, називаються комбінаторними.

Для розв’язування комбінаторних задач доцільно

використовувати таблиці або будувати «дерево».

Наприклад:

Скільки натуральних трицифрових чисел �можна скласти з цифр 1, 2, 3, �використовуючи в запису числа �кожну з них не більше одного разу?

Складемо таблицю

1

2

3

4

5

6

Розглянемо розв’язування даної задачі побудовою

«дерева» варіантів

1

1

1

1

1

2

2

2

2

2

3

3

3

3

3

Отже, всього 3∙2∙1 = 3! = 6

В основі розв’язування багатьох комбінаторних задач лежать два основних правила – правило суми і правило добутку.

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

Правило суми: якщо доводиться вибирати або перший елемент, або другий, або третій і т. д. елемент, кількості способів вибору кожного елемента додають.

Правило добутку: коли доводиться вибирати набір у який входить і один, і другий, і третій, і т. д. елемент, кількості способів вибору перемножають.

Перестановки множини А (позначається P_n) – це множини, що складаються з тих самих елементів, що й А, але розставлених у різному порядку.

P_n=n! =1∙2∙3∙…∙n=n∙(n-1)∙(n-2)∙…∙1)

​

Перестановки

Будь-яка впорядкована підмножина з k елементів даної n-елементної множини називається розміщенням з n елементів по k.

Розміщення

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

n - елементної множини.

Комбінації

Потренуйтеся працювати з комбінаторними формулами:

1. Обчислити:

4

6

20

4

5

3

2

2. Розв'язати рівняння:

2

2

2

3

Вибір формули у задачах

Чи враховується порядок?

(Чи є множина впорядкованою?)

Усі елементи приймають участь?

Так

Ні

Так

Ні

Успіхів!