MATEMANIJA

Neka je [inlmath]X=\{1,2,3,4\}[/inlmath]. Koliko ima funkcija [inlmath]f\colon X\to X[/inlmath] koje zadovoljavaju jednakost [inlmath](f\circ f)(x)=x[/inlmath] za svako [inlmath]x[/inlmath] iz [inlmath]X[/inlmath]?

Pokušao sam da uprostim zadatak razmatrajući prvo [inlmath]X_1=\{a,b\}[/inlmath], [inlmath]X_2=\{c,d\}[/inlmath] i broj načina da [inlmath]\{1,2,3,4\}[/inlmath] rasporedim u ta dva skupa i izbrojim sve mogućnosti pa da dobijeni zbir saberem sa slučajem [inlmath]X_1=\{a\}[/inlmath], [inlmath]X_2=\{b,c,d\}[/inlmath].
Ako je [inlmath]X_1=\{a,b\}[/inlmath] postoje dve mogućnosti [inlmath]f_1(a)=a[/inlmath], [inlmath]f_1(b)=b[/inlmath] i [inlmath]f_2(a)=b[/inlmath], [inlmath]f_2(b)=a[/inlmath]. Kada te dve mogućnosti pomnožimo sa brojem mogućnosti rasporeda [inlmath]\{c,d\}[/inlmath] (takođe [inlmath]2[/inlmath]) i brojem odabira [inlmath]\{a,b\}[/inlmath] iz [inlmath]\{1,2,3,4\}[/inlmath] dobijem [inlmath]n=2\cdot2\cdot6=24[/inlmath].
S obzirom da je ukupan broj permutacija od [inlmath]4[/inlmath] elementa [inlmath]4!=24[/inlmath] jasno mi je da ovo nije pravilan početak... a prostim prebrojavanjem mogućih funkcija dobije se da je ukupan broj mogućih funkcija [inlmath]10[/inlmath].

S druge strane postavljam sebi, a i vama opštije pitanje:

Šta ukoliko je [inlmath]X=\{1,2,3,\ldots,n\}[/inlmath]. Koliko ima funkcija [inlmath]f\colon X\to X[/inlmath] koje zadovoljavaju jednakost [inlmath](f\circ f)(x)=x[/inlmath] za svako [inlmath]x[/inlmath] iz [inlmath]X[/inlmath]?

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.

Zahvaljujem na brzom odgovoru koji mi je, bez obzira što mi nije u potpunosti jasan ipak proširio vidike.
Rešenje elementarnog zadatka se svodi na to da se od četiri elementa:
1) svi preslikavaju u sebe. Ovde imamo
[dispmath]{4\choose4}=1[/dispmath] 2) dva se preslikavaju u sebe a dva se preslikavaju u svoj par,
[dispmath]{4\choose2}=6[/dispmath] 3) dva para se preslikavaju u svoj par
[dispmath]\frac{4\choose2}{2!}=3[/dispmath]
Za opšti slučaj rešenje je
ako je [inlmath]n[/inlmath] parno:
[dispmath]{n\choose n}+{n\choose2}+\frac{{n\choose2}{n-2\choose2}}{2!}+\frac{{n\choose2}{n-2\choose2}{n-4\choose2}}{3!}+\cdots+\frac{{n\choose2}{n-2\choose2}\cdots{2\choose2}}{\left\lfloor\frac{n}{2}\right\rfloor!}[/dispmath]
ako je [inlmath]n[/inlmath] neparno:
[dispmath]{n\choose n}+{n\choose2}+\frac{{n\choose2}{n-2\choose2}}{2!}+\frac{{n\choose2}{n-2\choose2}{n-4\choose2}}{3!}+\cdots+\frac{{n\choose2}{n-2\choose2}\cdots{3\choose2}}{\left\lfloor\frac{n}{2}\right\rfloor!}[/dispmath]

Pokazao bih to i grafičkim putem, koristeći čistu kombinatoriku.
Kao što je već rečeno, trivijalan slučaj tražene funkcije je [inlmath]f(x)=x[/inlmath], tj. svaki element se slika u samog sebe (slika levo).


