1. Елементи комбінаторики без повторень

Комбінаторика – це область математики, в якій вивчається питання про те, скільки різних комбінацій, що задовольняють тим чи іншим умовам, можна скласти з елементів заданої множини.

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

Формула для числа розміщень :

.

Наприклад, потрібно визначити, скількома способами різні позики можуть розподілитися між десятьма фірмами ().

Це - задача на число розміщень з 10 елементів по 3.

Маємо:

.

Якщо , то– це число таких розміщень, які відрізняються тільки порядком розміщення елементів, але не самими елементами. Такі розміщення називаються перестановками. Перестановки зелементів позначають. Отже,

Наприклад, відвідувачів заходять по одному на прийом до керівника установи. Скільки існує варіантів різних черг?

Це – задача на число перестановок з елементів. Тому маємо:. Якщо, зокрема,, то.

Якщо не істотний порядок розміщення елементів у вибірках, одержуємо комбінації з елементів по:. Число таких комбінацій визначається за формулою:.

Наприклад, якщо з 8 виборів фірми потрібно 3 відправити на виставку продукції, то це можна зробити способами:

.

2. Елементи комбінаторики з повтореннями

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

а) Перестановки з повтореннями. Нехай задано різних елементів. побудуємо вибірку об’ємуз цих елементів, причому перший елемент повторимораз, другий –раз, ...,– тий –раз; при цьому.

Нехай, наприклад, елементами є різних букв:. Нехайвикористовуєтьсяраз,–раз, ...,–раз. Розглянемо вибірку:

.

Елементи можна переставлятиспособами, елементи–способами, елементи–способами. Число перестановок з повтореннями від цього не зміниться. Загальне число перестановок з повтореннямивизначається за формулою:

.

Наприклад, із букв слова “мама” можна утворити 6 різних “слів”: мама, амам, ммаа, аамм, амма, маам. Це дійсно так, оскільки, і

.

б) Комбінації з повтореннями. Комбінацією з повтореннями з елементів поназивається будь-який- елементний набір типу (), де кожен з елементів набору належить до одного зтипів. Число комбінацій з повтореннями зелементів попозначають.

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

.

Наприклад. У кіоску є коробки цукерок трьох видів. Скількома способами можна замовити набір із п’яти коробок?

В цій задачі , а. Таким чином,

в) Розміщення з повтореннями. Нехайі– довільні натуральні числа. розміщенням з повторенням зелементів поназивається будь-який упорядкований- елементний набір виду, де– не обов’язково різні елементи з множиниелементів. Число розміщень з повтореннями позначають.

Для будь-яких натуральних чисел імає місце формула:.

Ця формула впливає з правила добутку.

Наприклад. Скільки різних трьохзначних чисел можна скласти з цифр 1,2,3,4, і 5, якщо

а) одна і та ж сама цифра може використовуватись не більше одного разу;

б) можливі повторення цифр.

У випадку а) достатньо обчислити . Маємо:.

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