br permutacija cikličkog tipa....dokaz?

[Gost]

kako dokazati kombinatorno da je broj permutacija pod n elemenata cikličkog tipa (c1, ., cn) jednak n!/{c1!*2^c2*(c2)!*...*n^cn*(cn)!}

[C]

općenito permutacija određenog cikl. tipa (kada se zapiše po ciklusima) izgleda ovako:


(*)(*)(**)(**)(**)..(**..n zvjezdica..**)
u gdje je broj zagrada sa točno k zvjezdica ck, jasno je da zvjezdica sve skupa ima n.
Brojeve od 1..n možemo razmjestiti u zagrade na n! načina.
Očito da je svaki od n! zapisa zapis neke pemutacije traženog cikličkog tipa. Ali više različitih zapisa opisuje istu permutaciju, Koliko?

Fiksirajmo neku permutaciju i pogledajmo na koliko je načina možemo zapisati da zapis bude gornjeg oblika:

1. poredak zagrada iste duljine nije bitan, jer je npr.
(1)(2)(3,4) i (2)(1)(3,4) zapis iste permutacije
od tuda faktor c1!*c2!*..*cn! u nazivniku
(ck je broj zagrada duljine k koji se pojavljuje u tom zapisu)

2. unutar jedne zagrade duljine k možemo elemente "rotirati" na k načina tako da uvijek prikazujemo isti ciklus
npr. (3 2 1) i (2 1 3) i (1 3 2) su zapisi istog ciklusa. To su ujedno svi zapisi tog ciklusa
od tuda faktor 1^c1*2^c2*...n^cn


HTH