Math 475 Text: Brualdi, Introductory Combinatorics 5th Ed.

Prof: Paul Terwilliger

Selected solutions for Chapter 5

1. For an integer k and a real number n, we show

     
n n−1 n−1
= + .
k k−1 k

First assume k ≤ −1. Then each side equals 0. Next assume k = 0. Then each side equals
1. Next assume k ≥ 1. Recall

P (n, k) = n(n − 1)(n − 2) · · · (n − k + 1).

We have
 
n P (n, k) nP (n − 1, k − 1)
= = .
k k! k!

 
n−1 P (n − 1, k − 1) kP (n − 1, k − 1)
= = .
k−1 (k − 1)! k!

 
n−1 P (n − 1, k) (n − k)P (n − 1, k − 1)
= = .
k k! k!

The result follows.

2. Pascal’s triangle begins

1
1 1
1
1 2
1 3 1 3
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
· · ·

1
 n−k
P

3. Let Z denote the set of integers. For nonnegative n ∈ Z define F (n) = k∈Z k
.
The sum is well defined since finitely many summands are nonzero. We have F (0) = 1 and
F (1) = 1. We show F (n) = F (n − 1) + F (n − 2) for n ≥ 2. Let n be given. Using Pascal’s
formula and a change of variables k = h + 1,
X n − k 
F (n) =
k∈Z
k
X n − k − 1 X n − k − 1

= +
k∈Z
k k∈Z
k−1

X n−k−1  X n − h − 2

= +
k∈Z
k h∈Z
h
= F (n − 1) + F (n − 2).

Thus F (n) is the nth Fibonacci number.

4. We have

(x + y)5 = x5 + 5x4 y + 10x3 y 2 + 10x2 y 3 + 5xy 4 + y 5

and

(x + y)6 = x6 + 6x5 y + 15x4 y 2 + 20x3 y 3 + 15x2 y 4 + 6xy 5 + y 6 .

5. We have
7  
7
X 7
(2x − y) = 27−k (−1)k x7−k y k .
k=0
k

18


6. The coefficient of x5 y 13 is 35 (−2)13 5
. The coefficient of x8 y 9 is 0 since 8 + 9 6= 18.

7. Using the binomial theorem,

n  
n
X n k
n
3 = (1 + 2) = 2 .
k=0
k

Similarly, for any real number r,

n  
n
X n
(1 + r) = rk .
k=0
k

8. Using the binomial theorem,

n  
k n
X
n n
2 = (3 − 1) = (−1) 3n−k .
k=0
k

2
9. We have
n   n  
k n n−k n
X X
k n
(−1) 10 = (−1) (−1) 10k = (−1)n (10 − 1)n = (−1)n 9n .
k=0
k k=0
k

The sum is 9n for n even and −9n for n odd.

10. Given integers 1 ≤ k ≤ n we show

   
n n−1
k =n .
k k−1
Let S denote the set of ordered pairs (x, y) such that x is a k-subset of {1, 2, . . . , n} and y
is an element of x. We compute |S| in two ways. (i) To obtain an element (x, y) of
S there
are k choices for x, and for each x there are k choices for y. Therefore |S| = k nk
. (ii) To
n

obtain an element (x, y) of S there are n choices for y, and for each y there are n−1
k−1
choices
n−1


for x. Therefore |S| = n k−1 . The result follows.

11. Given integers n ≥ 3 and 1 ≤ k ≤ n. We show

         
n n−3 n−1 n−2 n−3
− = + + .
k k k−1 k−1 k−1
Let S denote the set of k-subsets of {1, 2, . . . , n}. Let S1 consist of the elements in S that
contain 1. Let S2 consist of the elements in S that contain 2 but not 1. Let S3 consist of
the elements in S that contain 3 but not 1 or 2. Let S4 consist P of the elements in S that do
not contain 1 or 2 or 3. Note that {Si }i=1 partition S so |S| = 4i=1 |Si |. We have
4

         
n n−1 n−2 n−3 n−3
|S| = , |S1 | = , |S2 | = , |S3 | = , |S4 | = .
k k−1 k−1 k−1 k
The result follows.

12. We evaluate the sum

n  2
X
kn
(−1) .
k=0
k

