Перестановки з повтореннями
Розглянемо це питання на прикладі. Нехай задана множина А = {а,а,а,b,b}. Розв’яжемо задачу: Скільки упорядкованих множин можна утворити з цих елементів? Будемо вважати, що усі елементи різні. Тоді з них можна утворити 5! перестановок. Тепер звернемо увагу на те що серед них є перестановки, в яких елемент 2 повторюється тричі, скажімо а,а,b,b,а. Значить при перестановці цих елементів а перестановка не зміниться. Не зміняться від цього й усі інші, тобто кожна з них повториться стільки разів, скільки разів можна переставити між собою елементи а. А їх можна переставити 3! раз. Отже, щоб звільнитися від усіх інших однакових перестановок, загальну їх кількість слід розділити на 3!. Аналогічну картину ми отримаємо і від повторення елементів b. З цього випливає, що для того, щоб отримати усі різні перестановки, треба загальну кількість перестановок поділити на добуток 3!×5!, тобто провести обчислення за формулою = . В загальному ж вигляді ця формула буде мати такий вигляд= Приклад. Скільки різних слів можна утворити зі слова мамбатумба (смисл слів ролі не грає)? У цьому слові буква м повторюється 3 рази, буква а – теж 3 рази, буква б повторюється двічі, а букви, у і т – по 1 разу.Значитьслів можна скласти = . Вправи Перестановки без повторень 1. Обчислити: а) ; б) ; в) 10! – 7! ; г) 3! + 4! ; д) 5! – 25. 2.Порівняйте числа: а) 4! – 3! і 4; б) 1! – 3! і 0; в) 2! + 4! і 26; г) 4! і 3! + 2!; д) 5! × 9 і 6!. 3. Розв’язати рівняння: а) 7! + 5! – х = 40. б) х + 3! = 5! в) 6! – 2х = 3×4!. 4. Скоротити дроби: а) ; б) 8 + ; в) . 5. Скількома способами можна скласти прапор з 5 горизонтальних смуг матерії різного кольору? 6. Скількома способами можна скласти прапор з 3 горизонтальних і 2 вертикальних смуг матерії різного кольору? 7. Скільки 5-значних чисел можна утворити з цифр 0, 2, 5, 6, 9, якщо цифри не повторюються? 8. 6 студентів підготувалися до відповіді на іспиті. Скількома способами вони можуть утворити чергу для відповіді? 9. У коробці 8 кубиків різного кольору. Скількома способами можна витягти ці кубики з коробки? 10. Скільки різних слів можна утворити з букв слова „Стрілковий”? 11. Довести тотожність: Рп = (п –1)×(Рп–1 + Рп–2). 12. 7 книг різних авторів разом з тритомником ще одного розташовані на полиці. Скількома способами можна розташувати їх так, щоб книги автора тритомника стояли поряд? 13. Скількома способами можна розставити 5 томів Т.Г.Шевченка так, щоб: а) перший том стояв скраю зліва; б) перший том стояв скраю справа або зліва; в) 2 і 3 томи стояли поряд; г) 1 і 2 томи стояли поряд зліва; д) 1 і 2 томи не стояли поряд? 14. На зборах мають виступити 5 осіб: А, Б, В, Г і Д. Скількома способами їх можна розташувати у списку так, щоб: а) Б не повинен виступати перед А; б) Б не повинен виступати після А. 15. Скільки перестановок можна утворити з цифр 1, 2, 4, 5, 7, 8, 9, які починаються з цифри 5? з числа 45? з числа 745? 16. Скількома способами можна розмістити на полиці 6 томів, щоб 3 і 5 томи не стояли поряд? 17. Обчислити: а) ; б) . 18. Розв’язати рівняння: а) 2× Рх = 48; б) Рх : 3 = 40; в) ; г) 19. Скількома способами можна вишикувати в одну шеренгу гравців двох футбольних команд (по 11 гравців) так, щоб при цьому 2 футболісти однієї команди не стояли поряд? Перестановки з повтореннями 20. Скільки різних 8-значних чисел можна утворити з цифр 5, 3, 0, якщо число 5 повторюється 3 рази, число 3 – 4 рази, а число 0 – 1 раз? 21. Скільки різних 8-значних чисел можна утворити з цифр 5, 3, 0, якщо число 5 повторюється 4 рази, число 3 – 2 рази, а число 0 – 2 рази? 22. На реї 9 місць для сигнальних прапорців. Скільки сигналів можна передати, якщо є 3 прапорці червоних, 2 прапорця синіх, 1 білий і 4 зелених, використовуючи усі прапорці? 23. Скільки різних слів можна утворити з слова „Міміно” , використовуючи усі букви? 24. Скільки різних слів можна утворити з слова „Математика”, використовуючи усі букви? 25. У мами 2 яблука і 3 груші. Щодня протягом п'яти днів підряд вона видає синові по одному фрукту. Скількома способами вона може Це зробити?
26. Скількома способами можна розставити на другій лінії шахової дошки 2 тури, 2 слона і 3 пішака? 27. П’ятизначний телефонний номер складається з двох трійок і трьох четвірок, але в якому порядку вони розташовані, хлопчик забув. Скільки йому треба зробити спроб, щоб додзвонитися до свого друга. 28. Скількома способами можна розставити 20 книг на 5 полках, кожна з яких може вмістити усі 20 книг. 29. Клоун кидає 10 кілець на 6 стержнів. Скільки варіантів попадання кілець на стержні може статися, якщо клоун ні разу не схибить. Розміщення. а) розміщення з повтореннями. Спробуємо з елементів множини Х={а; b; c; d}скласти будь-які пари. Комбінуючи ці елементи и можемо отримати такі: (а,а); (а,b); (а,c); (а,d); (b,а); (b, b); (b,c); (b,d); (c,а); (c,b); (c,c); (c,d); (d,а); (d,b); (d,c); (d,d); Розв’яжемо цю задачу в загальному вигляді. Зайти число кортежів довжини k, які можна утворити з элементів т-множини X. Щоб вирішити це завдання, треба знайти число кортежів в декартовому добутку Х´Х´...´Х, який містить k множників (цей декартовий добуток саме і k складається з таких кортежів). Але за правилом добутку число елементів в нашому декартовому добутку дорівнює п(Х)× п(Х) × п(Х)× . . . × п(Х). Оскільки k разів за умовою п(Х) = т, то п(Х´Х´...´Х) = т× т× т×. . .× т = тk . k разів Отже, число кортежів довжини k, складених з елементів т-множини X, дорівнює mk.
Кортеж довжини k, складений з елементів m-множини, називають розміщенням з повтореннями з т елементів по k, а число таких кортежів позначають (від французького слова arrangement –розміщення). Таким чином, = пk. Означення. Розміщенням зп елементів по k елементів називається будь-яка упорядкована k-підмножина даної п-множини. ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|