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

1 Кожна перестановка є продуктом непересічних циклів. Щоб довести теорему в назві розділу, нам потрібна лема про множення перестановок.

Не кожна перестановка є циклом, напр. (12342143). ( 1 2 3 4 2 1 4 3 ) . З іншого боку, як ми доведемо в цьому розділі, будь-яку перестановку можна записати як добуток непересічних циклів: ви можете перевірити, що наведена вище перестановка дорівнює (1,2)(3,4) ( 1 , 2 ) ( 3 , 4 ) .

Оскільки кожна перестановка є продуктом циклів, кожна перестановка може бути представлена ​​як добуток транспозицій. Ми щойно представили певну перестановку як добуток 5, 9 і 11 транспозицій — усі непарні числа. Це не випадковість!

Кожну перестановку на скінченній кількості елементів можна розкласти на циклічні перестановки, нетривіальні орбіти яких не перетинаються. Окремі циклічні частини перестановки також називаються циклами, таким чином другий приклад складається з 3-циклу та 1-циклу (або фіксованої точки), а третій складається з двох 2-циклів.

Кожна перестановка є циклом. Будь-яка перестановка може бути виражена в добутку непересічних циклів. Тому неправда.

циклічна перестановка (або цикл) — це перестановка елементів деякої множини X, яка відображає елементи деякої підмножини S з X один в одного циклічним чином, одночасно фіксуючи (тобто відображаючи на себе) всі інші елементи X.

Пара множин, яка не має жодного спільного елемента називаються непересічними множинами. Наприклад, множина A={2,3} і множина B={4,5} є непересічними множинами. Але множини C={3,4,5} і {3,6,7} не є непересічними, оскільки множини C і D мають 3 як спільний елемент. Дізнайтеся більше про непересічний набір тут.