Putem folosi urmatoarea reprezentare a lui S( n ) sub forma de arbore.
La inceput avem o radacina, (1).
Este singura permutare, cea identica, din S(1), grupul cu un element.
La primul pas facem trecerea de la S(1) la S(2).
La al doilea pas facem trecerea de la S(2) la S(3).
Si asa mai departe.
Fiecare trecere de la un S(k) la S(k+1) se face astfel:

Pelcam cu o permutare a lui S(k) pe care o scriem ca produs de cicli disjuncti, pe primul loc al fiecarui cicul fiind cel mai mic element din ciclu.
Dau cel mai bine un exemplu.

Pentru k=8 un ciclu posibil este (516)(28).
Il scriem complet si cum trebuie:
(165)(28)(3)(4)(7) .

Si acum inseram 9 "in toate locurile posibile".
Obtinem urmatoarele 9 permutari:

(1965)(28)(3)(4)(7)
(1695)(28)(3)(4)(7)
(1659)(28)(3)(4)(7)
(165)(298)(3)(4)(7)
(165)(289)(3)(4)(7)
(165)(28)(39)(4)(7)
(165)(28)(3)(49)(7)
(165)(28)(3)(4)(79)
(165)(28)(3)(4)(7)(9)

(Inserarile au fost facute dupa fiecare cifra a unui ciclu. Si ultima oara separat intr-un ciclu nou.)

Se demonstreaza usor ca in acest mod enumeram succesiv, recursiv, "toate permutarile".

Astfel, pentru problema data, o intrebare mai simpla este:

În câte permutari din S(8) sunt 1 si 2 in acelasi ciclu in scrierea unei permutari ca produs de cicli disjuncti?

[Citat] În câte permutari din S(8) sunt 1 si 2 in acelasi ciclu in scrierea unei permutari ca produs de cicli disjuncti?

Urmatorul cod clarifica in câte permutari se afla 1,2 in acelasi ciclu in scrierea...

G = SymmetricGroup( 8 )
contor = 0
for g in G:
contor += len( [ c for c in g.cycles() if c(1) != 1 and c(2) != 2 ] )
print contor

Si am obtinut:

20160
sage: G.order() / 2
20160

Deci in jumatate din cele 8! = 40320 cazuri 1 si 2 se afla in acelasi ciclu.

Desigur ca puteam sa scriem totul intr-o linie, daca asta e problema:

sage: sum( [ 1 for g in SymmetricGroup( 8 ) for c in g.cycles() if c(1) != 1 and c(2) != 2 ] )
20160


Si pentru câte permutari se afla 1,2,3 impreuna in acelasi ciclu?

sage: sum( [ 1 for g in SymmetricGroup( 8 ) for c in g.cycles() if c(1) != 1 and c(2) != 2 and c(3) != 3 ] )
13440
sage: SymmetricGroup( 8 ).order() / 3
13440


Incerc aici sa spun cum se construieste / cum se structureaza grupul de permutari cu 1, 2, 3, 4, ... elemente folosind ceea ce este "cel mai simplu lucru din informatica", anume un pom.

n=1.
Grupul S(1) are 1! = 1 element. Acest element se scrie sub forma de ciclu astfel:

(1)

Acest (1) este radacina pomului.

n=2
Grupul S(2) are 2! = 2 element. Aceste element se scriu sub forma de ciclu astfel:

(1)
+--- (12)
+--- (1)(2)

In primul caz l-am adaugat pe 2 imediat dupa 1 in acelasi ciclu.
In al doilea am deschis un ciclu nou pentru 2.

De la ultimul nivel inseram acum 3-ul unde putem (dupa 1 si 2) intr-un ciclu care exista deja sau intr-unul nou. Obtinem pomul cu cele 6 = 3! funze:

(1)
+--- (12)
+---+--- (132)
+---+--- (123)
+---+--- (12)(3)
+--- (1)(2)
+---+--- (13)(2)
+---+--- (1)(23)
+---+--- (1)(2)(3)

Sper ca e clar cum "inseram" 3-ul in structurile ciclice deja existente.
(Desigur ca distrugem structura de grup, nu asta ne intereseaza insa.)

Daca e sa scriem toate cele 4! = 24 de permutari inserând mai departe 4 in permutarile de mai sus... Nici o problema...


(1)
+--- (12)
+---+--- (132)
+---+---+--- (1432)
+---+---+--- (1342)
+---+---+--- (1324)
+---+---+--- (132)(4)
+---+--- (123)
+---+---+--- (1423)
+---+---+--- (1243)
+---+---+--- (1234)
+---+---+--- (123)(4)
+---+--- (12)(3)
+---+---+--- (142)(3)
+---+---+--- (124)(3)
+---+---+--- (12)(34)
+---+---+--- (12)(3)(4)
+--- (1)(2)
+---+--- (13)(2)
+---+---+--- (143)(2)
+---+---+--- (134)(2)
+---+---+--- (13)(24)
+---+---+--- (13)(2)(4)
+---+--- (1)(23)
+---+---+--- (14)(23)
+---+---+--- (1)(243)
+---+---+--- (1)(234)
+---+---+--- (1)(23)(4)
+---+--- (1)(2)(3)
+---+---+--- (14)(2)(3)
+---+---+--- (1)(24)(3)
+---+---+--- (1)(2)(34)
+---+---+--- (1)(2)(3)(4)

Si constructia merge asa mai departe.

Dupa cum se vede, daca 1,2,3 sunt "deja impreuna", ele nu vor mai fi separate prin acest procedeu de generare recursiva. Deci ajunge sa vedem probabilitatea ca 1,2,3 sa fie impreuna in acelasi ciclu la nivelul de generare al lui S(3).
In 2 din 6 cazuri se intampla acest lucru.

Probabilitatea ceruta este asadar 2/6 = 1/3 .

Mai sus am scris codul care verifica acest lucru pentru S(8).

N.B.
Problemele de matematica "s-au schimbat" de la o generatie la alta.
In noua generatie - desigur ca problemele din anii 1960, sa zicem, nu si-au pierdut din farmec - dar este greu sa convingem noua generatie de faptul ca se merita sa ne uitam pe ele.

In schimb, daca tot se "schimba paradigmele", este - se pare - de asemenea foarte greu sa convingem noua generatie ca problemele abordabile si care au un direct impact in viata de zi cu zi au un anumit farmec.

Singurul criteriu de a accepta o problema drept problema de luat in calcul (si de facut calculele pentru ea) este cel direct: daca problema s-a dat la o admitere (in ultimul an), atunci se admite, altfel nu.

Ii avertizez pe cei ce gândesc in acest mod ca acest tip de "snobism" nu duce la o dezvoltare a gândirii si a cunostintelor.

(Stiu desigur ca gustul meu in alegerea problemelor provoaca foarte probabil indigestii. Dar probleme pe alte gusturi sunt destule pe acest site. Si si ele provoaca indigestii...)