Отримання знань

Перестановки з повтореннями

Розміщення з повтореннями, що відрізня­ються лише порядком елементів у них, нази­вають перестановками з повтореннями. Тобто це вибірки виду (а₁, а₂,...,а_n), де еле­мент а₁ зустрічається m₁ разів, елемент а₂ - m₂ разів, елемент а_n - m_n разів. Тоді довжина всієї вибірки буде дорівнювати

.

Набір натуральних чисел   називають складом цієї вибірки.

Наприклад, (А, А, С, В, А, С) -вибірка складу (3, 1, 2) із множи­ни, що містить три елементи {А, В, С}. Кількість таких вибірок одного і того самого складу називають кількістю перестановок з по­втореннями з n елементів із зада­ними числами повторень m₁, m₂, ..., m_n   кожного елемента. Це число позначають через   і обчислюють за формулою

,

де .

Задача 1.

Скількома способами можна роз­ташувати білі фігури: 2 коней, 2 слонів, 2 тур, 1 ферзя і 1 короля на першій лінії шахової дошки?

Розв'язання.

Потрібно обчислити кількість упорядкованих вибірок довжиною 8, які мають заданий склад (2, 2, 2, 1, 1), тобто кількість перестановок з повтореннями:

.

Відповідь. 5040.

Задача 2.

Скільки різних слів можна отримати, переставляючи букви в слові «Міссісіпі»?

Для того, щоб побачити підказку до розв'язання задачі, виділіть блок між словами «Початок» і «Кінець» або натисніть Ctrl+A.

Початок 

Потрібно обчислити кількість упорядкованих вибірок довжиною 9, які мають заданий склад (1, 4, 3, 1).

Кінець

Задача 3.

Скільки різних браслетів можна зроби­ти з 5 смарагдів, 6 рубінів і 7 сапфірів (всі ка­мені одного виду однакові), якщо в браслет входять усі 18 каменів?

Задача 4.

Скількома способами можна розбити m + n + р предметів на три групи так, щоб в одній групі було m, у другій - n, а в третій - р предметів?

Підказка. Відповідь залежить від того, чи всі предмети є однаковими. Якщо всі предмети однакові, то таких способів буде 1. Розгляньте самостійно випадок, коли предмети різні.

Задача 5.

У мами 2 яблука, 3 груші і 4 апельсини. Кожний день вона дає дочці по одному фрук­ту. Скількома різними способами це можна зробити?

Задача 6.

Трамваю залишилось зробити 2 зупинки: передостанню і кінцеву. N пасажирів розв'язують задачу: «Скільки є різних способів виходу паса­жирів на цих зупинках?». Допоможіть знайти правильну відповідь.

Розв'язання.

Позначатимемо впорядкованою парою чисел спосіб виходу посажирів відповідно на 1-ій і 2-ій зупинках. Матимемо (0, N), (1, N-1), (2, N-2), ... (N-1, 1), (N, 0). Залишилось обчислити кількість способів отримання таких пар і знайти їх суму.

Остаточно, різних способів виходу паса­жирів на зупинках буде

.

Відповідь. .