Page 110 - MATINF Nr. 13-14

110 M.N. Popescu

11. Verific˘am relat , ia
n−1 n
Y X k
(x + i) = s (n, k) x
i=0 k=1
prin induct , ie dup˘a n.

• Pentru n = 1 avem

1−1 1
Y X k
(x + i) = x + 0 = x = s (1, 1) x = s (1, k) x .
i=0 k=1

• Presupunem relat , ia adev˘arat˘ pentru n − 1, adic˘a
a
(n−1)−1 n−1
Y X
k
(x + i) = s (n − 1, k) x .
i=0 k=1

• Verific˘am relat , ia pentru n. Folosind pasul de induct , ie s , i punctul 10 avem

 
n−1 (n−1)−1
Y Y
(x + i) =  (x + i) (x + n − 1)

i=0 i=0
" #
n−1
X
= s (n − 1, k) x k (x + n − 1)
k=1
n−1 n−1
X k+1 X k
= s (n − 1, k) x + (n − 1) s (n − 1, k) x
k=1 k=1
n n−1
X X
k
= s (n − 1, k − 1) x + (n − 1) s (n − 1, k) x k
k=2 k=1
n−1
X
= [s (n − 1, k − 1) + (n − 1) s (n − 1, k)] x k
k=2
n
+ s (n − 1, n − 1) x + (n − 1) s (n − 1, 1) x
n−1
X
k
n
= s (n, k) x + s (n, n) x + s (n, 1) x
k=2
n
X
k
= s (n, k) x .
k=1
12. Deoarece
{X n = k} = {σ ∈ S n : ω (σ) = k} ,

avem
card {X n = k} = s (n, k) ,
deci
card {X n = k} s (n, k)
P (X n = k) = = .
card S n n!