1.1 Principles

Here are three rules that come up all the time.

  • \(Pr(A \cup B) = Pr(A)+Pr(B) - Pr(AB)\). This rule generalizes to \(Pr(A \cup B \cup C)=Pr(A)+Pr(B)+Pr(C)-Pr(AB)-Pr(AC)-Pr(BC)+Pr(ABC)\).

  • \(Pr(A|B) = \frac{P(AB)}{P(B)}\)

  • If A and B are independent, \(Pr(A \cap B) = Pr(A)Pr(B)\), and \(Pr(A|B)=Pr(A)\).

Uniform distributions on finite sample spaces often reduce to counting the elements of A and the sample space S, a process called combinatorics. Here are three important combinatorial rules.

Multiplication Rule. \(|S|=|S_1 |⋯|S_k|\).

How many outcomes are possible from a sequence of 4 coin flips and 2 rolls of a die? \(|S|=|S_1| \cdot |S_2| \dots |S_6| = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 6 \cdot 6 = 288\).

How many subsets are possible from a set of n=10 elements? In each subset, each element is either included or not, so there are \(2^n = 1024\) subsets.

How many subsets are possible from a set of n=10 elements taken k at a time with replacement? Each experiment has \(n\) possible outcomes and is repeated \(k\) times, so there are \(n^k\) subsets.

Permutations. The number of ordered arrangements (permutations) of a set of \(|S|=n\) items taken \(k\) at a time without replacement has \(n(n-1) \dots (n-k+1)\) subsets because each draw is one of k experiments with decreasing number of possible outcomes.

\[_nP_k = \frac{n!}{(n-k)!}\]

Notice that if \(k=0\) then there is 1 permutation; if \(k=1\) then there are \(n\) permutations; if \(k=n\) then there are \(n!\) permutations.

How many ways can you distribute 4 jackets among 4 people? \(_nP_k = \frac{4!}{(4-4)!} = 4! = 24\)

How many ways can you distribute 4 jackets among 2 people? \(_nP_k = \frac{4!}{(4-2)!} = 12\)

Subsets. The number of unordered arrangements (combinations) of a set of \(|S|=n\) items taken \(k\) at a time without replacement has

\[_nC_k = {n \choose k} = \frac{n!}{k!(n-k)!}\]

combinations and is called the binomial coefficient. The binomial coefficient is the number of different subsets. Notice that if k=0 then there is 1 subset; if k=1 then there are n subsets; if k=n then there is 1 subset. The connection with the permutation rule is that there are \(n!/(n-k)!\) permutations and each permutation has \(k!\) permutations.

How many subsets of 7 people can be taken from a set of 12 persons? \(_{12}C_7 = {12 \choose 7} = \frac{12!}{7!(12-7)!} = 792\)

If you are dealt five cards, what is the probability of getting a “full-house” hand containing three kings and two aces (KKKAA)? \[P(F) = \frac{{4 \choose 3} {4 \choose 2}}{{52 \choose 5}}\]

Distinguishable permutations. The number of unordered arrangements (distinguishable permutations) of a set of \(|S|=n\) items in which \(n_1\) are of one type, \(n_2\) are of another type, etc., is

\[{n \choose {n_1, n_2, \dots, n_k}} = \frac{n!}{n_{1}! n_{2}! \dots n_{k}!}\]

How many ordered arrangements are there of the letters in the word PHILIPPINES? There are n=11 objects. \(|P|=n_1=3\); \(|H|=n_2=1\); \(|I|=n_3=3\); \(|L|=n_4=1\); \(|N|=n_5=1\); \(|E|=n_6=1\); \(|S|=n_7=1\).

\[{n \choose {n_1, n_2, \dots, n_k}} = \frac{11!}{3! 1! 3! 1! 1! 1! 1!} = 1,108,800\]

How many ways can a research pool of 15 subjects be divided into three equally sized test groups?

\[{n \choose {n_1, n_2, \dots, n_k}} = \frac{15!}{5! 5! 5!} = 756,756\]