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

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

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

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

.

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

.

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

.

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

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

.

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

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

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

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

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

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

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

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

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

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