]>
The purpose of this section is to study several combinatorial structures that are of basic importance in probability.
Consider a set with elements. A permutation of length from is an ordered sequence of distinct elements of :
Of course, cannot be larger than . Statistically, a permutation of length from corresponds to an ordered sample of size chosen without replacement from the population .
Use the multiplication principle to show that the number of permutations of length from an element set is
Show that the number of permutations of length from the element set (these are called simply permutations of ) is
Show that
Note that the basic permutation formula is defined for every real number and nonnegative integer . This extension is sometimes referred to as the generalized permutation formula. Actually, we will sometimes need an even more general formula of this type (particularly in the section on Pólya's urn and the beta-Bernoulli process). For , , and , define
Note that
Consider again a set with elements. A combinationof size from is an (unordered) subset of distinct elements of :
Again, cannot be larger than . Statistically, a combination of size from corresponds to an unordered sample of size chosen without replacement from the population . Note that for each combination of size from , there are distinct orderings of the elements of that combination. Each of these is a permutation of length from .
The number of combinations of size from an -element set is denoted by or .
Use the multiplication principle and to show that
The number is called a binomial coefficient. Note that the formula makes sense for any real number and nonnegative integer , since this is true of the generalized permutation formula . With this extension, is called the generalized binomial coefficient. Note that if and are positive integers and then . By convention, we will also define if . This convention sometimes simplifies formulas.
Show that if and are nonnegative integers and then
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 first combination formula or the second combination formula. 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.
Show that
Give algebraic and combinatorial proofs of the identity
For the combinatorial argument, note that if you select a subset of size from a set of size , then you leave a subset of size behind.
Give algebraic and combinatorial proofs of the following identity: if and are non-negative integers and then
For the combinatorial argument, fix an element of the set. Count the number of subsets of size that contain the designated element and the number of subsets of size 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 the Exercise 9, each interior number in Pascal's triangle is the sum of the two numbers directly above it.
Give algebraic and combinatorial proofs of the binomial theorem: if and are real numbers and is a positive integer, then
Give algebraic and combinatorial proofs of the following identity: if and are positive integers then
For the combinatorial argument, consider two procedures for selecting a committee of size from a group of persons, with one distinguished member of the committee as chair.
Give algebraic and combinatorial proofs of the following identity: if , , and are nonnegative integers, then
For the combinatorial argument, suppose that a committee of size is chosen form a group of persons, consisting of women and men. Count the number of committees with men and women, and then sum over .
Give algebraic and combinatorial proofs of the following identity: if and are nonnegative integers and then
For the combinatorial argument, suppose that we pick a subset of size from the set . For , count the number of subsets in which the largest element is and sum over . For an even more general version of this identity, see the section on Order Statistics in the chapter on Finite Sampling Models.
Show that the identity in Exercise 9 is a special case of the identity in the Exercise 13, as is the following identity for the sum of the first positive integers:
Show that there is a one-to-one correspondence between each pair of the following collections. Hence the number objects in each of these collection is .
Show that if and are nonnegative integers then
In particular, note that
The experiment of drawing a sample from a population is basic and important. There are two essential attributes of samples: whether or not order is important, and whether or not a sampled object is replaced in the population before the next draw. Suppose now that the population contains objects and we are interested in drawing a sample of objects. Let's review what we know so far:
Thus, we have one case left to consider.
Show that there is a one-to-one correspondence between each pair of the following collections:
Show that each of the collections in Exercise 17 has elements.
The following table summarizes the formulas for the number of samples of size chosen from a population of elements, based on the criteria of order and replacement.
With Order | Without Order | |
---|---|---|
With Replacement | ||
Without Replacement |
Recall that the binomial coefficient is the number of subsets of size from a set of elements. Note also that when we select a subset of size from we effectively partition into two disjoint subsets of sizes and , namely and . A natural generalization is to partition into a union of distinct, pairwise disjoint subsets where for each . Of course we must have .
Use the multiplication rule to show that the number of such partitions is
This number is called the multinomial coefficient and is denoted by
Give an algebraic and a combinatorial argument for the identity
Consider now the set . Elements of this set are sequences of length in which each coordinate is one of values. Thus, these sequences generalize the bit strings of length in the last section. Again, let be a sequence of nonnegative integers with .
Construct a one-to-one correspondence between the following collections:
It follows that the number of sequences in the second part of the Exercise 21 is
Suppose now that we have object of different types, with elements of type for each . Moreover, objects of a given type are considered identical. Construct a one-to-one correspondence between the following collections:
It follows that the number of permutations in the second part of the Exercise 22 is
Give a combinatorial proof of the multinomial theorem. Or course, this theorem is the reason for the name of the coefficients.
Show that there are terms in the multinomial expansion in the Exercise 23.
In a race with 10 horses, the first, second, and third place finishers are noted. How many outcomes are there?
A license tag consists of 2 letters and 5 digits. Find the number of tags with the letters and digits are all different.
Eight persons, consisting of four married couples, are to be seated in a row of eight chairs. How many seating arrangements are there in each of the following cases:
Suppose that people are to be seated at a round table. Show that there are distinct seating arrangements. The mathematical significance of a round table is that there is no dedicated first chair.
Twelve books, consisting of 5 math books, 4 science books, and 3 history books are arranged on a bookshelf. Find the number of arrangements in each of the following cases:
Find the number of distinct arrangements of the letters in each of the following words:
A child has 12 blocks; 5 are red, 4 are green, and 3 are blue. In how many ways can the blocks be arranged in a line (blocks of a given color are considered identical)?
A club has 20 members; 12 are women and 8 are men. A committee of 6 members is to be chosen. Find the number of different committees in each of the following cases:
Suppose that a club with 20 members plans to form 3 distinct committees with 6, 5, and 4 members, respectively. In how many ways can this be done. Hint: the members not on a committee also form one of the sets in the partition.
A standard card deck can be modeled by the product set
where the first coordinate encodes the denomination or kind (ace, 2-10, jack, queen, king) and where the second coordinate encodes the suit (clubs, diamonds, hearts, spades). Sometimes we represent a card as a string rather than an ordered pair (for example ).
A poker hand consists of 5 cards dealt without replacement and without regard to order from a deck of 52 cards. Find the number of poker hands in each of the following cases:
The game of poker is studied in detail in the chapter on Games of Chance.
A bridge hand consists of 13 cards dealt without replacement and without regard to order from a deck of 52 cards. Find the number of bridge hands in each of the following cases:
A hand of cards that has no cards in a particular suit is said to be void in that suit. Use the inclusion-exclusion formula to find each of the following:
A bridge hand that has no honor cards (cards of denomination 10, jack, queen, king, or ace) is said to be a Yarborough, in honor of the Second Earl of Yarborough. Find the number of Yarboroughs.
A bridge deal consists of dealing 13 cards (a bridge hand) to each of 4 distinct players (generically referred to as north, south, east, and west) from a standard deck of 52 cards. Show that the number of bridge deals is
This staggering number is about the same order of magnitude as the number of atoms in your body, and is one of the reasons that bridge is a rich and interesting game.
Show that the number of permutations of the cards in a standard deck is
This number is enormous. Indeed if you perform the experiment of dealing all 52 cards from a well-shuffled deck, you may will generate a pattern of cards that has never been generated before, thereby ensuring your immortality. Actually, this experiment shows that, in a sense, rare events can be very common. By the way, Persi Diaconis has shown that it takes about seven standard riffle shuffles to thoroughly randomize a deck of cards.
Suppose that 5 distinct, standard dice are rolled and the sequence of scores recorded.
Suppose that in a group of people, each person shakes hands with every other person. Show that there are different handshakes.
In the lottery, numbers are chosen without replacement from the set of integers from 1 to (where of course). Order does not matter.
For more on this topic, see the section on Lotteries in the chapter on Games of Chance.
In the Galton board game,
A fair coin is tossed 10 times and the outcome is recorded as a bit string (where 1 denotes heads and 0 tails).
A shipment contains 12 good and 8 defective items. A sample of 5 items is selected. Find the number of samples that contain exactly 3 good items.
Suppose that 20 identical candies are distributed to 4 children. Find the number of distributions are there in each of the following cases:
Suppose that persons are selected and their birthdays noted.
Find the number of ways of placing 8 rooks on a chessboard so that no rook can capture another in each of the following cases. Note that the squares of a chessboard are distinct, and in fact are often identified with the product set .
In the song The Twelve Days of Christmas, find the number of gifts given to the singer by her true love. (Note that the singer starts afresh with gifts each day, so that for example, the true love gets a new partridge in a pear tree each of the 12 days.)