First assume that n = 2m + 1 is odd. Then for 0 ≤ k ≤ m the k-summand and the (n − k)-
summand are opposite. Therefore the sum equals 0. Next assume that n = 2m is even. To
evaluate the sum in this case we compute in two ways
the the coefficient of xn in (1−x2 )n . (i)
By the binomial theorem this coefficient is (−1)m 2m
m
. (ii) Observe (1 − x2 ) = (1 + x)(1 − x).
We have
n  
n
X n k
(1 + x) = x ,
k=0
k
n  
n
X n
(1 − x) = (−1)k xk .
k=0
k

3
By these comments the coefficient of xn in (1 − x2 )n is
n     X n  2
X n k n k n
(−1) = (−1) .
k=0
n − k k k=0
k

Therefore
n  2  
X
k n m 2m
(−1) = (−1) .
k=0
k m

13. We show that the given sum is equal to

 
n+3
.
k

The above binomial coefficient is in row n + 3 of Pascal’s triangle. Using Pascal’s formula,
write the above binomial coefficient as a sum of two binomial coeffients in row n + 2 of
Pascal’s triangle. Write each of these as a sum of two binomial coeffients in row n + 1 of
Pascal’s triangle. Write each of these as a sum of two binomial coeffients in row n of Pascal’s
triangle. The resulting sum is
       
n n n n
+3 +3 + .
k k−1 k−2 k−3

14. Given a real number r and integer k such that r 6= k. We show

   
r r r−1
= .
k r−k k

First assume that k ≤ −1. Then each side is 0. Next assume that k = 0. Then each side is
1. Next assume that k ≥ 1. Observe
 
r P (r, k) rP (r − 1, k − 1)
= = ,
k k! k!

and
 
r−1 P (r − 1, k) (r − k)P (r − 1, k − 1)
= = .
k k! k!

The result follows.

15. For a variable x consider

n  
n
X n
(1 − x) = (−1)k xk .
k=0
k

4
Take the derivative with respect to x and obtain
n  
n−1
X n
−n(1 − x) = (−1)k kxk−1 .
k=0
k

Now set x = 1 to get

n  
X n
0= (−1)k k.
k=0
k

The result follows.

16. For a variable x consider

n  
n
X n
(1 + x) = xk .
k=0
k

Integrate with respect to x and obtain

n  
(1 + x)n+1 X n xk+1
= +C
n+1 k=0
k k + 1

for a constant C. Set x = 0 to find C = 1/(n + 1). Thus

n  
(1 + x)n+1 − 1 X n xk+1
= .
n+1 k=0
k k + 1

Now set x = 1 to get

n  
2n+1 − 1 X n 1
= .
n+1 k=0
k k+1

17. Routine.

18. For a variable x consider

n  
n
X n
(x − 1) = (−1)n−k xk .
k=0
k

Integrate with respect to x and obtain

n  
(x − 1)n+1 X n xk+1
= (−1)n−k +C
n+1 k=0
k k+1

for a constant C. Set x = 0 to find C = (−1)n+1 /(n + 1). Thus

n  
(x − 1)n+1 − (−1)n+1 X n xk+1
= (−1)n−k .
n+1 k=0
k k+1

5
Now set x = 1 to get
n  
(−1)n X n 1
= (−1)n−k .
n+1 k=0
k k+1

Therefore
n  
1 X n 1
= (−1)k .
n + 1 k=0 k k+1

19. One readily checks

   
m m
2 + = m(m − 1) + m = m2 .
2 1
Therefore
n
X n
X
2
k = k2
k=1 k=0
n   X n  
X k k
= 2 +
2 1
k=0   k=0

n+1 n+1
= 2 +
3 2
(n + 1)n(2n + 1)
= .
6

20. One readily checks

     
3m m m
m =6 +6 + .
3 2 1
Therefore
n
X n
X
3
k = k3
k=1 k=0
n   n   n  
X k X k X k
= 6 +6 +
3 2 1
k=0  k=0   k=0

n+1 n+1 n+1
= 6 +6 +
4 3 2
2 2
(n + 1) n
=
4
 2
n+1
= .
2

6
21. Given a real number r and an integer k. We show
   
−r k r+k−1
= (−1) .
k k

First assume that k < 0. Then each side is zero. Next assume that k ≥ 0. Observe
 
