Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




3. Розглянемо множину M={a1,a2,a3,...,an}. Розглянемо над цією множиною кортеж довжини k, де k=k1+k2+k3+...+kn, причому елемент a1 - повторюється k1 раз; елемент a2 повторюється k2 раз; елемент a3 - k3 раз; нарешті, елемент an - kn разів. У комбінаториці такі кортежі називають перестановками з повтореннями, а їх число позначають символом Pk1,k2,k3,…kn i читають: число перестановок з повтореннями, в якій перший елемент повторюється k1 раз, другий - k2, третій - k3, n-ий - kn раз.

Означення: будь-який кортеж довжини k, де k=k1+k2+k3+...+kn над даною n елементною множиною М, в якому елемент a1 - повторюється k1 раз, елемент a2 повторюється k2 раз, елемент a3 - k3 раз, … елемент an - kn разів називається перестановкою довжини k (k=k1+k2+k3+...+kn) з повтореннями.

Числом перестановок з перетвореннями обчислюють за формулою: Pk1,k2,k3,…kn =(k1+k2+k3+...+kn)!/(k1!k2!k3!...kn!). Застосування цієї формули покажемо на прикладі наступної задачі.

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

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

У цій задачі є трьохелементна множина М={1, 2, 3}. Із елементів цієї множини потрібно утворити кортеж довжини k, що дорівнює k1+k2+k3, де k1=3, k2=2, k3=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=Ann. За формулою Ann=n!/(n-k)!. Отже, Рn= Ann=n!/(n-n)!=n!/0!=n!/1=n! Формула доведена.

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

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

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

Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...