Page 94 - MATINF Nr. 13-14

94 M.N. Popescu

Fie n un num˘ar natural nenul. Reamintim c˘a pentru orice permutare σ ∈ S n , exist˘a o
∗
descompunere unic˘a (pˆan˘a la o rearanjare) σ = c 1 c 2 . . . c ω(σ) , unde ω (σ) ∈ N s , i c 1 , . . . , c ω(σ)
sunt cicluri disjuncte avˆand respectiv lungimile l 1 ≤ l 2 ≤ . . . ≤ l ω(σ) , cu l 1 + l 2 + . . . + l ω(σ) = n.
ˆ a
In particular, atent , ion˘am c˘ sunt luate ˆın considerare s , i ciclurile c i de lungime 1, care corespund
punctelor fixe ale lui σ, caz ˆın care c i este o identitate.

De exemplu, dac˘a σ este permutarea identitate a mult , imii {1, . . . , n}, atunci ω (σ) = n s , i
l ω(σ) = 1. De asemenea, dac˘a σ este transpozit , ia (1, 2) a mult , imii {1, 2, 3}, atunci σ = c 1 ◦ c 2 ,
a
unde c 1 = (3) este identitate s , i c 2 = (1, 2), astfel c˘ ω (σ) = 2.
Obt , inem astfel o aplicat , ie ω : S n → N. Ne propunem s˘a demonstr˘am c˘a, ˆın medie, ω (σ)
este de ordinul lui ln (n), ˆıntr-un sens pe care ˆıl vom specifica.
Pentru un num˘ar natural k mai mic sau egal cu n, not˘am cu s (n, k) num˘arul de permut˘ari
σ ∈ S n astfel ˆıncˆat ω (σ) = k. Consider˘am apoi, pe spat , iul de probabilitate (S n , P (S n )) ˆınzestrat
cu probabilitatea uniform˘a, variabila aleatoare X n definit˘ de X n (σ) = ω (σ).
a
1 X
9. Calculat , i, pentru n ∈ {1, 2, 3, 4}, valoarea expresiei ω (σ).
n !
σ∈S n
10. Specificat , i s (n, n) s , i s (n, 1), apoi ar˘atat , i c˘a, pentru 2 ≤ k ≤ n − 1, avem

s (n, k) = s (n − 1, k − 1) + (n − 1) s (n − 1, k) .

Pentru σ ∈ S n , se pot distinge cazurile σ (1) = 1 s , i σ (1) 6= 1.
n−1 n
Y X
k
11. Stabilit , i c˘a, pentru orice num˘ar real x, (x + i) = s (n, k) x .
i=0 k=1
12. Demonstrat , i c˘a M [X n ] = ln (n) + γ + O 1 .
n→+∞ n
13. a. Demonstrat , i c˘a

n n n n
1 X X X 1 X 1
k (k − 1) s (n, k) = − .
n ! ij i 2
k=1 i=1 j=1 i=1

b. Deducet , i c˘a

!
n n n n
1 X 2 X X 1 X 1
k s (n, k) = M [X n ] + − .
n ! ij i 2
k=1 i=1 j=1 i=1
14. a. Demonstrat , i c˘a

Å ã
1 X 2 2 ln (n)
ω(σ) = (2γ + 1) ln (n) + c + ln (n) + O ,
n ! n→+∞ n
σ∈S n
pentru un c real ce trebuie specificat.

b. Demonstrat , i c˘a

1 X 2 Å ln (n) ã
(ω (σ) − ln (n)) = ln (n) + c + O .
n ! n→+∞ n
σ∈S n