Exercises 467
- A six-person committee is to be chosen from 16 university students, (4 from each
class-first, second, third, and fourth years). Determine how many committees are
possible if:
(a) Each class is represented.
(b) No class has more than two representatives, and each class has at least one
representative.
- How many ways can an eight-person committee be chosen from a group of 10 new
members and 15 old members if the committee is composed of:
(a) Four members from each group
(b) More new members than old members
(c) At least two new members
- A string consisting of O's and 1's has even parity if 1 occurs an even number of times;
otherwise, the string has odd parity. How many strings of length n have even parity?
How many strings of length n have odd parity?
- A domino is made of two squares, each of which is marked with one, two, three, four,
five, or six spots or is left blank. A set of dominoes consists of dominoes with all
possible pairs showing in the two squares. How many different dominoes are there in
a set?
- A bridge hand consists of 13 cards dealt from the 52-card deck. Bridge involves four
players named North, East, South, and West. How many ways can the cards be dealt
so that the game can be played?
23. Prove Z•=o C(n, k)^2 = C(2n, n).
(a) Prove the identity using the fact that (1 + x)^2 n = (1 x)(1 + x)n.
(b) Give a combinatorial proof of the identity in part a.
(c) Find the number of 14-digit binary sequences for which the number of l's in the
first seven digits is the same as the number of O's in the last seven digits of the
sequence. Enumerate all such sequences of length six.
- Prove that n(n + 1)2n-2 = y=1 k^2 C(n, k).
- Sum 13 + 23 + + + m^3 using the fact that m^3 can be represented as
m^3 = aC(m, 3) + bC(m, 2) + cC(m, 1)
where a, b, and c are rational numbers. This problem should not be solved using a
proof by induction.
- Prove that 1.2+2.3+...+n-(n+l)-=n(n+1)(n+2)/3. This problem
should not be solved using a proof by induction.
- Prove that
1.2.3 +2.3.4+... +n. (n + 1) • (n +2) = n (n + 1) (n + 2)(n + 3)/4.
This problem should not be solved using a proof by induction.
28. Given that (2n)!/n! = 2(1 • 3 • 5 •... • (2n - 1)), conclude that 2 .6. 10.... • (4n -
6) • (4n - 2) = (n + 1)(n - 2)(n + 3)(n + 4)... (2n - 1)2n.
- Construct the first 10 rows of Pascal's triangle.
- Using the Binomial Theorem, expand:
(a) (x + y)
5
(b) (x + y)
6
- Expand (1 ± x)^8 using the Binomial Theorem.
