Комбінаторика: перестановки з повторенням. Розміщення. Розміщення з повторенням.

Розглянемо таку задачу: скільки 8-буквених слів можна скласти із букв слова «множення»? Уявіть собі, що всі букви написані на картках і ми можемо перекладати ці картки, утворюючи нові слова. Чим ця задача відрізняється від задачі про слово «брат»? Правильно, тим, що є букви, які повторюються, у нас є три букви «н». Давайте трішки «виправимо» наше слово, щоб можна було застосувати попередню формулу. А саме: дамо буквам «н» номери, н-1, н-2, н-3. Тепер всі букви різні, отже, кількість слів, що можна з них скласти, становить 8!. Тепер згадаємо, що для нашого новоствореного слова все одно, яка саме з букв «н» іде першою, яка – другою і яка – третьою. Отже, насправді варіантів менше у стільки разів, скількома способами ми можемо переставити букви «н» між собою, тобто, в 3! Рази менше. Отже, кінцева відповідь: можна скласти 8!/3! 8-буквених слів із букв слова «множення».

Приклад: Скільки слів можна скласти, використавши всі букви слова «пропорція»? (словом вважаємо будь-яку комбінацію букв)

Розв’язання: В цьому слові 9 букв, серед них є букви, що повторюються: «п» - 2 рази, «р» - 2 рази, «о» - 2 рази. Якщо б таких букв не було, кількість слів дорівнювала б 9!. За рахунок повторення букв варіантів насправді менше, їх буде 9!/(2!ꞏ2!ꞏ2!).

Отже, якщо маємо множину із n елементів, в якій перший елемент повторюється к1 раз,другий - к2 рази, третій - к3 рази і т.ін.. то кількіть перестоновок елементів такої множини дорівнює n!/(к1!к2!к3!...)

Задача 1. Скільки слів можна скласти, використавши всі букви слова «дискримінант»?

Задача 2. Мати купила апельсин, два мандарини, три яблука і банан і хоче видавати Петрику по одному фрукту кожного дня. Скількома способами вона може це зробити, якщо всі яблука однакові між собою і всі мандарини однакові між собою?

Задача 3. Петрик має 12 марок, серед яких 4 однакових марки з бенгальським тигром і 2 однакових марки з видом на площу Незалежності. Скількома способами він може розмістити ці марки на сторінці клясера, на якій є рівно 12 місць під марки?

Розглянемо таку задачу: в класі 28 учнів-вундеркіндів, скількома способами з них можна вибрати чотирьох, щоб вони поїхали на олімпіади з фізики, хімії, біології та математики? (На кожну олімпіаду може поїхати тільки 1 учень) Позначимо 4 олімпіади як 4 нумерованих місця: . Тоді для першого місця у нас є вибір із 28 учнів, для другого – залишилось 27 варіантів вибору, для третього – 26 варіантів, для четвертого – 25 варіантів:

28 27 26 25

Так як ми обираємо їх одночасно, то варіанти треба перемножити, отже, існує 28ꞏ27ꞏ26ꞏ25 варіантів вибору. (*)

Якщо ми вибираємо із множини впорядковану підмножину, то такий вибір називають розміщенням. Позначають розміщення буквою А. внизу пишемо загальну кількість елементів, вгорі – кількість елементів, яку ми вибираємо. Для створення формули можемо зазначити, що, якщо отриману нами в попередній задачі (*) відповідь домножити на 24!, то матимемо 28!, отже, відповідь попередньої задачі можна записати як 28!/24!

Це – формула розміщень без повторень, коли елементи в множині, з якої ми вибираємо, не повторюються.

А що робити, якщо вони повторюються? Розглянемо таку задачу: на валізі є кодовий замок, який складається з 4 барабанчиків, на яких розміщені цифри від 0 до 9. Скільки варіантів коду існує для такого замка? Для розв’язання знов використаємо нумеровані місця: маємо 4 місця , на кожне з них можна поставити одну із 10 цифр: 10 10 10 10. Так як ми робимо вибір цифр на барабанчиках одночасно, то треба перемножити кількості варіантів, матимемо 10ꞏ10ꞏ10ꞏ10 = 10⁴. Отже, якщо ми на n місць розміщуємо один з m предметів на кожне, то маємо формулу перестановок з повторенням:

Розглянемо такі задачі:

1. Скільки існує 7-цифрових чисел?

Розв’язання: маємо 7 місць під цифри, але на перше місце не можна поставити 0, тому для першого місця є 9 варіантів, а для кожного наступного – по 10 варіантів вибору цифри, отже, всього буде 9ꞏ10⁶ = 9 000 000 чисел.

1. Скільки існує 7-цифрових чисел, в яких немає цифри «7»?

Розв’язання: Так як тепер ми маємо на 1 цифру менше, то для першого місця є 8 варіантів вибору цифри, а для кожного наступного – 9 варіантів, отже, маємо 8ꞏ9⁶ чисел.

1. Скільки існує 7-цифрових чисел, в яких є цифра «7»?

Розв’язання: Число або має цифру «7», або не має її, отже, щоб знайти кількість чисел з цифрою 7, треба від загальної кількості 7-цифрових чисел відняти кількість чисел, в яких нема цифри «7», і будемо мати 9ꞏ10⁶ - 8ꞏ9⁶ чисел.

Задача 4. Скільки існує парних 6-цифрових чисел, в яких нема цифри «6»?

Задача 5. Наталка забула мамин номер телефону, пам’ятає лише дві останні цифри із семи. Скільки спроб додзвонитися їй доведеться зробити в найгіршому випадку? Скільки часу вона витратить на це, якщо на перевірку одного номера вона витрачає 30 секунд?

Задача 6. На картках написані цифри 2,3,4,7,8,9,0. Скільки 4-цифрових парних чисел, цифри яких не повторюються, можна скласти з них?

Задача 7. Катерина сіла в маршрутку біля метро, в яку, крім неї, сіло ще 20 людей. Маршрутка робить 7 зупинок, на яких люди тільки виходять. І замислилась Катерина: скільки їснує варіантів виходу цих людей(без неї) з маршрутки?