Урок 3. Перестановки

ВИДЕО УРОК

Традиційне рішення комбінаторних завдань зводиться до визначення виду поєднання, про яке йде мова в завданні, і застосування відповідної формули для обчислення кількості цих поєднань.

Тут основна трудність – визначення виду поєднань: перестановки, розміщення, комбінації.

Перестановки.

Нехай є  n  різних об'єктів. Переставлятимемо їх усіма можливими способами (число і склад об'єктів залишається незмінним, міняється тільки їх порядок). Комбінації, що вийшли, називаються перестановками.

Перестановками називають комбінації, що складаються з одних і тих же  n  різних об'єктів і відрізняються тільки порядком їх розташування.

Або

Перестановками називаються такі вибірки елементів, які відрізняються тільки порядком розташування елементів, але не самими елементами.

Відмітною особливістю перестановок є те, в кожній з них бере участь уся множина, тобто, все  n  об'єктів.

Формула для числа перестановок.

Якщо перестановки робляться на множині з  n  елементів, їх число визначається по формулі:

n! – позначення, яке використовується для короткого запису добутку усіх натуральних чисел від  1  до  n  включно і називають

"n, – факторіал".

За визначенням, вважають, що 

0! = 1, 1! = 1.

Схема для вирішення комбінаторних завдань.

Перед рішенням задачі на обчислення різних видів поєднань пропонується схема сприяючи правильному виявленню виду поєднання згідно з умовою завдання. При цьому враховуються характеристичні властивості кожного виду поєднань.

Як видно з схеми, вибір формули залежить від того, чи будуть усі елементи використовуватися у формуванні поєднань або ні, і чи важливий їх порядок. Застосовуючи таку схему, завжди можна проаналізувати умову завдання і відповісти на ці два головні питання.

ЗАДАЧА:

Скількома способами можна розсадити  5  чоловік за столом ?

РОЗВ'ЯЗАННЯ:

Використовуємо формулу кількості перестановок.

Р₅ = 5! = 120.

ВІДПОВІДЬ:

120 способами.

ЗАДАЧА:

На книжковій полиці поміщається  30  томів. Скількома способами їх можна розставити, щоб при цьому  1-й  і  2-й  томи не стояли поряд ?

РОЗВ'ЯЗАННЯ:

Визначимо загальне число перестановок з  30  елементів по формулі

Р₃₀ = 30!

Щоб вичислити число "зайвих" перестановок, спочатку визначимо, скільки варіантів, в якому  2-й  том знаходиться поряд з  1-м праворуч від нього. У таких перестановках  1-й том може займати місця з першого по  29-і, а  2-й  з другого по  30-і – всього  29  місць для цієї пари книг. І при кожному такому положенні перших двох томів інші  28  книг можуть займати інші  28  місць в довільному порядку. Варіантів перестановки  28 книг.

Р₂₈ = 28! 

Всього "зайвих" варіантів при розташуванні  2-го тому праворуч від  1-го  вийде

29×28! = 29!

Аналогічно розглянемо випадок, коли  2-й том розташований поряд з першим, але зліва від нього. Виходить таке ж число варіантів

29×28! = 29!

Означає усього "зайвих" перестановок

2×29!,

а потрібних способів розставляння

30! – 2×29

Вичислимо це значення

30! – 2×29! = 29!×30 – 2×29!

= 29!×(30 – 2) = 29!×28.

Итак, нам треба перемножити усі натуральні числа від  1  до  29  і ще раз помножити на  28.

ВІДПОВІДЬ:

2,4757335×1032.

ЗАДАЧА:

Скільки чотиризначних чисел можна скласти з чотирьох карток  з цифрами  0, 5, 7, 9 ?

РОЗВ'ЯЗАННЯ:

Для того, щоб скласти чотиризначне число треба задіяти усі чотири картки (цифри на яких різні), і це дуже важлива передумова для застосування формули  Р_n = n! Очевидно, що, переставляючи картки, ми отримуватимемо різні чотиризначні числа, але коли картка з нулем розташовується на  1-м  місці, те число стає тризначним, тому ці комбінації слід виключити.

Спочатку знайдемо кількість усіх можливих перестановок  4  карток

Р₄ = 4! = 24.

Нехай нуль знаходиться на  1-м  місці, тоді решта  3  цифри в молодших розрядах можна переставити

Р₃ = 3! = 6  способами.

Оскільки карток трохи, то тут нескладно перерахувати усі такі варіанти

0579,  0597,  0759,  0795,  0957,  0975.

Таким чином, із запропонованого набору можна скласти

24 – 6 = 18  чотиризначних чисел.

ВІДПОВІДЬ:  18.

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

Для випадку, коли серед вибираних  n  елементів однакові (вибірка з поверненням), завдання про число перестановок з повтореннями можна виразити питанням:

