Advanced book on Mathematics Olympiad

Combinatorics and Probability 775

912.The total number of permutations is of coursen!. We will count instead the number
of permutations for which 1 and 2 lie in different cycles.

( If the cycle that contains 1 has lengthk, we can choose the otherk−1 elements in
n− 2
k− 1

)

ways from the set{ 3 , 4 ,...,n}. There exist(k− 1 )!circular permutations of these
elements, and(n−k)!permutations of the remainingn−kelements. Hence the total
number of permutations for which 1 and 2 belong to different cycles is equal to

∑n−^1

k= 1

(

n− 2

k− 1

)

(k− 1 )!(n−k)!=(n− 2 )!

∑n−^1

k= 1

(n−k)=(n− 2 )!

n(n− 1 )

2

=

n!

2

.

It follows that exactly half of all permutations contain 1 and 2 in different cycles, and so
half contain 1 and 2 in the same cycle. The probability is^12.
(I. TomescuProblems in Combinatorics, Wiley, 1985)

913.There are

(n

k

)

ways in which exactlyktails appear, and in this case the difference is
n− 2 k. Hence the expected value of|H−T|is

1

2 n

∑n

k= 0

|n− 2 k|

(

n

k

)

.

Evaluate the sum as follows:

1

2 n

∑n

m= 0

|n− 2 m|

(

n

m

)

=

1

2 n−^1

∑n/ 2 

m= 0

(n− 2 m)

(

n

m

)

=

1

2 n−^1

(n/ 2 

∑

m= 0

(n−m)

(

n

m

)

−

∑n/ 2 

m= 0

m

(

n

m

))

=

1

2 n−^1

(n/ 2 

∑

m= 0

n

(

n− 1

m

)

−

∑n/ 2 

m= 1

n

(

n− 1

m− 1

))

=

n

2 n−^1

(

n− 1

⌊n

2

⌋

)

.

(35th W.L. Putnam Mathematical Competition, 1974)

914.Usencards with the numbers 1, 2 ,...,non them. Shuffle the cards and stack them
with the numbered faces down. Then pick cards from the top of this pack, one at a time.
We say that a matching occurs at theith draw if the number on the card drawn isi. The
probability that no matching occurs is

∑n

i= 0

(− 1 )i

i!

=p(n),