Uslov [inlmath](f\circ f)(x)=x[/inlmath] zadovoljavaće i funkcija na slici u sredini, koja ima, da se slobodnije izrazim, jedan „ukršten par“, dok se svaki od preostalih elemenata slika u samog sebe.
Na slici desno imamo dva ukrštena para, takva funkcija takođe zadovoljava uslov.
Uslov će zadovoljavati svaka funkcija koja ima proizvoljan broj tako ukrštenih parova, pod uslovom da se svaki od onih elemenata koji ne pripadaju ukrštenim parovima slika u samog sebe.
Ukrštenih parova može biti najviše [inlmath]\frac{n}{2}[/inlmath] kada je [inlmath]n[/inlmath] parno, odnosno [inlmath]\frac{n-1}{2}[/inlmath] kada je [inlmath]n[/inlmath] neparno. Ili, u opštem slučaju (nezavisno od parnosti [inlmath]n[/inlmath]), može ih biti [inlmath]\left\lfloor\frac{n}{2}\right\rfloor[/inlmath], tj. celobrojni deo od [inlmath]\frac{n}{2}[/inlmath].

Nađimo sada broj funkcija kod kojih imamo [inlmath]k[/inlmath] ukrštenih parova (nakon toga ćemo pustiti sumu po [inlmath]k[/inlmath] da ide od [inlmath]0[/inlmath] do [inlmath]\left\lfloor\frac{n}{2}\right\rfloor[/inlmath], jer [inlmath]k[/inlmath] može uzeti sve ove vrednosti).
Prvi ukršteni par možemo odabrati na [inlmath]n\choose2[/inlmath] načina (kombinacije bez ponavljanja, jer od ukupno [inlmath]n[/inlmath] elemenata biramo neka [inlmath]2[/inlmath]). Nakon toga nam je ostalo [inlmath]n-2[/inlmath] elemenata od kojih biramo njih [inlmath]2[/inlmath] za drugi ukršteni par, prema tome, broj takvih načina je [inlmath]n-2\choose2[/inlmath]. Sledeći binomni koeficijent će biti [inlmath]n-4\choose2[/inlmath] itd..., a poslednji ([inlmath]k[/inlmath]-ti) binomni koeficijent biće [inlmath]n-2k+2\choose2[/inlmath]:
[dispmath]{n\choose2}{n-2\choose2}{n-4\choose2}\cdots{n-2k+2\choose2}[/dispmath] Množenjem ovih binomnih koeficijenata dobićemo [inlmath]k![/inlmath] puta veći rezultat od stvarnog broja odabira [inlmath]k[/inlmath] ukrštenih parova, jer smo za svaki od tih slučajeva računali sve njegove permutacije, kojih ima [inlmath]k![/inlmath]. Dakle, proizvod binomnih koeficijenata treba sada podeliti sa [inlmath]k![/inlmath] (slično odnosu varijacija bez ponavljanja i kombinacija bez ponavljanja):
[dispmath]\frac{{n\choose2}{n-2\choose2}{n-4\choose2}\cdots{n-2k+4\choose2}{n-2k+2\choose2}}{k!}[/dispmath] Binomne koeficijente sada napišimo preko njihove definicije:
[dispmath]\frac{\frac{n!}{\cancel{(n-2)!}2!}\frac{\cancel{(n-2)!}}{\cancel{(n-2-2)!}2!}\frac{\cancel{(n-4)!}}{\cancel{(n-4-2)!}2!}\cdots\frac{\cancel{(n-2k+4)!}}{\cancel{(n-2k+4-2)!}2!}\frac{\cancel{(n-2k+2)!}}{(n-2k+2-2)!2!}}{k!}=\frac{n!}{2^k(n-2k)!k!}[/dispmath] Prema tome, broj traženih funkcija iznosi
[dispmath]\enclose{box}{\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!}{2^k(n-2k)!k!}}[/dispmath] što je identično rezultatu koji je dobio ubavic, a što se može i pokazati ako izraz pod sumom malo transformišemo:
[dispmath]\frac{n!}{2^k(n-2k)!k!}=\frac{n!(2k)!}{2^k(n-2k)!(2k)!k!}={n\choose2k}\frac{(2k)!}{2^kk!}=[/dispmath][dispmath]={n\choose2k}\frac{\cancel{2k}(2k-1)\cancel{(2k-2)}(2k-3)\cancel{(2k-4)}\cdots\cancel6\cdot5\cdot\cancel4\cdot3\cdot\cancel2\cdot1}{\cancel{2k}\cdot\cancel{2(k-1)}\cdot\cancel{2(k-2)}\cdots\cancel{(2\cdot3)}\cdot\cancel{(2\cdot2)}\cdot\cancel{(2\cdot1)}}=[/dispmath][dispmath]={n\choose2k}(2k-1)(2k-3)\cdots5\cdot3\cdot1={n\choose2k}(2k-1)!![/dispmath]