−r (−r)(−r − 1) · · · (−r − k + 1)
=
k k!
r(r + 1) · · · (r + k − 1)
= (−1)k
 k!

k r + k − 1
= (−1) .
k

22. Given a real number r and integers k, m. We show

     
r m r r−k
= .
m k k m−k

First assume that m < k or k < 0. Then each side is zero. Next assume that 0 ≤ k ≤ m.
Observe
  
r m r(r − 1) · · · (r − m + 1) m!
=
m k m! k!(m − k)!
r(r − 1) · · · (r − m + 1)
=
k!(m − k)!
r(r − 1) · · · (r − k + 1) (r − k)(r − k − 1) · · · (r − m + 1)
=
k! (m − k)!
  
r r−k
= .
k m−k

24


23. (a) 10
.
9 15



(b) 4 6
.
9

9
6

(c) 4 3 3
.
9 15 9



9
6

(d) 4 6
− 4 3 3
.

24. The number of walks of length 45 is equal to the number of words of length 45 involving
10 x’s, 15 y’s, and 20 z’s. This number is
45!
.
10! × 15! × 20!

7
25. Given integers m1 , m2 , n ≥ 0. Show
n     
X m1 m2 m1 + m2
= .
k=0
k n−k n

Let A denote a set with cardinality m1 +m2 . Partition A into subsets A1 , A2 with cardinalities
m1 and m2 respectively. Let S denote the set of n-subsets of A. We compute |S| in two
ways. (i) By construction
 
m1 + m2
|S| = .
n

(ii) For 0 ≤ k ≤ n let the set Sk consist of the elementsP in S whose intersection with A1
has cardinality k. The sets {Sk }k=0 partition S, so |S| = nk=0 |Sk |. For 0 ≤ k ≤ n we now
n

compute |Sk |. To do this we construct an element x ∈ Sk via the following 2-stage procedure:

stage to do # choices

m1


1 pick x ∩ A1 k

m2


2 pick x ∩ A2 n−k

m2
|Sk | is the product of the entries in the right-most column above, which comes
The number
m1
to k n−k . By these comments
n   
X m1 m2
|S| = .
k=0
k n − k

The result follows.

26. For an integer n ≥ 1 show

n       
X n n 1 2n + 2 2n
= − .
k=1
k k − 1 2 n + 1 n

Using Problem 25,

n    n   
X n n X n n
=
k=1
k k−1 k=0
k k−1
n   
X n n
=
k=0
k n+1−k
 
2n
=
n+1
   
1 2n 1 2n
= + .
2 n−1 2 n+1

8
It remains to show
       
1 2n 1 2n 1 2n + 2 2n
+ = − .
2 n−1 2 n+1 2 n+1 n
This holds since
         
2n 2n 2n 2n + 1 2n + 1
+2 + = +
n−1 n n+1 n n+1
 
2n + 2
= .
n+1

27. Given an integer n ≥ 1. We show

n  
n−2
X
2 n
n(n + 1)2 = k .
k=1
k

Let S denote the set of 3-tuples (s, x, y) such that s is a nonempty subset of {1, 2, . . . , n}
and x, y are elements (not necessarily distinct) in s. We compute |S| in two ways. (i)
Call an element (s, x, y) of S degenerate whenever x = y. Partition S into subsets S + , S −
with S + (resp. S − ) consisting of the degenerate (resp. nondegenerate) elements of S. So
|S| = |S + | + |S − |. We compute |S + |. To obtain an element (s, x, x) of S + there are n choices
for x, and given x there are 2n−1 choices for s. Therefore |S + | = n2n−1 . We compute |S − |.
To obtain an element (s, x, y) of S − there are n choices for x, and given x there are n − 1
choices for y, and given x, y there are 2n−2 choices for s. Therefore |S − | = n(n − 1)2n−2 . By
these comments
|S| = n2n−1 + n(n − 1)2n−2 = n(n + 1)2n−2 .
(ii) For 1 ≤ k ≤ n let Sk denote the set ofP elements (s, x, y) in S such that |s| = k. The
sets {Sk }k=1 give a partition of S, so |S| =
nk=1 |Sk |. For 1 ≤ k ≤ n we compute |Sk |. To
n

