Тема 2. Перестановки, розміщення, сполучення з повторенням. Теоретичні відомості Розміщенням з повторенням

Часто доводиться робити упорядковані вибірки з повторенням деяких елементів. Наприклад, з множини М=(1,2,3) такими вибірками є 3-вибірки (1,1,2), (1,2,1), (2,1,1), (2,3,3), (3,2,3),(3,3,2), (1,1,1), (2,2,2), (3,3,3), (2,2,1), (2,1,2), (1,2,2), (3,2,2), (2,3,2), (2,2,3), (1,3,3), (3,1,3), (3,3,1), (1,3,1), (1,1,3), (3,1,1), (1,2,3), (2,1,3), (3,1,2). (Всього таких вибірок буде 27). Такі загальні упорядковані k вибірки з n елементів іноді називають кортежами.

Визначення. Розміщенням з повторенням з n елементів по k називається кортеж (вибірка з повторенням) довжини k з n елементів.

Кожен елемент може бути обраний n способами, тоді за правилом добутку .

Кількість k розміщень з повтореннями з n елементів обчислюється за формулою:

.

В нашому прикладі число розміщень з трьох елементів 1,2,3 по 3 з повторенням дорівнюе .

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

Нехай множина М з n предметів ( ) складається з множини предметів першого типу кількістю ( ), множини предметів другого типу кількістю і т.д. до множини предметів k-го типу кількістю ( ), причому , , , .

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

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

Список ( ) називають специфікацією перестановки.

Приклад 7.

Маємо набір з четирьох літер aabc. Тоді всі перестановки з повтореннями з цих літер: abac, baac, aabc, aacb, abca, baca, acba, acab, bcaa, cbaa, caba, caab. В розглянутому вище прикладі, літер a в даному наборі дві, а літер b и с – по одній. Тоді кільсть всіх перестановок з повтореннями з 4 элементів та складом літер 2, 1, 1 дорівнює P(2, 1, 1) = 4! / (2! 1! 1!) = 12, в чому ми переконались.

Сполучення з повтореннями.

Маємо предмети n типів у такій кількості, що предметів кожного типу не менше, ніж k екземплярів. Число k – кількість обираємих элементів, та n –кількість типів елементів, з яких проводимо вибір. Скільки існує неупорядкованих k вибірок (комбінацій) предметів з можливими повторюваннями?

Розглянемо задачу: маємо об’єкти n типів. Скільки існує способів вибрати k об’єктів, порядок розташування яких в вибірках не має значення? Складемо вибірки таким чином: для кожного типу пишуть стільки одиниць, скільки предметів цього типу входять у комбінацію, якщо предмети деякого типу не входять у комбінацію, тоді у відповідному місці пишеться 0, тобто кожну вибірку доповнюємо нулями, кількість яких дорівнюе найбільшої кількості типів предметів відсутніх в вибірці – n-1.Тоді вибірки будуть мати вигляд, наприклад, або . Кожна вибірка має n+k-1 елементів. Кількість таких вибірок буде дорівнювати кількості перестановок з повторюваннями з n+k-1 елементів, де одиниці повторюються k разів, нулі- n-1 раз: .

Приклад 8.

З трьох цифр1, 2, 3 скласти всі можливі сполучення з повтореннями, які містять по 2 элементи.

Розв’язання:

Всі такі сполучення: (1, 1); (1, 2); (1, 3); (2, 2); (2, 3); (3, 3).

Скористаємося формулою (k = 2, n = 3). .

Пояснемо цю формулу на даному прикладі:

Запишемо послідовності, які містять 2 одиниці та 2 нулі, так як максимальна кількість типів елементів, які відсутні в виборці дорівнює 2. Послідовності, які відповідають кожному з 6 сполук з повтореннями: (1, 1) – 1100; (1, 2) – 1010; (1, 3) – 1001; (2, 2) – 0110; (2, 3) – 0101; (3, 3) – 0011.

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

Приклад 9.

В кондитерському магазині продають 4 сорти тістечок: наполеони, эклери, пісочні та «картошка». Сколькома способами можно купити 7 тістечок?

Розв’язання:

Кількість способів рахуємо за формулою:

.