Permutacje - problem

[ronek22]

Cześć,
Mam problem z dwoma zadankami:

1)
Wyznacz liczbę permutacji \(\displaystyle{ \pi}\) ze zbioru \(\displaystyle{ S_{6}}\), które spełniają \(\displaystyle{ \pi^2 = id, \pi \ne id}\).
Czy dobrze myślę, że \(\displaystyle{ \pi=id}\) tylko dla jednego wypadku?
Natomiast nie wiem jak się potęguje permutacje.

2)Permutacja \(\displaystyle{ \pi \in S_n}\) jest nazywana cykliczną, jeśli jej postać w notacji cyklicznej składa się z jednego cyklu długości \(\displaystyle{ n}\). Wykaż, że istnieje dokładnie \(\displaystyle{ (n-1)!}\) permutacji cyklicznych w zbiorze \(\displaystyle{ S_n}\).

Bardzo proszę o pomoc

[a4karo]

wsk. potęgowanie to mnożenie przez siebie

[ronek22]

Mnożenie = złożenie?

[Majeskas]

Czy dobrze myślę, że \(\displaystyle{ \pi=id}\) tylko dla jednego wypadku?

Bez wątpienia: napis \(\displaystyle{ \pi=\textrm{id}}\) oznacza, że \(\displaystyle{ \pi}\) jest permutacją identycznościową.

Natomiast nie wiem jak się potęguje permutacje.

Permutacje to funkcje, więc potęgowanie czy w ogóle mnożenie oznacza tutaj składanie ze sobą tych funkcji.

Żeby rozwiązać te zadania, trzeba mieć pewną wiedzę o permutacjach jako obiektach algebraicznych.

Ad 1) Każdą permutację można przedstawić w postaci iloczynu cykli rozłącznych. Wówczas rząd takiej permutacji to najmniejsza wspólna wielokrotność rzędów poszczególnych cykli. Rząd cyklu zaś to po prostu jego długość. Rozkład permutacji z \(\displaystyle{ S_6}\) może wyglądać różnie, ale można dość łatwo określić, jakie muszą być te cykle, żeby najmniejsza wspólna wielokrotność ich długości była równa \(\displaystyle{ 2}\). Po prostu permutacja ta musi się składać z samych cykli długości co najwyżej \(\displaystyle{ 2}\) (z których przynajmniej jeden musi mieć długość \(\displaystyle{ 2}\)). Możliwości są zatem następujące:
\(\displaystyle{ (a_1,a_2)(a_3)(a_4)(a_5)(a_6)}\)
\(\displaystyle{ (a_1,a_2)(a_3,a_4)(a_5)(a_6)}\)
\(\displaystyle{ (a_1,a_2)(a_3,a_4)(a_5,a_6)}\)

Permutacji pierwszego typu jest \(\displaystyle{ {6\choose2}}\) (wybieramy elementy \(\displaystyle{ a_1,a_2}\)), drugiego \(\displaystyle{ {6\choose2}\cdot{4\choose2}\cdot\frac12}\) (wybieramy elementy \(\displaystyle{ a_5}\) i \(\displaystyle{ a_6}\), następnie musimy rozdzielić zbiór pozostałych czterech elementów na dwa równoliczne podzbiory), a trzeciego \(\displaystyle{ {6\choose2}\cdot{4\choose2}\cdot\frac1{3!}}\) (podział zbioru sześcioelementowego na trzy równoliczne bloki).

Ad 2)
Sposób I. Weźmy dowolny napis \(\displaystyle{ (a_1,a_2,\ldots,a_n)}\). Każda permutacja, w której elementy sąsiednie będą takie same, to będzie ten sam cykl, np. \(\displaystyle{ (a_2,a_3,\ldots,a_n,a_1),(a_3,a_4,\ldots,a_n,a_1,a_2)}\) itd. Można wykonać \(\displaystyle{ n}\) takich przesunięć. To oznacza, że takich permutacji jest \(\displaystyle{ \frac{n!}{n}}\).
(Można by to sformalizować, wprowadzając na zbiorze \(\displaystyle{ S_n}\) relację równoważności, która będzie utożsamiała odpowiednie permutacje w taki sposób jak wyżej. Klasy abstrakcji tej relacji to będą cykle długości \(\displaystyle{ n}\) i każda z nich będzie mocy \(\displaystyle{ n}\)).

Sposób II. Skoro każde "przesunięcie" elementów w cyklu daje ten sam cykl, oznacza to, że miejsce wybranego elementu w cyklu jest nieistotne. Możemy więc np. ustalić, że cykl rozpoczyna się od \(\displaystyle{ a_1}\). Różne cykle będziemy teraz otrzymywać, permutując pozostałe \(\displaystyle{ n-1}\) elementów. Cykli jest więc \(\displaystyle{ (n-1)!}\).

Dobrą, poglądową interpretacją takich permutacji jest sadzanie \(\displaystyle{ n}\) ludzi przy okrągłym stole. Warto przyjrzeć się obu rozumowaniom na tym przykładzie.