Page 109 - MATINF Nr. 13-14

´
Rezolvarea problemelor date la concursul de admitere la Ecole Polytechnique, filiera MPI, sesiunea 2024 109

10. Avem
1 ≤ l 1 ≤ l 2 ≤ . . . ≤ l ω(σ) s , i l 1 + l 1 + . . . + l ω(σ) = n.

• Dac˘a ω (σ) = n, atunci l 1 = l 2 = . . . = l n = 1, deci σ are n puncte fixe, deci σ este
permutarea identic˘a. Prin urmare s (n, n) = 1.

• Dac˘a ω (σ) = 1, atunci l 1 = n, deci σ este un ciclu. Evident σ (1) 6= 1 s , i σ (1) = i 2 ∈
{2, . . . , n} . Dac˘
a
Å ã
1 i 2 . . . i n−1 i n
σ =
i 2 i 3 . . . i n 1
(nu am p˘astrat ordinea cresc˘atoare a elementelor de pe prima linie) atunci ˆıi putem asocia
ˆın mod unic permutarea
Å ã
i 2 . . . i n−1 i n
¯ σ =
i 3 . . . i n i 2
care este un ciclu din S n−1 . Prin urmare

s (n, 1) = (n − 1) · s (n − 1, 1)

= (n − 1) (n − 2) · s (n − 2, 1)
. . .

= (n − 1) (n − 2) . . . 2 · s (2, 1)
= (n − 1) !.

a
S˘ ar˘at˘am c˘ pentru 2 ≤ k ≤ n − 1 avem
a
s (n, k) = s (n − 1, k − 1) + (n − 1) s (n − 1, k) .

Pentru σ ∈ S n cu ω (σ) = k putem avea cazurile:

• σ (1) = 1, atunci
Ä ä
σ| ∈ S n−1 s , i ω σ| = k − 1,
{2,...,n} {2,...,n}
a
exist˘ s (n − 1, k − 1) astfel de cazuri.

• σ (1) 6= 1, atunci σ (1) = i ∈ {2, 3, . . . , n} . Dac˘a ˆın descompunerea lui σ ˆınlocuim ciclul
care cont , ine 1 s , i i,
Å ã
1 i i 2 . . . i p i p+1
,
1
i i 2 i 3 . . . i p+1
cu ciclul
Å ã
i i 2 . . . i p i p+1
,
i 2 i 3 . . . i p+1 i
obt , inem descompuerea unei permut˘ari ¯σ ∈ S n−1 cu ω (¯σ) = k. Exist˘a (n − 1) s (n − 1, k)
astfel de cazuri.
ˆ
In concluzie
s (n, k) = s (n − 1, k − 1) + (n − 1) s (n − 1, k) .