Svaku funkciju [inlmath]f\colon X\rightarrow X[/inlmath] za koju važi [inlmath]x=f\left(f\left(x\right)\right)[/inlmath] za svako [inlmath]x\in X[/inlmath] nazivamo
involucija. Lako se pokazuje da svaka involucija mora biti bijekcija. U algebri, svaku bijekciju skupa [inlmath]X[/inlmath] na njega samog nazivamo
permutacija skupa [inlmath]X[/inlmath]. Ispostavlja se da skup svih permutacija skupa [inlmath]X[/inlmath] zajedno sa operacijom kompozicije funkcija [inlmath]\circ[/inlmath] čini jednu grupu, koju nazivamo
simetrična grupa skupa [inlmath]X[/inlmath] i obeležavamo je sa [inlmath]\mathbb{S}_X[/inlmath] (ako je skup [inlmath]X[/inlmath] konačan i ima [inlmath]n[/inlmath] elemenata, tada koristimo oznaku [inlmath]\mathbb{S}_n[/inlmath], jer skupovi iste kardinalnosti imaju izomorfne simetrične grupe).
Ciklus [inlmath]\zeta[/inlmath] je permutacija takva da postoji niz [inlmath]x_1,\dots x_k[/inlmath] od [inlmath]k[/inlmath] različitih elemenata, za koji važi:
- [inlmath]\zeta\left(x_j\right)=x_{j+1}[/inlmath] za svako [inlmath]1\le j\le k-1[/inlmath],
- [inlmath]\zeta\left(x_k\right)=x_1[/inlmath],
- [inlmath]\zeta\left(x\right)=x[/inlmath] za sve [inlmath]x\notin\left\{x_1,\dots,x_k\right\}[/inlmath]
Ciklus [inlmath]\zeta[/inlmath] u tom slučaju označavamo sa [inlmath]\left(x_1\,x_2\,\cdots\,x_k\right)[/inlmath]. Na primer, za ciklus [inlmath]\zeta=\left(2\,4\,3\right)\in\mathbb{S}_4[/inlmath] važi [inlmath]\zeta\left(1\right)=1[/inlmath], [inlmath]\zeta\left(2\right)=4[/inlmath], [inlmath]\zeta\left(3\right)=2[/inlmath] i [inlmath]\zeta\left(4\right)=3[/inlmath].
Jedan od osnovnih rezultata o simetričnoj grupi [inlmath]\mathbb{S}_n[/inlmath] kaže da se svaka permutacija [inlmath]n[/inlmath] elemenata može napisati kao proizvod disjunktnih ciklusa. Uz pomoć ovog stava lako dolazimo do rešenja tvog problema. Naime, ti tražiš permutaciju [inlmath]f[/inlmath] skupa od [inlmath]n[/inlmath] elemenata za koju važi [inlmath]x=f\left(f\left(x\right)\right)[/inlmath] za svako [inlmath]x\in X[/inlmath], odnosno za koju važi [inlmath]f^2=f\circ f=\varepsilon[/inlmath] (gde je [inlmath]\varepsilon[/inlmath] jedinični element grupe [inlmath]\mathbb{S}_n[/inlmath]). Drugim rečima, ti tražiš sve elemente reda dva u grupi [inlmath]\mathbb{S}_n[/inlmath]. Po pomenutom stavu, tražena permutacija se može napisati kao proizvod disjunktnih ciklusa tj. [inlmath]f=\zeta_1\circ\zeta_2\circ\dots\circ\zeta_l[/inlmath]. Kako su ciklusi disjunktni, oni komutiraju međusobno (sama grupa [inlmath]\mathbb{S}_n[/inlmath] nije komutativna!) pa je [inlmath]f^2=\zeta_1^2\circ\zeta_2^2\circ\dots\circ\zeta_l^2[/inlmath]. Opet, pošto su navedeni ciklusi disjunktni, važi [inlmath]\zeta_1^2=\varepsilon[/inlmath], [inlmath]\zeta_2^2=\varepsilon[/inlmath], ..., [inlmath]\zeta_l^2=\varepsilon[/inlmath]. Iz ovoga dalje sledi da je svaki navedeni ciklus reda jedan ili dva, odnosno da je oblika [inlmath](x_1)[/inlmath] ili [inlmath]\left(x_1\,x_2\right)[/inlmath]. Cikluse reda jedan možemo ignorisati (jer su oni zapravo jedna ista permutacija - [inlmath]\varepsilon[/inlmath]), pa je dovoljno posmatrati samo cikluse reda dva. Tražena permutacija je u potpunosti određena sa izborom ciklusa reda dva, i obrnuto, svaki izbor disjunktnih ciklusa reda dva određuje jednu jedinstvenu permutaciju sa traženom osobinom. Tačno [inlmath]k[/inlmath] disjunktnih ciklusa možemo izabrati na
[dispmath]{n\choose2k}\frac{\left(2k\right)!}{k!2^k}={n\choose2k}\left(2k-1\right)!![/dispmath] načina ([inlmath]2k[/inlmath] elemenata biramo na [inlmath]n\choose2k[/inlmath] načina, a tih [inlmath]2k[/inlmath] elemenata možemo zatim rasporediti u parove na [inlmath]\left(2k\right)!/\left(k!2^k\right)[/inlmath] načina). U dekompoziciji permutacije iz grupe [inlmath]\mathbb{S}_n[/inlmath] može biti najviše [inlmath]\lfloor n/2\rfloor[/inlmath], a najmanje [inlmath]0[/inlmath] ciklusa reda dva, pa sumiranjem prethodnog izraza dobijamo konačan rezultat
[dispmath]\sum_{k=0}^{\lfloor n/2\rfloor}{n\choose2k}\left(2k-1\right)!!.[/dispmath]
Inače, broj koji tražiš je poznat kao
Telephone number. Na linkovanoj stranici možeš pročitati neke zanimljivosti o ovim brojevima (npr.
In the mathematics of chess, the telephone numbers count the number of ways to place [inlmath]n[/inlmath] rooks on an [inlmath]n\times n[/inlmath] chessboard in such a way that no two rooks attack each other (the so-called eight rooks puzzle), and in such a way that the configuration of the rooks is symmetric under a diagonal reflection of the board.)
Rešenje koje sam naveo je elegantno ako se poznaje teorija grupa. Ovo mi je prvo palo na pamet. Nisam istraživao dalje, i ne znam da li postoji neko elementarnije rešenje.