3Охаректиризувати основні принципи комбінаторики

Двома основними правилами комбінаторики є: Принцип суми. Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то А і B містить m+n елементів. Принцип добутку. Якщо множина A містить m елементів, а множина B – n елементів, то A і B містить m на n елементів, тобто пар. Кількість елементів множини A будемо далі позначати |A|.  Ці правила мають також вигляд: Принцип суми. Якщо об'єкт A можна вибрати m способами, а об'єкт B – n іншими способами, то вибір "або A, або B" можна здійснити m+n способами. Принцип добутку. Якщо об'єкт A можна вибрати m способами і після кожного такого вибору об'єкт B може бути вибраним n способами, то вибір "A і B" в указаному порядку можна здійснити m на n способами. Наведені правила очевидним чином узагальнюються на випадки довільних скінченних об'єднань множин, що попарно не перетинаються, та на скінченні декартові добутки. Правило добутку застосовується для підрахунку кількості об'єктів, що розглядаються як елементи декартових добутків відповідних множин. Отже, ці об'єкти являють собою скінченні послідовності – пари, трійки тощо. Нагадаємо, що з точки зору математики послідовність довжини m елементів множини A – це функція, яка натуральним числам 1, 2, …, m ставить у відповідність елементи з A.

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

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

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

Дві впорядковані множини називаються рівними, якщо вони складаються з тих самих елементів і однаково впорядковані. З цього випливає, що множини (а, b, с) і (b, с, а) - це різні впорядковані множини.

Означення. Будь-яка впорядкована множина, що складається з п елементів, називається перестановкою з п елементів.

Перестановки з п елементів складаються з одних і тих самих елементів, а відрізняються одна від одної лише порядком.

3. Розміщення

Нехай деяка множина складається з п різних елементів.

Означення. Розміщеннями з п елементів по k називаються підмножини, що мають k елементів, вибраних з даних п елементів і розміщених у певному порядку (k<п).

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

Сполучення

4Охарактеризувати упорядковані множини

Впорядко́вана множина́ — множина для будь-яких двох елементів  ,   якої встановлено одне з наступних відношень порядку:

або   (  не перевищує  ), або   (  не перевищує  ),

Запис впорядкованих множин

Впорядковані (скінченні або такі, елементи яких можна перерахувати) множини часто записують, розташовуючи їх елементи в заданому порядку в круглих дужках. Наприклад, записи

(1; 2; 3) і (2; 1; 3)   (1)

представляють різні скінченні впорядковані множини, які можна отримати з однієї і тієї ж множини {1; 2; 3}, впорядковуючи її двома різними способами. Для запису скінченної впорядкованої множини у виді, аналогічному (1), необхідно вказати перший елемент впорядкованої множини і вказати порядок (правило) розташування наступних елементів.