6.2 Binomial Coefficients and Counting Methods 309The second example comes from I. Tomescu’s bookProblems in Combinatorics
(Wiley, 1985).
Example.An alphabet consists of the lettersa 1 ,a 2 ,...,an. Prove that the number of all
words that contain each of these letters twice, but with no consecutive identical letters,
is equal to
1
2 n[
( 2 n)!−(
n
1)
2 ( 2 n− 1 )!+(
n
2)
22 ( 2 n− 2 )!−···+(− 1 )n 2 nn!]
.
Solution.The number of such words without imposing the restriction about consecutive
letters is
( 2 n)!
( 2 !)n=
( 2 n)!
2 n.
This is so because the identical letters can be permuted.
Denote byAithe number of words formed with thenletters, each occurring twice,
for which the two lettersaiappear next to each other. The answer to the problem is then
( 2 n)!
2 n
−|A 1 ∪A 2 ∪···∪An|.We evaluate|A 1 ∪A 2 ∪···∪An|using the inclusion–exclusion principle. To this end,
let us compute|Ai 1 ∩Ai 2 ∩···∩Aik|for some indicesi 1 ,i 2 ,...,ik,k≤n. Collapse the
consecutive lettersaij,j= 1 , 2 ,...,k. As such, we are, in fact, computing the number
of words made of the lettersa 1 ,a 2 ,...,anin whichai 1 ,ai 2 ,...,aikappear once and all
other letters appear twice. This number is clearly equal to
( 2 n−k)!
2 n−k,
since such a word has 2n−kletters, and identical letters can be permuted. There are
(n
k)
k-tuples(i 1 ,i 2 ,...,ik). We thus have
|A 1 ∪A 2 ∪···∪An|=∑
k∑
i 1 ,...,ik(− 1 )k−^1 |Ai 1 ∩Ai 2 ∩···∩Aik|=
∑
k(− 1 )k−^1(
n
k)
( 2 n−k)!
2 n−k,
and the formula is proved.
898.Letm, n, p, q, r, sbe positive integers such thatp<r<mandq<s<n.In
how many ways can one travel on a rectangular grid from( 0 , 0 )to(m, n)such
that at each step one of the coordinates increases by one unit and such that the path
avoids the points(p, q)and(r, s)?