Page 107 - MATINF Nr. 13-14

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

s , i
Å ã
1 2
σ 2 = care este un ciclu, deci ω (σ 2 ) = 1.
2 1
Prin urmare
1 X 1 3
ω (σ) = · (2 + 1) = .
2! 2! 2
σ∈S 2
• Pentru n = 3, S 3 are

3 k Å ã
X (−1) 1 1 1 1
D 3 = 3! · = 3! · − + − = 2
k! 1 1 2 6
k=0
permut˘ari care nu au puncte fixe, anume

Å ã Å ã
1 2 3 1 2 3
σ 1 = s , i σ 2 = ;
2 3 1 3 1 2
ele sunt cicluri, deci
ω (σ 1 ) = ω (σ 2 ) = 1.
Apoi, S 3 are trei permut˘ari cu un singur punct fix, anume

Å ã Å ã Å ã
1 2 3 1 2 3 1 2 3
σ 3 = , σ 4 = s , i σ 5 = ;
1 3 2 3 2 1 2 1 3
fiecare se descompune ˆıntr-un punct fix s , i o transpozit , ie (care este un ciclu), deci

ω (σ 3 ) = ω (σ 4 ) = ω (σ 5 ) = 2.
ˆ
In fine, S 3 cont , ine o permutare cu trei puncte fixe,

Å ã
1 2 3
σ 6 = ,
1 2 3
pentru care
ω (σ 6 ) = 3.

Prin urmare
1 X 1 11
ω (σ) = · (2 · 1 + 3 · 2 + 1 · 3) = .
3! 3! 6
σ∈S 3
• Pentru n = 4, S 4 are

4 k Å ã
X (−1) 1 1 1 1 1
D 4 = 4! · = 4! · − + − + = 9
k! 1 1 2 6 24
k=0
permut˘ari care nu au puncte fixe. Acestea sunt:
Å ã
1 2 3 4
σ 1 = = 1 2 3 4 , cu ω (σ 1 ) = 2;
2 1 4 3
Å ã
1 2 3 4
σ 2 = , ciclu, cu ω (σ 2 ) = 1;
2 3 4 1