Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 57 ยท Probability Foundations

Counting: Permutations and Combinations

Learn the multiplication principle, factorials, permutations and combinations, and use them to compute probabilities of cards, lotteries and committees, verified in Python.

For equally likely outcomes, probability is a counting problem: how many outcomes are favorable, and how many are possible? Listing them works for dice, but nobody lists all five-card poker hands (2,598,960 of them). Counting rules give you the numbers without listing.

The multiplication principle

If a task has two steps, with m ways for the first and n ways for the second, there are m * n ways to do both. This extends to any number of steps.

A cafรฉ offers 3 sizes, 4 drinks and 2 milk options: 3 * 4 * 2 = 24 different orders. A 4-digit PIN with digits 0 to 9 and repetition allowed has 10^4 = 10,000 possibilities.

Factorials

The number of ways to arrange n distinct objects in a row is

n! = n * (n-1) * ... * 2 * 1

with 0! = 1. Three books can be arranged in 3! = 6 orders; ten books in 10! = 3,628,800. Factorials grow explosively, which is why brute-force listing breaks down so quickly.

Permutations: order matters

A permutation is an ordered selection of r items from n distinct items without repetition:

P(n, r) = n! / (n - r)!

How many ways can 3 medals (gold, silver, bronze) be awarded among 8 runners? P(8, 3) = 8 * 7 * 6 = 336. After the first medal there are 7 candidates left, then 6.

Combinations: order does not matter

A combination selects r items from n when only which items matter, not their order:

C(n, r) = n! / (r! * (n - r)!)

Choosing a 3-person committee from 8 people: C(8, 3) = 336 / 6 = 56. Each committee corresponds to 3! = 6 permutations (the same three people in a different order), so we divide by 6. The notation (n choose r) is read "n choose r".

Question type Order matters? Formula
Arrange all n Yes n!
Pick r in order Yes P(n, r)
Pick r as a group No C(n, r)
flowchart TD
    A["Choose r items from n"] --> B{"Does order matter?"}
    B -- "Yes" --> C["Permutation<br/>n! / (n-r)!"]
    B -- "No" --> D["Combination<br/>n! / (r!(n-r)!)"]

Ask one question: would swapping two chosen items give a different result?

Python Counting with Python's math module

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Permutations with repeated items

Arrange the letters of "STATISTICS": there are 10 letters with S three times, T three times, I twice, and A, C once. Dividing out the indistinguishable swaps:

10! / (3! * 3! * 2!) = 50,400

In general, n! / (n1! * n2! * ... ).

Probability by counting

Now combine counting with P(A) = favorable / total.

Example 1: a lottery. Pick 6 numbers from 49. There are C(49, 6) = 13,983,816 equally likely draws, so one ticket wins with probability 1 / 13,983,816.

Example 2: a poker hand. What is the probability that a 5-card hand contains all four aces? Choose the 4 aces (1 way) and one more card from the remaining 48: C(4,4) * C(48,1) = 48. So P = 48 / 2,598,960 โ‰ˆ 0.0000185.

Example 3: a committee. From 6 women and 4 men, a committee of 4 is chosen at random. The probability it has exactly 2 women is C(6,2) * C(4,2) / C(10,4) = 15 * 6 / 210 = 90/210 = 3/7. The numerator multiplies the independent choices of women and men.

Python Probabilities from counting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last table is a hypergeometric distribution, which you will meet formally in the chapter on common distributions.

Combinations and the binomial coefficients

C(n, r) are the numbers in Pascal's triangle, and they appear in the expansion of (a + b)^n. They are also the engine of the binomial distribution: the probability of exactly k successes in n independent trials with success probability p is C(n, k) * p^k * (1-p)^(n-k). You will use that on random variables.

Python Pascal's triangle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Using permutations when order does not matter (counting each group several times).
  • Forgetting that "with replacement" changes the formulas: ordered with repetition is n^r.
  • Treating the sum of two dice as equally likely instead of counting ordered pairs.
  • Dividing probabilities by total outcomes when the favorable count was derived under a different model (ordered vs unordered).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many 3-letter arrangements can be made from 5 distinct letters (no repeats)?

    P(5, 3) = 5 * 4 * 3 = 60.
  2. 2. In how many ways can a committee of 2 be chosen from 6 people?

    C(6, 2) = 6 * 5 / 2 = 15.
  3. 3. How many orders are there for 4 people in a queue?

    4! = 24.
  4. 4. A 3-digit code uses digits 0-9 and may repeat digits. How many codes are there?

    10 choices for each of the 3 positions: 10^3 = 1000.

Summary

  • The multiplication principle multiplies the number of choices at each step.
  • n! counts arrangements of n distinct objects.
  • Permutations count ordered selections, n!/(n-r)!; combinations count unordered ones, n!/(r!(n-r)!).
  • Probability of equally likely outcomes is favorable count divided by total count.
  • Python's math.comb, math.perm and itertools check your counting.

Next: Conditional Probability and Independence