Virtual Laboratories > Combinatorics > 1 2 [3] 4 5

3. Combinations

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).

1. Show that the following procedure generates all permutations of size k from D:

1. Select a combination of size k from D.
2. Select an ordering of the elements of the set in step (a).

2. Show that (n)_k = C(n, k)k!. Hint: Use Exercise 1 and the multiplication principle.

3. Show that C(n, k) = n! / [k!(n - k)!].

We will define C(n, k) = 0 if k < 0 or if k > n. This convention sometimes simplifies formulas.

4. A poker hand consists of 5 cards dealt without replacement and without regard to order from a deck of 52 cards.

1. Show that the number of poker hands is 2,598,960.
2. Find the probability that a random poker hand is a full house (3 cards of one kind and 2 of another kind).
3. Find the probability that a random poker hand has 4 of a kind.

The game of poker is studied in detail in the chapter on Games of Chance.

5. A bridge hand consists of 13 cards dealt without replacement and without regard to order from a deck of 52 cards.

1. Show that the number of bridge hands is 635,013,559,600.
2. Find the probability that a random bridge hand has 4 spades.
3. Find the probability that a random bridge hand has 4 spades and 3 hearts.
4. Find the probability that a random bridge had has 4 spades, 3 hearts and 2 diamonds.

6. Suppose that in a group of n people, each person shakes hands with every other person. Show that there are C(n, 2) different handshakes.

7. 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.

A hand of cards that has no cards in a particular suit is said to be void in that suit.

8. Find the number of poker hands that are void in at least one suit. Hint: Use the inclusion-exclusion formula.

9. In the N, n lottery, n numbers are chosen at random, without replacement from the population of integers from 1 to N (where n < N, of course). Order does not matter. The player who buys a lottery ticket is essentially trying to guess the outcome.

1. Show that the probability of winning (matching all n numbers) with a single ticket is 1 / C(N, n).
2. Compute the probability of winning a 6 / 44 lottery with a single ticket (this is a common format).

For more on this topic, see the section on Lotteries in the chapter on Games of Chance.

Bit Strings and the Galton Board

10. Show that there is a one-to-one correspondence between each pair of the following collections.

1. Subsets of size k from a set of n elements.
2. Bit strings of length n with exactly k 1's.
3. Paths in the Galton board from (0, 0) to (n, k).

Hence the number objects in each of these collection is C(n, k).

11. In the Galton board game, move the ball from (0, 0) to (12, 7) along a path of your choice. Note the corresponding bit string and subset.

12. In the Galton board game, generate the bit string 0011101001101. Note the corresponding subset and path.

13. In the Galton board game, generate the subset {1, 4, 5, 10, 12, 15}. Note the corresponding bit string and path.

14. In the Galton board game, generate all paths from (0, 0) to (5, 3). How many paths are there?

15. A fair coin is tossed 10 times.

1. Find the probability that there will be exactly 4 heads.
2. Find the probability that there will at least 8 heads.

16. An shipment contains 12 good and 8 defective items. A sample of 5 items is chosen at random. Find the probability that the sample contains exactly 3 good items.

17. Suppose that 8 rooks are randomly placed on a chessboard.

1. Show that the probability that no rook can capture another is 8! / C(52, 8).
2. Compare the answer and method to that of Problem 11 in the last section on permutations.

Basic Properties

For some of the identities in the exercises below, you are asked to give two proofs. An algebraic proof, of course, should be based on the formula in Exercise 3. A combinatorial proof is constructed by showing that the left and right sides of the identity are two different ways of counting the same collection.

18. Show that C(n, 0) = C(n, n) = 1

19. Give algebraic and combinatorial proofs of the identity

C(n, k) = C(n, n - k).

20. Give algebraic and combinatorial proofs of the identity: if n and k are non-negative integers and k n then 

C(n, k) = C(n - 1, k - 1) + C(n - 1, k).