Скількома способами можна переставити  n  предметів, розташованих на  n  різних місцях, якщо серед  n  предметів є  k  різних типів (k < n), т. е. однакові предмети.

Формула для числа перестановок з повтореннями.

Для перестановок  n – кількість елементів, що переставляються,

n ₁, n₂, … n_k – число повторень.

Схема для вирішення комбінаторних завдань.

ПРИКЛАД:

У слові "темперамент"  11  букв (n = 11), буква  "т"  повторюється двічі  (n₁ = 2), буква  "е" – тричі  (n₂ = 3) і буква  "м" – двічі (n₃ = 2). Число можливих перестановок букв в цьому слові:

У перестановках з повтореннями, як і в звичайних перестановках, бере участь відразу уся безліч об'єктів, але є одно але: в цій множині один або більша кількість елементів (об'єктів) повторюється.

ЗАДАЧА:

Скільки різних букв поєднань можна отримати перестановкою карток з наступними буквами:

К, О, Л, О, К, О, Л, Ь, Ч, И, К ? 

РОЗВ’ЯЗАННЯ:

У тому випадку, якщо б усі букви були різні, то слід було б застосувати тривіальну формулу  Р_n, проте абсолютно зрозуміло, що для запропонованого набору карток деякі маніпуляції спрацьовуватимуть <<вхолосту>>, так, наприклад, якщо поміняти місцями будь-які дві картки з буквами  <<К>>  у будь-якому слові, то вийде то ж саме слово. Причому, фізично картки можуть сильно відрізнятися: одна бути круглою з надрукованою буквою  <<К>>, інша – квадратною з намальованою буквою  <<К>>. Але по сенсу завдання навіть такі картки вважаються однаковими, оскільки в умові питається про букво поєднання.

Все гранично просто – всього  11  карток, серед яких буква

К – повторюється  3  рази.

О – повторюється  3  рази.

Л – повторюється  2  рази.

Ь – повторюється  1  раз.

Ч – повторюється  1  раз.

И – повторюється  1  раз.

Перевірка: 

3 + 3 + 2 + 1 + 1 + 1,

Що і вимагалося перевірити.

По формулі кількості перестановок з повтореннями:

Різних букво поєднань можна отримати – 554400.

На практиці цілком допустимо не записувати загальну формулу і, крім того, опускати одиничні факторіали:

ВІДПОВІДЬ:  554400.

ЗАДАЧА:

Олексій займається спортом, причому  4  дні в тиждень – легкою атлетикою, 2  дні – силовими вправами і один день відпочиває. Скількома способами він може скласти собі розкладів зайняття на тиждень ?

РОЗВ'ЯЗАННЯ:

Формула  Р₇ = 7!  тут не годиться, оскільки враховує співпадаючі перестановки (наприклад, коли міняються місцями силові вправи в середу з силовими вправами в четвер).

По формулі кількості перестановок з повтореннями:

105  способами можна скласти розклад зайняття на тиждень.

ВІДПОВІДЬ:  105.

Перестановки і теорія вірогідності.

Часто необхідність підрахунку числа варіантів виникає в теорії вірогідності.

ЗАДАЧА:

На книжковій полиці стояло  30  томів. Дитина впустила книги з полиці, а потім розставив їх у випадковому порядку. Яка вірогідність того, що він не поставив  1-й  і  2-й  томи поруч ?

РОЗВ'ЯЗАННЯ:

Спочатку визначимо вірогідність подія  А, що полягає в тому, що дитина поставила  1-й  і  2-й  томи поруч. Елементарна подія – деяке розставляння книг на полиці. Зрозуміло, що загальне число усіх елементарних подій дорівнюватиме загальному числу усіх можливих перестановок 

Р₃₀ = 30!.

Число елементарних подій, що сприяють події  А, дорівнює числу перестановок, в яких  1-й  і  2-й  томи знаходяться поруч, воно рівне

2×29!.

Вірогідність визначаємо діленням числа сприяючих елементарних подій на число усіх можливих елементарних подій.

Подія  В – дитина не поставила  1-й  і  2-й  томи поруч – протилежно події  А, означає його вірогідність:

Р(В) = 1 – Р(А) =

1 – ¹/₁₅ = ¹⁴/₁₅ = 0,9333.

ВІДПОВІДЬ:  0,9333.

У відповіді вийшло число близьке до одиниці, це означає, що при такій кількості книг випадково поставити два задані томи поруч складніше, ніж не поставити. 

Завдання до уроку 3

• Завдання 1
• Завдання 2
• Завдання 3

Інші уроки:

• Урок 1. Прості методи рішення комбінаторних завдань
• Урок 2. Правило суми і правило добутку
• Урок 4. Розміщення
• Урок 5. Сполучення