obtain an element (s, x, y) of Sk there are
nk choices for s, and given s there are k 2 ways to
choose the pair x, y. Therefore |Sk | = k 2 nk . By these comments
n  
2 n
X
|S| = k .
k=1
k

The result follows.

28. Given an integer n ≥ 1. We show

n  2  
X n 2n − 1
k =n .
k=1
k n−1

Let S denote the set of ordered pairs (s, x) such that s is a subset of {±1, ±2, . . . , ±n} and
x is a positive element of s. We compute |S| in two ways.
(i) To obtain an element (s, x) of
S There are n choices for x, and given x there are 2n−1
n−1
choices for s. Therefore
 
2n − 1
|S| = n .
n−1

9
(ii) For 1 ≤ k ≤ n let Sk denote the set of elements (s, x) in S such
Pn that s contains exactly
n
k positive elements. The sets {Sk }k=1 partition S, so |S| =
k=1 |Sk |. For 1 ≤ k ≤ n
we compute |Sk |. To obtain an element (s, x) of Sk there are nk ways to pick the positive
n
= nk ways to pick the negative elements of s. Given s there are k



elements of s and n−k

2
ways to pick x. Therefore |Sk | = k nk . By these comments
n  2
X n
|S| = k .
k=1
k

The result follows.

29. The given sum is equal to

 
m2 + m2 + m3
.
n
To see this, compute the coefficient of xn in each side of

(1 + x)m1 (1 + x)m2 (1 + x)m3 = (1 + x)m1 +m2 +m3 .

In this computation use the binomial theorem.

30, 31, 32. We refer to the proof of Theorem 5.3.3 in the text. Let A denote an antichain
such that
 
n
|A| = .
bn/2c
For 0 ≤ k ≤ n let αk denote the number of elements in A that have size k. So
n  
X n
αk = |A| = .
k=0
bn/2c

As shown in the proof of Theorem 5.3.3,

n
X αk
n ≤ 1,


k=0 k

with equality if and only if each maximal chain contains an element of A. By the above
comments
n n
n



bn/2c
−

k ≤ 0,
X
αk n
k=0 k

with equality if and only if each maximal chain contains an element of A. The above sum is
nonpositive but each summand is nonnegative. Therefore each summand is zero and the sum
is zero. Consequently (a) each maximal chain contains an element of A; (b) for 0 ≤ k ≤ n
either αk is zero or its coefficient is zero. We now consider two cases.

10
Case: n is even. We show that for 0 ≤ k ≤ n, αk = 0 if k 6= n/2. Observe that for 0 ≤ k ≤ n,
if k 6= n/2 then the coefficient of αk is nonzero, so αk = 0.
Case: n is odd. We show that for 0 ≤ k ≤ n, either αk = 0 if k 6= (n − 1)/2 or αk = 0
if k 6= (n + 1)/2. Observe that for 0 ≤ k ≤ n, if k 6= (n ± 1)/2 then the coefficient of αk
is nonzero, so αk = 0. We now show that αk = 0 for k = (n − 1)/2 or k = (n + 1)/2.
To do this, we assume that αk 6= 0 for both k = (n ± 1)/2 and get a contradiction. By
assumption A contains an element x of size (n + 1)/2 and an element y of size (n − 1)/2.
Define s = |x ∩ y|. Choose x, y such that s is maximal. By construction 0 ≤ s ≤ (n − 1)/2.
Suppose s = (n−1)/2. Then y = x∩y ⊆ x, contradicting the fact that x, y are incomparable.
So s ≤ (n − 3)/2. Let y 0 denote a subset of x that contains x ∩ y and has size (n − 1)/2.
Let x0 denote a subset of y 0 ∪ y that contains y 0 and has size (n + 1)/2. By construction
|x0 ∩ y| = s + 1. Observe y 0 is not in A since x, y 0 are comparable. Also x0 is not in A by the
maximality of s. By construction x0 covers y 0 so they are together contained in a maximal
chain. This chain does not contain an element of A, for a contradiction.
33. Define a poset (X, ≤) as follows. The set X consists of the subsets of {1, 2, . . . , n}.
For x, y ∈ X define x ≤ y whenever x ⊆ y. For n = 3, 4, 5 we display a symmetric chain
decomposition of this poset. We use the inductive procedure from the text.
For n = 3,
∅, 1, 12, 123
2, 23
3, 13.
For n = 4,
∅, 1, 12, 123, 1234
4, 14, 124
2, 23, 234
24,
3, 13, 134
34.
For n = 5,
∅, 1, 12, 123, 1234, 12345
5, 15, 125, 1235
4, 14, 124, 1245
45, 145
2, 23, 234, 2345
25, 235
24, 245
3, 13, 134, 1345
35, 135
34, 345.

