Combinatorial Structures

The purpose of this section is to study several combinatorial structures that are of basic importance in probability.

Permutations

Consider a set

D

with

n

elements. A permutation of length

k

from

D

is an ordered sequence of

k

distinct elements of

D

Of course,

k

cannot be larger than

n

. Statistically, a permutation of length

k

from

D

corresponds to an ordered sample of size

k

chosen without replacement from the population

D

Derivation

Use the multiplication principle to show that the number of permutations of length $k$ from an $n$ element set is

n k n n 1 n k 1

Show that the number of permutations of length $n$ from the $n$ element set $D$ (these are called simply permutations of $D$ ) is

n n n n n 1 1

Show that

n k n n k

Note that the basic permutation formula is defined for every real number

n

and nonnegative integer

k

. 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

a

s

, and

j

, define

Note that

$a 0 j a j$
$a 1 j a j$ ,
$a 1 j a a 1 a j 1$ ,
$11 j j$ .

Combinations

Consider again a set

D

with

n

elements. A combinationof size

k

from

D

is an (unordered) subset of

k

distinct elements of

D

Again,

k

cannot be larger than

n

. Statistically, a combination of size

k

from

D

corresponds to an unordered sample of size

k

chosen without replacement from the population

D

. 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

Derivation

The number of combinations of size

k

from an

n

-element set is denoted by

n k

C n k

Use the multiplication principle and to show that

n k n k k

An algorithm for generating all permutations of size $k$ from $D$ is to first select a combination of size $k$ and then to select an ordering of the elements.
Thus, argue that $n k n k k$ .

The number

n k

is called a binomial coefficient. Note that the formula 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,

n k

is called the generalized binomial coefficient. Note that if

n

and

k

are positive integers and

k n

then

n k 0

. By convention, we will also define

n k 0

k 0

. This convention sometimes simplifies formulas.

Show that if $n$ and $k$ are nonnegative integers and $k n$ then

n k n k n k

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 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 $n 0 n n 1$

Give algebraic and combinatorial proofs of the identity

n k n n k

For the combinatorial argument, note that if you select a subset of size $k$ from a set of size $n$ , then you leave a subset of size $n k$ behind.

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

n k n 1 k 1 n 1 k

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 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 $a$ and $b$ are real numbers and $n$ is a positive integer, then

a b n k 0 n n k a k b n k

Give algebraic and combinatorial proofs of the following identity: if $n$ and $k$ are positive integers then

k n k n n 1 k 1

For the combinatorial argument, consider two procedures for selecting a committee of size $k$ from a group of $n$ persons, with one distinguished member of the committee as chair.

Select the committee from the population and then select a member of the committee to act as chair.
Select the chair of the committee from the population and then select $k 1$ other committee members from the remaining $n 1$ members of the population.

Give algebraic and combinatorial proofs of the following identity: if $m$ , $n$ , and $k$ are nonnegative integers, then

j 0 k m j n k j n m k

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 then sum over $j$ .

Give algebraic and combinatorial proofs of the following identity: if $n$ and $m$ are nonnegative integers and $n m$ then

j n m j n m 1 n 1

For the combinatorial argument, suppose that we pick a subset of size $n 1$ from the set $12 m$ . For $j n n 1 m$ , count the number of subsets in which the largest element is $j 1$ and sum over $j$ . 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 $m$ positive integers:

j 1 m j m 1 2 m 1 m 2

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 $n k$ .

Subsets of size $k$ from a set of $n$ elements.
Bit strings of length $n$ with exactly $k$ 1's.
Paths in the Galton board from $00$ to $n k$ .

Show that if $n$ and $k$ are nonnegative integers then

n k 1 k n k 1 k

Samples

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

D

contains

n

objects and we are interested in drawing a sample of

k

objects. Let's review what we know so far:

Unordered Samples With Replacement

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

Unordered samples of size $k$ chosen with replacement from a population $D$ of $n$ elements.
Distinguishable strings of length $n k 1$ from a two-letter alphabet (say $* /$ ) where * occurs $k$ times and / occurs $n 1$ times.
Nonnegative integer solutions of $x 1 x 2 x k k$ .

Show that each of the collections in Exercise 17 has $n k 1 k$ elements.

Summary of Sampling Formulas

The following table summarizes the formulas for the number of samples of size

k

chosen from a population of

n

elements, based on the criteria of order and replacement.

Multinomial Coefficients

Partitions of a Set

Sampling formulas
	With Order	Without Order
With Replacement	$n k$	$n k 1 k$
Without Replacement	$n k$	$n k$

Recall that the binomial coefficient

n j

is the number of subsets of size

j

from a set

S

n

elements. Note also that when we select a subset

A

of size

j

from

S

we effectively partition

S

into two disjoint subsets of sizes

j

and

n j

, namely

A

and

A

. A natural generalization is to partition

S

into a union of

k

distinct, pairwise disjoint subsets

S 1 S 2 S k

where

S i n i

for each

i 12 k

. Of course we must have

n 1 n 2 n k n

Use the multiplication rule to show that the number of such partitions is

n n 1 n n 1 n 2 n n 1 n k 1 n k n n 1 n 2 n k

