ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     1.3. ПЕРЕСТАНОВКИ

      Нехай множинавміщуєпредметів різного виду.
Розглянемо розміщення ізелементів по, які відмінні одне від другого лише порядком елементів, що в них входять. Такі розміщення називають перестановками, їх число позначають.

     

      Приклад 5. Маючи шість олівців різного кольору малюк малює веселку із шести кольорів. Скільки різних веселок він може намалювати?

      Розв'язання. Число веселок - це число перестановок із шести по шість, тому малюк може намалювативеселок.

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

      Наприклад, перестановку можна задати так:
;;.

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

, тобто перестановку представлено розкладом на цикли.
Будемо називати перестановкуперестановкою типу,якщо вона вміщує цикли в точності до- циклів і довжиною. Типзаписують символічно (якщо, то- опускається).

      Наприклад, перестановка

має розклад по циклам
, тобто тип.
Зобразимона рис.2

Рис.2.

ЗМІСТ