11
 n n



34. For 0 ≤ k ≤ bn/2c there are exactly k
− k−1
symmetric chains of length n − 2k + 1.

35. Let S denote the set of 10 jokes. Each night the talk show host picks a subset of S for
his repertoire. It is required that

these subsets form an antichain. By Corollary 5.3.2 each
10
antichain has size at most 5 , which is equal to 252. Therefore the talk show host can
continue for 252 nights.

36. Compute the coefficient of xn in either side of

(1 + x)m1 (1 + x)m2 = (1 + x)m1 +m2 ,

In this computation use the binomial theorem.

37. In the multinomial theorem (Theorem 5.4.1) set xi = 1 for 1 ≤ i ≤ t.

38. (x1 + x2 + x3 )4 is equal to

x41 + x42 + x43 + 4(x31 x2 + x31 x3 + x1 x32 + x32 x3 + x1 x33 + x2 x33 )

+ 6(x21 x22 + x21 x23 + x22 x23 ) + 12(x21 x2 x3 + x1 x22 x3 + x1 x2 x23 ).

39. The coefficient is

10!
3! × 1! × 4! × 0! × 2!
which comes to 12600.

40. The coefficient is

9!
× 13 × (−1)3 × 2 × (−2)2
3! × 3! × 1! × 2!
which comes to −40320.

41. One routinely obtains the multinomial theorem (Theorem 5.4.1) with t = 3.

42. Given an integer t ≥ 2 and positive integers n1 , n2 , . . . , nt . Define n = ti=1 ni . We show

P

  t  
n X n−1
= .
n1 n2 · · · nt k=1
n1 · · · nk−1 nk − 1 nk+1 · · · nt

Consider the multiset

{n1 · x1 , n2 · x2 , . . . , nt · xt }.

Let P denote the set of permutations of this multiset. We compute |P | in two ways.
(i) We saw earlier that
 
n! n
|P | = = .
n1 ! × n2 ! × · · · × nt ! n1 n2 · · · nt

12
(ii) For 1 ≤ k ≤ t let Pk denote thePset of elements in P that have first coordinate xk . The
sets {Pk }tk=1 partition P , so |P | = tk=1 |Pk |. For 1 ≤ k ≤ t we compute |Pk |. Observe that
|Pk | is the number of permutations of the multiset

{n1 · x1 , . . . , nk−1 · xk−1 , (nk − 1) · xk , nk+1 · xk+1 , . . . , nt · xt }.

Therefore
 
n−1
|Pk | = .
n1 · · · nk−1 nk − 1 nk+1 · · · nt

By these comments
t  
X n−1
|P | = .
k=1
n1 · · · nk−1 nk − 1 nk+1 · · · nt

The result follows.

43. Given an integer n ≥ 1. Show by induction on n that

∞  
1 X n+k−1 k
= z , |z| < 1.
(1 − z)n k=0
k

The base case n = 1 is assumed to hold. We show that the above identity holds with n
replaced by n + 1, provided that it holds for n. Thus we show
∞  
1 X n+` `
= z, |z| < 1.
(1 − z)n+1 `=0
`

Observe
1 1 1
n+1
= n
(1 − z) (1 − z) 1 − z
X ∞   X∞ 
n+k−1 k h
= z z
k=0
k h=0
∞
X
= c` z `
`=0

where
       
n−1 n n+1 n+`−1
c` = + + + ··· +
0 1 2 `
 
n+`
= .
`

The result follows.

13
44. (Problem statement contains typo) The given sum is equal to (−3)n . Observe

(−3)n = (−1 − 1 − 1)n

 
X n
= (−1)n1 +n2 +n3
n1 +n2 +n3 =n
n1 n2 n3
 
X n
= (−1)n1 −n2 +n3 .
n +n +n =n
n1 n2 n3
1 2 3

