Permutaatiot, Samassa syklissä

Tämä kahden samassa syklissä olo hoituu huomaamalla, että kun permutaatiot, jossa 1 ja 2 ovat samassa syklissä kerrotaan syklillä (12), kuvautuu ne sellaisiksi, jossa 1 ja 2 eivät ole samassa syklissä (sykli katkeaa: (12):ssa ykkönen menee kakkoseen ja kun sitten kerrotaan sillä syklillä, jossa 1 ja 2 ovat, niin siinähän lähdetään siis ykköstä kuvaamaan kakkosesta ja saavutaan ykköseen ennen kuin tullaan takaisin kakkoseen, joten kakkonen ei ole ykkösen syklissä).

Nämä kaksi joukkoa osittavat koko S_n:n ja ovat tämän bijektion (käänteiskuvaus kerrotaan (12)^{-1} = (12):lla eli itseasiassa itsensä käänteiskuvaus) nojalla yhtäsuuret, joten kysytynlaisia permutaatioita on n!/2.

Yleisempi kysymys "1,2,..., k samassa syklissä" voidaan ratkaista symbolisella metodilla.

Aluksi lemma:
Lemma1: d^n/dz^n (1/(1-z)) = n!/(1-z)^(n 1)

Kysytyt permutaatiot ovat k-boksattu tähtitulo Syklistä ja Permutaatioista.
Syklin EGF on log(1/(1-z)) ja permutaatioiden 1/(1-z)
Täten eksponentiaalisille generoiville funktioille (merkitään kysyttyjen lukujen EGF:ää A:lla) pätee

d^k/dz^k A(z) = d^k/dz^k {log(1/(1-z))} * 1/(1-z),

josta tulee Lemma1:n nojalla

d^k/dz A(z) = (k-1)! / (1-z)^(k 1)

Kerrotaan puolittain k:lla, jotta Lemma1:n nojalla nähdään, että

A(z) = 1/k * 1/(1-z).
Näin huomataan, koska 1/(1-z) enumeroi permutaatiot, että n-permutatioita, joissa 1, 2,..., k ovat samassa syklissä on n!/k kappaletta eli k:s osa kaikista.