Hint: For the combinatorial argument, fix an element of the set. Count the number of subsets of size k that contain the designated element and the number of subsets of size k that do not contain the designated element.

If each peg in the Galton board is replaced by the corresponding binomial coefficient, the resulting table of numbers is known as Pascal's triangle, named for Blaise Pascal. By Exercise 16, each interior number in Pascal's triangle is the sum of the two numbers directly above it.

21. Generate Pascal's triangle up to n = 10.

22. Give an algebraic and combinatorial proofs of the binomial theorem: if a and b are real numbers and n is a positive integer, then

(a + b)ⁿ = _{k = 0, ..., n} C(n, k) a^k b^{n - k}.

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

23. Find the coefficient of x⁵ in (2 + 3x)⁸.

24. Find the coefficient of x³y⁴ in (2x - 4y)⁷.

25. Show that jC(n, j) = nC(n - 1, j - 1) for n, j = 1, 2, ...

26. Give algebraic and combinatorial proofs of the following identity: if m, n, and k are positive integers, then

_{j = 0, ..., k} C(m, j) C(n, k - j) = C(n + m, k).

Hint: For the combinatorial argument, suppose that a committee of size k is chosen form a group of n + m persons, consisting of n women and m men. Count the number of committees with j men and k - j women and sum over j.

27. Give algebraic and combinatorial proofs of the following identity: if n and N are non-negative integers and n N then 

_{j = n, n + 1, ..., N} C(j, n) = C(N + 1, n + 1).

Hint: For the combinatorial argument, suppose that we pick a subset of size n + 1 from the set {1, 2, ..., N + 1}. For j = n, n + 1, ..., N, count the number of subsets in which the largest element is j + 1 and sum over j.

For an even more general version of the identity in Exercise 27, see the section on Order Statistics in the chapter on Finite Sampling Models. 

28. Establish the following special cases of the identity in the previous exercise.

1. The basic identity in Exercise 20. 
2. 1 + 2 + ··· + N = (N + 1)N / 2.

29. In the song The Twelve Days of Christmas, find the number of gifts given to the singer by her true love. Hint: Use the identity in Exercise 27 twice. 

Unordered Samples With Replacement

30. Show that there is a one-to-one correspondence between each pair of the following collections:

1. Unordered samples of size k chosen with replacement from a population D of n elements.
2. Distinguishable strings of length n + k - 1 from a two-letter alphabet (say {*, /}) where * occurs k times and / occurs n - 1 times.
3. Nonnegative integer solutions of x₁ + x₂ + ··· + x_n = k.

31. Show that each of the collections in Exercise 19 has C(n + k - 1, k) elements.

32 Suppose that 20 identical candies are distributed to 4 children. How many distributions are there if

1. There are no restrictions.
2. Each child must get at least one candy.

33. Suppose that 5 identical dice are rolled. How many outcomes are there?

34. How many integer solutions of x₁ + x₂ + x₃ = 10 are there if

1. x_i 0 for each i.
2. x_i > 0 for each i.

Summary of Sampling Formulas

The following table summarizes the formulas for the the number of samples of size k chosen from a population of n elements, based on the criteria of order and replacement.

35. Explicitly compute each formula in the table above when n = 10 and k = 4.

The Generalized Binomial Coefficient

The formula C(n, k) = (n)_k / k! makes sense for any real number n and nonnegative integer k, since this is true of the generalized permutation formula (n)_k. With this extension, C(n, k) is called the generalized binomial coefficient.

36. Compute each of the following

1. C(1 / 2, 3)
2. C(-5, 4)
3. C(-1 / 3, 5)

37. Show that if n and k are nonnegative integers then

C(-n, k) = (-1)^k C(n + k - 1, k).

In particular, note that C(-1, k) = (-1)^k.

Virtual Laboratories > Combinatorics > 1 2 [3] 4 5
Contents | Applets | Data Sets | Biographies | Resources | Keywords | ©