468 CHAPTER 7 Counting and Combinatorics
- Expand (2x - y)^7 using the Binomial Theorem.
- In the expansion of (3x - 2y)^18 , what are the coefficients of:
(a) x
(^5) •y^13
(b) x
(^3) y15
- Expand (a + b + c)^2.
- Use the Binomial Theorem to prove that
n
3n - • C(n, k)2nk.
k=O
Write out what the identity says for n = 4.- Use the Binomial Theorem to prove that
n
2n = L(--)kC(n, k)3n-k.
k=O
Write out what the identity says for n = 4. - Theorem 4 in Section 7.9 proves that C(n, m) C(m, k) = C(n, k) C(n - k, m - k).
Use this result to prove that C(n, k) C(n - k, m) = C(n, m) C(n - m, k). - Prove the Diagonal Sum formula of Theorem 8 in Section 7.10.
- Prove that C(n, r) > C(n, r - 1) if r < n/2 for each row of Pascal's triangle.
- Prove that C (2n, n) + C (2n, n - 1) = (1/2) C (2n + 2, n + 1).
- Find a closed form for F"=1 kC(n, k).
- Count the number of triples (x, y, z) where z > max{x, y) and 1 < x, y, z < n + 1.
Deduce that 12 + 22 +... + n^2 = C(n + 1, 2) + 2C(n + 1, 3).
- Evaluate (1/4) 5= I k (6 - k) and deduce the number of points of intersection for
the diagonals of an octagon if no three diagonals meet at a point. - Find the following multinomials:
(a) The coefficient of x^2 y^3 z^5 in the expansion of (x + y + z)10
(b) The coefficents of x^3 y^4 z^2 and x^3 y^3 z^3 in the expansion of (3x +^2 y - z)9 - Show that there are ( 3 n + 1)/2 strings of length n consisting of the letters a, b, and x
in which a occurs an even number of times. - For n = 1, 2, 3 ... , write
[x]t = x(x - 1)(x - 2)-... (x - t + 1)
for 0 < t < n. We can represent [xIt as a linear combination of powers of x. The
coefficients for this expansion are denoted as s(n, t) and are known as the Stirling
numbers of the first kind. Thus, for any n, we can write
n
[X]t = s(n, t)xt
t=O
The numbers s(n, t) can be defined as s(n, 0) = 0 forn = 1, 2, 3. s(n, n) = 1 forn =0, 1,2,.... ; and
s(n,t)=s(n- 1,t-1)-(n-1)s(n- l,t)