Combinations and Permutations

Multiplication Principle

Suppose that I want to purchase a tablet computer. I can choose either a large or a small screen; a 64GB, 128GB, or 256GB storage capacity, and a black or white cover. How many different options do I have?

Answer: $2 \times 3 \times 2 = 12$

Combination - order does not matter

• Repetition is Allowed: such as coins in your pocket (5,5,5,10,10)
• No Repetition: such as lottery numbers (2,14,15,27,30,33)

1. Combinations/Unordered with Repetition/Replacement (repetition/replacement allowed, order doesn't matter)

$\left( \frac {r + n - 1} {r} \right) = \frac {(r + n - 1)!} {r!(n-1)!}$

where $n$ is the number of things to choose from, and we choose $r$ of them

2. Combinations/Unordered without Repetition/Replacement (no repetition/replacement, order doesn't matter)

${n \choose k} = \frac {n!} {k!(n-k)!}$

${n \choose k} = {n \choose n - k}$

where $n$ is the number of things to choose from, and we choose $k$ of them

• I choose 33 cards from the standard deck of cards. What is the probability that these cards contain at least one ace?

$|S|={52 \choose 3}$

$|A^c|={48 \choose 3}$

$P(A) = (1 - {48 \choose 3}) / {52 \choose 3}$

• Suppose that I have a coin for which $P(H)=p$ and $P(T)=1-p$. I toss the coin 5 times.

  • What is the probability that the outcome is THHHHTHHHH?
  • What is the probability that I will observe exactly four heads and one tails?
  • What is the probability that I will observe exactly three heads and two tails?
  • If I toss the coin n times, what is the probability that I observe exactly k heads and n-k tails?

• Ten people have a potluck. Five people will be selected to bring a main dish, three people will bring drinks, and two people will bring dessert. How many ways they can be divided into these three groups?

We can solve this problem in the following way. First, we can choose 5 people for the main dish. This can be done in (105) ways. From the remaining 5 people, we then choose 3 people for drinks, and finally the remaining 2 people will bring desert. Thus, by the multiplication principle, the total number of ways is given by, ${10 \choose 5} {5 \choose 3} {2 \choose 2}=\frac{10!}{5! 5!} \cdot \frac{5!}{3! 2!} \cdot \frac{2!}{2! 0!}=\frac{10!}{5! 3! 2!}$

• I roll a die 18 times. What is the probability that each number appears exactly 3 times?

First of all, each sequence of outcomes in which each number appears 3 times has probability

$\left(\frac{1}{6}\right)^3 \times \left(\frac{1}{6}\right)^3 \times \left(\frac{1}{6}\right)^3 \times \left(\frac{1}{6}\right)^3 \times \left(\frac{1}{6}\right)^3 \times \left(\frac{1}{6}\right)^3 =\left(\frac{1}{6}\right)^{18}$

How many distinct sequences are there with three 1's, three 2's, ..., and three 6's? Each sequence has 18 positions which we need to fill with the digits. To obtain a sequence, we need to choose three positions for 1's, three positions for 2's, ..., and three positions for 6's. The number of ways to do this is given by the multinomial coefficient, ${18 \choose 3,3,3,3,3,3}=\frac{18!}{3! 3! 3! 3! 3! 3!}$.

Thus, the total probability is $\frac{18!}{(3!)^6} \left(\frac{1}{6}\right)^{18}$

Permutation (Position) - order does matter

• Repetition is Allowed: such as the lock above. It could be "333".
• No Repetition: for example the first three people in a running race. You can't be first and second.

1. Permutations/Ordered with Repetition/Replacement (repetition/replacement allowed, order matters)

$n^k$

where $n$ is the number of things to choose from, and we choose $k$ of them

• How many ways can you order 2 out of 3 items? $A = \{1, 2, 3\}, k = 2$

2. Permutations/Ordered without Repetition/Replacement (no repetition/replacement, order matters)

Factorial - how many ways to arrange $n$ items

$P^n_k = \frac {n!} {(n-k)!}$

where $n$ is the number of things to choose from, and we choose $k$ of them

• How many ways can order of 3 out of 16 pool balls?
• How many ways can first and second place be awarded to 10 people?