Give an algebraic and a combinatorial argument for the identity

n k n k n k

Sequences

Consider now the set

T 12 k n

. Elements of this set are sequences of length

n

in which each coordinate is one of

k

values. Thus, these sequences generalize the bit strings of length

n

in the last section. Again, let

n 1 n 2 n k

be a sequence of nonnegative integers with

i 1 k n i n

Construct a one-to-one correspondence between the following collections:

Partitions of $S$ into pairwise disjoint subsets $S 1 S 2 S k$ where $S i n i$ for each $i 12 k$ .
Sequences in $12 k n$ in which $i$ occurs $n i$ times for each $i 12 k$ .

It follows that the number of sequences in the second part of the Exercise 21 is

Permutations with Indistinguishable Objects

Suppose now that we have $n$ object of $k$ different types, with $n i$ elements of type $i$ for each $i 12 k$ . Moreover, objects of a given type are considered identical. Construct a one-to-one correspondence between the following collections:

Sequences in $12 k n$ in which $i$ occurs $n i$ times for each $i 12 k$ .
Distinguishable permutations of the $n$ objects.

It follows that the number of permutations in the second part of the Exercise 22 is

The Multinomial Theorem

Give a combinatorial proof of the multinomial theorem. Or course, this theorem is the reason for the name of the coefficients.

x 1 x 2 x k n n 1 n 2 n k n 1 n 2 n k n n n 1 n 2 n k x 1 n 1 x 2 n 2 x k n k

Show that there are $n k 1 k 1$ terms in the multinomial expansion in the Exercise 23.

Computational Exercises

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.

Arrangements

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:

There are no other restrictions.
The men must sit together and the women must sit together.
The men must sit together.
The spouses in each married couple must sit together.

Suppose that $n$ people are to be seated at a round table. Show that there are $n 1$ 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:

There are no restrictions.
The books of each type must be together.
The math books must be together.

Find the number of distinct arrangements of the letters in each of the following words:

statistics
probability
mississippi
tennessee
alabama

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

Committees

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:

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

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.

Cards

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

q

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:

There are no restrictions.
The hand is a full house (3 cards of one kind and 2 of another kind).
The hand has 4 of a kind.
The cards are all in the same suit (so the hand is a flush or a straight flush).

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:

There are no restrictions.
The hand has exactly 4 spades.
The hand has exactly 4 spades and 3 hearts.
The hand has exactly 4 spades, 3 hearts, and 2 diamonds.

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:

The number of poker hands that are void in at least one suit.
The number of bridge hands that are void in at least one suit.

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

53644737765488792839237440000 5.36 28

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

52 8.0658 67

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.

Dice

Suppose that 5 distinct, standard dice are rolled and the sequence of scores recorded.

Find the number of sequences.
Find the number of sequences with the scores all different.

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

Polynomial Coefficients

Find the coefficient of $x 3 y 4$ in $2 x 4 y 7$ .

Find the coefficient of $x 5$ in $2 3 x 8$ .

Find the coefficient of $x 3 y 7 z 5$ in $x y z 15$ .

Generate Pascal's triangle up to $n 10$ .

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

In the $n k$ lottery, $k$ numbers are chosen without replacement from the set of integers from 1 to $n$ (where $k n$ of course). Order does not matter.

Find the number of outcomes in the general $n k$ lottery.
Explicitly compute the number of outcomes in the $446$ lottery (a common format).

In the Galton board game,

Move the ball from $00$ to $127$ along a path of your choice. Note the corresponding bit string and subset.
Generate the bit string $0011101001101$ . Note the corresponding subset and path.
Generate the subset $145101215$ . Note the corresponding bit string and path.
Generate all paths from $00$ to $53$ . How many paths are there?

A fair coin is tossed 10 times and the outcome is recorded as a bit string (where 1 denotes heads and 0 tails).

Find the number of outcomes with exactly 4 heads.
Find the number of outcomes with at least 8 heads.

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:

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

Find the number of integer solutions of $x 1 x 2 x 3 10$ in each of the following cases:

$x i 0$ for each $i$ .
$x i 0$ for each $i$ .

Explicitly compute each formula in the sampling table above when $n 10$ and $k 4$ .

Compute each of the following:

$53$
$1 2 4$
$1 3 5$

Compute each of the following:

$1 2 3$
$54$
$1 3 5$

Suppose that $n$ persons are selected and their birthdays noted.

Find the number of outcomes.
Find the number of outcomes with distinct birthdays.

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 $a b c d e f g h 12345678$ .

The rooks are distinguishable.
The rooks are indistinguishable.

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

Suppose that 10 kids are divided into two teams of 5 each for a game of basketball. In how many ways can this be done in each of the following cases:

The teams are distinguishable (for example, one team is labeled Alabama and the other team is labeled Auburn).
The teams are not distinguishable.

8. Combinatorial Structures

Permutations

Derivation

Combinations

Derivation

Basic Properties

Samples

Unordered Samples With Replacement

Summary of Sampling Formulas

Multinomial Coefficients

Partitions of a Set

Sequences

Permutations with Indistinguishable Objects

The Multinomial Theorem

Computational Exercises

Arrangements

Committees

Cards

Dice

Polynomial Coefficients