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

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

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

У задачі йдеться про п’ятиелементну множину {2, 4, 5, 6, 7}, із якої слід вибирати кортежі довжини два так, щоб елементи, тобто цифри, не повторювалися. Отже, необхідно обчислити число розміщень без повторень із п’яти елементів по два елемента. Використаємо формулу А_n^k=n(n-1)(n-2)...(n-k+1), в якій n=5, k=2. Обчислюємо А₅²;=5•(5-1)=5•4=20. Таким чином, за допомогою цифр 2, 4, 5, 6, 7 можна записати 20 двозначних чисел так, щоб вони не повторювалися.

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.

Дата добавления: 2014-01-05