Daniel je napisao: Prema tome, broj traženih funkcija iznosi
[dispmath]\enclose{box}{\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!}{2^k(n-2k)!k!}}[/dispmath] što je identično rezultatu koji je dobio ubavic, a što se može i pokazati ako izraz pod sumom malo transformišemo:
[dispmath]\frac{n!}{2^k(n-2k)!k!}=\frac{n!(2k)!}{2^k(n-2k)!(2k)!k!}={n\choose2k}\frac{(2k)!}{2^kk!}=[/dispmath][dispmath]={n\choose2k}\frac{\cancel{2k}(2k-1)\cancel{(2k-2)}(2k-3)\cancel{(2k-4)}\cdots\cancel6\cdot5\cdot\cancel4\cdot3\cdot\cancel2\cdot1}{\cancel{2k}\cdot\cancel{2(k-1)}\cdot\cancel{2(k-2)}\cdots\cancel{(2\cdot3)}\cdot\cancel{(2\cdot2)}\cdot\cancel{(2\cdot1)}}=[/dispmath][dispmath]={n\choose2k}(2k-1)(2k-3)\cdots5\cdot3\cdot1={n\choose2k}(2k-1)!![/dispmath]

Kada je [inlmath]k=0[/inlmath], tada je [inlmath]2k-1[/inlmath] negativno pa bih ga radije izbacio iz sume napisane u obliku koji je dao ubavic, dok je u obliku koji si ti uokvirio sasvim regularno da [inlmath]k[/inlmath] uzima sve vrednosti od [inlmath]0[/inlmath] do [inlmath]\left\lfloor\frac{n}{2}\right\rfloor[/inlmath]
[dispmath]\enclose{box}{1+\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}{n\choose2k}(2k-1)!!}[/dispmath]

Može i tako, ali je dvostruki faktorijel negativnih neparnih brojeva sasvim regularan.
Ako pođemo od rekurentne veze
[dispmath](n+2)!!=(n+2)n!![/dispmath] prebacivanjem [inlmath](n+2)[/inlmath] na levu stranu dolazimo do takođe rekurentne veze
[dispmath]n!!=\frac{(n+2)!!}{n+2}[/dispmath] i, uvrštavajući [inlmath]n=-1[/inlmath], dobijamo
[dispmath](-1)!!=1[/dispmath] Možemo uočiti da ovo nismo mogli primeniti na običan faktorijel negativnih celih brojeva, jer bismo već za [inlmath](-1)![/inlmath] u rekurentnoj vezi [inlmath]n!=\frac{(n+1)!}{n+1}[/inlmath] dobili nulu u imeniocu – što znači da faktorijel negativnih celih brojeva nije definisan.
Nulu u imeniocu bismo takođe dobili i da smo u [inlmath]n!!=\frac{(n+2)!!}{n+2}[/inlmath] uvrstili [inlmath]n=-2[/inlmath], što znači da ne postoje dvostruki faktorijeli parnih negativnih brojeva.