Підстановки

Визначення. Підстановкою множини А називається біекція на А (біективна відповідність на А).

Число різних підстановок для скінченних множин можна легко обчислити.

Нехай ½A½=nÎN і нехай _nP_n - число таких підстановок. _nP_n=n! Оскільки А~N_n, то можна звести підстановку множини А до підстановки множини N_n. Будь-яка підстановка N_n повинна визначати образ кожного елемента в N_n, що має бути єдиним і відмінним від інших (скрізь визначеність, функціональність та ін’єктивність).

Нехай y - підстановка N_n, тоді y можна визначити як множину n пар y={(1, x₁), (2, x₂),..., (n, x_n)}, де (x₁, x₂,..., x_n}=N_n.

Приклад. y₁ 1 2 3 4 5 6® ù

¯® 5 6 3 1 4 2 ¯ y₁oy₂

y₂ 5 6 3 1 4 2 ¯

¯® 4 5 6 3 1 2 û

Нехай А={а₁, а₂,..., а_n}.

Визначення. Підстановка r називається циклом (циклічною підстановкою), якщо r={(a₁, a₂), (a₂, a₃),..., (a_n-1, a_n), (a_n, a₁)}.

Говорять також про цикл довжини n, якщо область (множина) А має потужність n.

Нехай АÍВ і В – скінченні множини. Розширення r на всю множину В дозволяє визначити нову підстановку s:

s: x= ìr(x), якщо xÎA;

îx, якщо xÏA,

у цьому випадку s - поводиться подібно r у всіх випадках, коли В не «залишаються на місці». Не всі підстановки можуть бути циклами.

Приклад. y₁ з попереднього прикладу сама по собі не є циклом, але містить такі - (1, 5, 4), (2, 6), (3).

Теорема. Кожна підстановка r на скінченній множині А виражається множиною циклів, цикли при цьому можуть розташовуватися в будь-якому порядку і не перетинатися.

Елемент а множини А, для якого r(а)¹а називається нестаціонарним (у y₁ - ²3² - стаціонарний елемент). Якщо ½A½=m, а ½B½=n£m, то число сюр’ективних і ін’єктивних функцій з А в В чи число функціональних відображень з В в А дорівнює _nR_m (число перестановок без повторень), де _nR_m=n!/(n-m)! Якщо при цьому ВÍА, то число таких множин В (число сполучень без повторень з n по m ) дорівнює С_n^m=_nP_m/_mR_m= n!/m!(n-m)! і С_n^m=C_n^n-m.