Also

1 = (1 − 1 + 1)n
 
X n
= (−1)n2 .
n +n +n =n
n1 n2 n3
1 2 3

45. (Problem statement contains typo) The given sum is equal to (−4)n . Observe

(−4)n = (−1 − 1 − 1 − 1)n

 
X n
= (−1)n1 +n2 +n3 +n4
n1 +n2 +n3 +n4 =n
n n n
1 2 3 4 n
 
X n
= (−1)n1 −n2 +n3 −n4 .
n +n +n +n =n
n1 n2 n 3 n 4
1 2 3 4

Also

0 = (1 − 1 + 1 − 1)n
 
X n
= (−1)n2 +n4 .
n +n +n +n =n
n n n n
1 2 3 4
1 2 3 4

46. Observe
√
r
30
30 = 5
25
= 5(1 + z)1/2 z = 1/5,
∞  
X 1/2 k
= 5 z .
k=0
k
√
For n = 0, 1, 2, . . . the nth approximation to 30 is
n  
X 1/2 −k
an = 5 5 .
k=0
k

We have

14
 n an
0 5
1 5.5
2 5.475
3 5.4775
4 5.4771875
5 5.47723125
6 5.477224688
7 5.477225719
8 5.477225551
9 5.477225579

47. Observe
 1/3
1/3 10
10 = 2
8
= 2(1 + z)1/3 z = 1/4,
∞  
X 1/3 k
= 2 z .
k=0
k

For n = 0, 1, 2, . . . the nth approximation to 101/3 is

n  
X 1/3 −k
an = 2 4 .
k=0
k

We have
n an
0 2
1 2.166666667
2 2.152777778
3 2.154706790
4 2.154385288
5 2.154444230
6 2.154432769
7 2.154435089
8 2.154434605
9 2.154434708

48. We show that a poset with mn + 1 elements has a chain of size m + 1 or an antichain
of size n + 1. Our strategy is to assume the result is false, and get a contradiction. By
assumption each chain has size at most m and each antichain has size at most n. Let r
denote the size of the longest chain. So r ≤ m. By Theorem 5.6.1 the elements of the poset
can be partitioned into r antichains {Ai }ri=1 . We have |Ai | ≤ n for 1 ≤ i ≤ r. Therefore
r
X
mn + 1 = |Ai | ≤ rn ≤ mn,
i=1

15
for a contradiction. Therefore, the poset has a chain of size m + 1 or an antichain of size
n + 1.

49. We are given a sequence of mn + 1 real numbers, denoted {ai }mn i=0 . Let X denote the set
of ordered pairs {(i, ai )|0 ≤ i ≤ mn}. Observe |X| = mn + 1. Define a partial order ≤ on
X as follows: for distinct x = (i, ai ) and y = (j, aj ) in X, declare x < y whenever i < j and
ai ≤ aj . For the poset (X, ≤) the chains correspond to the (weakly) increasing subsequences
of {ai }mn mn
i=0 , and the antichains correspond to the (strictly) decreasing subsequences of {ai }i=0 .
By Problem 48, there exists a chain of size m + 1 or an antichain of size n + 1. Therefore the
sequence {ai }mni=0 has a (weakly) increasing subsequence of size m+1 or a (strictly) decreasing
subsequence of size n + 1.

50. (i) Here is a chain of size four: 1, 2, 4, 8. Here is a partition of X into four antichains:

8, 12
4, 6, 9, 10
2, 3, 5, 7, 11
1

Therefore four is both the largest size of a chain, and the smallest number of antichains that
partition X.

(ii) Here is an antichain of size six: 7, 8, 9, 10, 11, 12. Here is a partition of X into six chains:

1, 2, 4, 8
3, 6, 12
9
5, 10
7
11

Therefore six is both the largest size of an antichain, and the smallest number of chains that
partition X.

51. There exists a chain x1 < x2 < · · · < xt of size t ≥ 2 in the poset S such that x1 6< xt in
the poset R. Indeed we could take t = 2 and let x1 , x2 be elements of X such that x1 < x2
in S but x1 6< x2 in R. Pick a chain as above with t maximal. Define p = x1 and q = xt .
Then the pair (p, q) meets the requirements of the problem.

16