Ch2: Combinatorial Probability

Key concepts

Definitions

• Permutation: arrangement in some order
• Ordered versus unordered samples: In ordered samples, the order of the elements in the sample matters; e.g., digits in a phone number, or the letters in a word. In unordered samples the order of the elements is irrelevant; e.g., elements in a subset, or lottery numbers.
• Samples with replacement versus samples without replacement: In the first case, repetition of the same element is allowed (e.g., numbers in a license plate); in the second, repetition not allowed (as in a lottery drawing—once a number has been drawn, it cannot be drawn again).

Formula's

• Number of permutations of n objects: n!
• Number of ordered samples of size r, with replacement, from n objects: $n^r$
• Number of ordered samples of size r, without replacement, from n objects:$$n(n-1)\cdots (n-r+1)=\frac{n!}{(n-r)!}={}_n{P}_r$$
• Number of unordered samples of size r, without replacement, from a set of n objects (= number of subsets of size r from a set of n elements) (combinations):$$(\genfrac{}{}{0ex}{}{n}{x})=\frac{{}_n{P}_r}{r!}=\frac{n!}{r!(n-r)!}=\frac{n(n-1)\dots (n-r+1)}{r!}$$
• Number of subsets of a set of n elements: $2^n$

Binomial coefficients

Definition

For n = 1, 2, . . . and k = 0, 1, . . . , n,

$$(\genfrac{}{}{0ex}{}{n}{x})=\frac{n!}{k!(n-k)!}=\frac{n(n-1)\dots (n-k+1)}{k!}$$

Combinatorial Interpretations

$(\genfrac{}{}{0ex}{}{n}{k})$ represents:

1. the number of ways to select k objects out of n given objects (in the sense of unordered samples without replacement);
2. the number of k-element subsets of an n-element set;
3. the number of n-letter HT sequences with exactly k H’s and n − k T’s.

Rules and properties

The product rule

If an experiment consists of performing k partial experiments and the $i^{th}$ partial experiment has $n_i$ possible outcomes $(i=1,\dots k)$, no matter what the results of the partial experiments are, then $n_1\times n_2\times \cdots \times n_k$ outcomes of the total experiment are possible.

The permutation rule

The number of orders or permutations (variations) in which k different things can be arranged is $k!$

Properties

When $A_1,A_2,\dots ,A_k$ are mutually exclusive events, then:

$$N\left(\prod _{i=1}^k{A}_i\right)=\sum _{i=1}^{k}N\left(A_i\right)$$

Hypergeometric formula

If we draw n times, at random and without replacement, from a set of $N$ balls, consisting of $R$ red and $N$ - $R$ white balls, the probability of event $A_k$, that we draw $k$ red (and $n$ - $k$ white) balls, is given by:

$$P(A_k)=\frac{(\genfrac{}{}{0ex}{}{R}{k})(\genfrac{}{}{0ex}{}{N-R}{n-k})}{(\genfrac{}{}{0ex}{}{N}{n})}$$