Комбінаторика: перестановки

Перестановки – це такі розташування елементів множини, при яких враховується порядок слідування. Для обчислення кількості варіантів використовують такий метод: нехай маємо множину із n елементів. Будемо розставляти їх в ряд на нумеровані місця. Тоді для першого місця у нас є n варіантів, для другого – n-1 варіант, для третього – n-2 варіанти і т.ін., і для n-го місця залишається 1 варіант. Тепер, щоб знайти загальну кількість варіантів, треба перемножити n(n-1)( n-2)( n-3)…3ꞏ2ꞏ1, такий добуток позначається n! (читається «n факторіал»). Отже, щоб знайти кількість перестановок із n різних елементів, треба обчислити n!

P_n = n!

Приклад: Скількома способами можна розставити в ряд на полицю 6 книг?

Розв’язання: маємо 6 місць, є 6 варіантів вибрати книгу на І місце, 5 способів – на ІІ, 4 – на ІІІ, 3 – на ІV, 2 – на V і 1 – на VІ, всього 6ꞏ5ꞏ4ꞏ3ꞏ2ꞏ1 = 720 способів, або 6!

Тепер модифікуємо цю задачу: Скількома способами можна розставити в ряд на полицю 6 книг так, щоб «Українська мова» і «Українська література» стояли поруч?

Розв’язання: «Склеїмо» ці дві книги, тоді ми будемо мати 5 книг, 5 книг розставити на полиці можна 5! способами. Тепер згадаємо, що ці дві книги ще можна переставити між собою, переставити 2 книги між собою можна 2! способами, отже, варіантів стає в 2! рази більше, і всього буде 2!ꞏ5! = 240 способів.

А якщо умова виглядає так: «Скількома способами можна розставити в ряд на полицю 6 книг так, щоб «Українська мова» і «Українська література» НЕ стояли поруч?»

Розв’язання: Ми знайшли, скільки всього існує варіантів і скільки варіантів, якщо ці книги стоять поруч. Тоді для того, щоб знайти кількість варіантів, при яких вони НЕ стоять поруч, треба від всієї кількості способів відняти ті способи, при яких книги стоять поруч: 720 – 240 = 480 варіантів.

Розглянемо ще дві задачі: 1) скількома способами можна розсадити людей за круглий стіл? 2) скільки існує способів створити намисто із 6 намистинок?

Для розв’язання цих задач треба зрозуміти, які варіанти вважаються однаковими. Якщо для того, щоб отримати з одного варіанта інший людям не треба вставати і мінятися місцями, то це – один і той же варіант. Якщо для того, щоб отримати з одного намиста інше не треба розв’язувати мотузку і переставляти намистинки, то це – одне і те ж намисто. Тоді для розв’язування першої задачі перенумеруємо місця за столом, тоді задача зведеться до розстановки 6 людей по 6 нумерованим місцям, тобто, таких варіантів 5! Але якщо подумаємо ось про що: якщо у нас сидять Василь, Петро , Михайло саме в такому порядку, і перед Василем на столі було написано цифру «1», перед Петром – «2», а перед Михайлом – «3», то для того, щоб перед Петром стало написано «1», а перед Михайлом – «2», нам не треба їх підіймати з місць, а досить просто повернути стіл, то стає очевидним, що насправді варіантів менше у стільки разів, скільки ми можемо прокрутити стіл, тобто, в 6 разів, і насправді розсадити 6 людей за круглий існує 6! : 6 = 5! варіантів. Врахуємо це в задачі про намисто, намисто із 6 намистинок, отже, розкласти намистинки по колу буде 5! Способів, але намисто можна перевернути і мати дзеркальне розташування намистинок без розв’язування мотузочки і переставлення намистинок. Тоді насправді варіантів 5! /2.

1. П'ять товаришів на своїх машинах вирушили в подорож і домовились щогодини міняти порядок слідування. Через скільки годин вони вичерпають всі можливі варіанти?

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

3. Скількома способами можна розставити на полиці 12 підручників так, щоб фізика, хімія та біологія стояли поруч?

4. В день Василь має 7 різних уроків, серед яких математика і фізкультура. Скільки існує способів скласти розклад для Василя так, щоб математика не йшла після фізкультури?

5. Марічка має круглий різдвяний віночок і хоче прикрасити його гірляндою з 10 різнокольорових лампочок. Скільки в неї способів розташувати лампочки в гірлянді, якщо віночок видно лише з одного боку?