Practice Problems
Counting problems
1. How many ways are there to order 8 programs if p_3 must directly
follow p_2 which must directly follow p_1?
2. How many binary words of length 10 contain at least two 0's?
3. How many integers between 100 and 999 (inclusive) have distinct
digits?
4. A set contains 192 elements. Half of the elements are grouped
into groups of size 4, and the rest are grouped into groups of size 2. How
many groups are there?
5. How many necklaces can be made by using 10 round beads, all of a
different color?
6. In how many ways can k of n people be arranged in a circle where
the position of each person in the circle doesn't matter?
Combinatorial identities
1. We saw that C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n, where
we can think of C(n, i) as the number of ways we can select a set of i
objects (order irrelevant, without repetition). We can think of n^i
as the number of ways of selecting i objects with repetition where order matters.
Prove by induction that for n <> 1,
n^0 + n^1 + n^2 + ... + n^m = (n^(m+1) - 1)/(n - 1)
2. Prove
1*1! + 2*2! + ... + n*n! = (n+1)! - 1
by induction. Can you prove it combinatorially?
Recurrence relations