Combinations

Consider a set D with n elements. A combination of size k from D is an (unordered) subset

{x₁, x₂, ..., x_k}

of D with k (distinct) elements (of course, k cannot be larger than n). A combination of size k from D is formed when k elements are chosen from D without replacement (and without regard to order). Note that for each combination of size k from D, there are k! distinct orderings of the elements of that combination. Each of these is a permutation of length k from D.

The first two exercises below will derive the number of combinations of size k from an n-element set; this number is denoted by C(n, k) or by

1. Use the multiplication principle to argue that

2. Use the result in Exercise 1 to show that

Bit Strings

A bit string is a sequence in which each of the coordinates is either 0 or 1.

3. Give a one-to-one correspondence between the collection of subsets of size k of an n-element set and the collection of bits strings of length n with exactly k ones. Hence the number of such bit strings is C(n, k).

Basic Properties

4. For each of the following, try to give a combinatorial proof (show that the left and right sides are two different ways of counting the same collection) and an algebraic proof, using the formula in Exercise 2.

1. C(n, 0) = C(n, n) = 1
2. C(n, k) = C(n, n - k)
3. C(n, k) = C(n - 1, k - 1) + C(n - 1, k)

5. Prove the binomial theorem: If a and b are real numbers and n is a positive integer, then

Because of the binomial theorem, the numbers C(n, j) are called binomial coefficients.

Additional Exercises

6. A club has 20 members; 12 are women and 8 are men. A committee of 6 members is to be chosen. How many different committees are possible if:

1. There are no other restrictions.
2. The committee must have 4 women and 2 men
3. The committee must have at least 2 women and at least 2 men.

Combinations are important in the Ball and Urn Experiment.

Combinatorics