Robert Bartoszynski - Probability and Statistical Inference

12 3.2.12 A regular die is tossed times. Find the probability that: (i) Each side turns up exactly once if . (ii) Each side turns up at least once if .

13 3.2.13 Find the number of three‐digit integers (i.e., integers between 100 and 999) that have all digits distinct. How many of them are odd?

14 3.2.14 Let be the probability that exactly two people in a group of have the same birthday, and let be the probability that everybody in the group has a different birthday. Show that

The permutations discussed in Section 3.2were ordered selections from a certain set. Often, these orders are irrelevant, as we are interested only in the total number of possible choices. Such choices are referred to as combinations .

Definition 3.3.1A subset of size selected from a set of size (regardless of the order in which this subset was selected) is called a combination of out of .

Theorem 3.3.1 The number of combinations of out of , , is given by

(3.8)

Proof By Theorem 3.2.5we have different permutations of out of elements. Each permutation determines the set of elements selected and their order. Consequently, permutations lead to the same combination, which proves ( 3.8).

The ratio appears in various contexts, and it is convenient to have a special symbol for it.

Definition 3.3.2The ratio

(3.9)

is called a binomial coefficient and is denoted by , to be read as “ choose .”

Using ( 3.3), we have

(3.10)

Observe, however, that ( 3.10) requires to be an integer, whereas in ( 3.9) can be any real number ( has to be an integer in both cases).

As an illustration, let us evaluate , which we will use later. We have

Multiplying the numerator and denominator by we get

(3.11)

In this section, we tacitly assume that is an integer with .

Observe also that the symbol makes sense for and , in view of the convention that . Thus, we have

(3.12)

for all integers and such that . For , we have , since there is only one empty set, and since only one set of size can be selected out of a set of size . Formula ( 3.12) gives correct values, namely