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

3. Розглянемо множину M={a₁,a₂,a₃,...,a_n}. Розглянемо над цією множиною кортеж довжини k, де k=k₁+k₂+k₃+...+k_n, причому елемент a₁ - повторюється k₁ раз; елемент a₂ повторюється k₂ раз; елемент a₃ - k₃ раз; нарешті, елемент a_n - k_n разів. У комбінаториці такі кортежі називають перестановками з повтореннями, а їх число позначають символом Pk₁,k_2,k_3,…k_n i читають: число перестановок з повтореннями, в якій перший елемент повторюється k₁ раз, другий - k₂, третій - k₃, n-ий - k_n раз.

Означення: будь-який кортеж довжини k, де k=k₁+k₂+k₃+...+k_n над даною n елементною множиною М, в якому елемент a₁ - повторюється k₁ раз, елемент a₂ повторюється k₂ раз, елемент a₃ - k₃ раз, … елемент a_n - k_n разів називається перестановкою довжини k (k=k₁+k₂+k₃+...+k_n) з повтореннями.

Числом перестановок з перетвореннями обчислюють за формулою: Pk₁,k_2,k_3,…k_n =(k₁+k₂+k₃+...+k_n)!/(k₁!k₂!k₃!...k_n!). Застосування цієї формули покажемо на прикладі наступної задачі.

Задача: скільки чисел можна утворити з цифр 1, 2, 3, якщо 1 - повторюється три рази, 2 - два, 3 - оди раз.

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

У цій задачі є трьохелементна множина М={1, 2, 3}. Із елементів цієї множини потрібно утворити кортеж довжини k, що дорівнює k₁+k₂+k₃, де k₁=3, k₂=2, k₃=1. Отже, k=3+2+1=6, тобто треба утворювати кортежі довжини 6. Це означає, що нам потрібно обчислити число перестановок з повтореннями, в яких перший елемент повторюється три рази, другий - два рази, третій - один. Таким чином, Р_3,2,1=(3+2+1)!/(3!•2!•1!)=6!/(3!•2!•1!)=(1•2•3•4•5•6)/(1•2•3•1•2•1)=720:12=60. Отже, за допомогою цифр 1, 2, 3 можна записати 60 шестицифрових чисел, в яких цифра 1 буде повторюватися цифра 2 - два рази, цифра 3 - один раз.

У комбінаториці розглядаються такою перестановки без повторень. Введемо відповідне означення та виведемо формулу для обчислення їх числа.

Означення: перестановкою без повторень з даних n елементів даної n елементної множини М називають розміщення без повторень із даних n елементів по n елементів.

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

Теорема: число перестановок із даних n елементів обчислюють за формулою: Р_n=n!=1•2•3•...•n.

Доведення.

Згідно із означенням перестановок без повторень Р_n=A_nⁿ. За формулою A_nⁿ=n!/(n-k)!. Отже, Р_n= A_nⁿ=n!/(n-n)!=n!/0!=n!/1=n! Формула доведена.

Задача: скільки п’ятицифрових чисел можна записати за допомогою цифр 1, 3, 5, 7, 9 якщо жодна із цифр не повторюється.

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

У задачі є п’ятиелементна множина М={1, 3, 5, 7, 9}. Із елементів цієї множини потрібно утворювати п’ятицифрові числа, причому жодна з цифр не повторюється, а оскільки одне п’ятицифрове число від іншого, утвореного з тих самих цифр буде відрізнятися навіть при переставлянні двох цифр, то нам слід утворювати перестановки без повторень із п’яти елементів. Отже у формулі: Р_n=n!, n=5. Р₅=5!=1•2•3•4•5=120. За допомогою п’яти цифр запишемо 120 чисел.