Advanced book on Mathematics Olympiad

776 Combinatorics and Probability

which follows from the deragements formula (see Section 6.2.4.). The probability that
exactlykmatches occur is

(

n

k

)

p(n−k)(n−k)!

n!

=

1

k!

p(n−k)=

1

k!

∑n−k

i= 0

(− 1 )i

i!

.

Denote byXthe number of matchings in thisn-card game. The expected value ofXis

E(X)=

∑n

k= 0

kP (X=k)=

∑n

k= 0

k

1

k!

∑n−k

i= 0

(− 1 )i

i!

=

∑n

k= 1

1

(k− 1 )!

∑n−k

i= 0

(− 1 )i

i!

,

because

P(X=k)=

1

k!

∑n−k

i= 0

(− 1 )i

i!

.

Let us computeE(X)differently. Set

Xi=

{

1 if there is a match at theith draw,

0 if there is no match at theith draw.

Then

E(X)=E(X 1 +···+Xn)=

∑n

i= 1

E(Xi)=n

1

n

= 1 ,

because

E(Xi)= 1 ·P(Xi= 1 )=

(n− 1 )!

n!

=

1

n

.

Combining the two, we obtain

∑n

k= 1

1

(k− 1 )!

∑n−k

i= 0

(− 1 )i

i!

= 1 ,

which proves the first identity. The proof of the second identity is similar. We have

E(X^2 )=E

⎛

⎝

(n

∑

i= 1

Xi

) 2 ⎞

⎠=

∑n

i= 1

E(X^2 i)+ 2

∑

i<j

E(XiXj).

But