Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 68 ยท Counting

Permutations and Combinations

Count arrangements and selections with factorials, nPr and nCr, with and without repetition, and use math.perm, math.comb and itertools to verify.

Two questions sound alike but have very different answers. "How many ways can 3 runners finish on a podium out of 10?" and "How many ways can I pick 3 people out of 10 for a committee?" In the first, gold, silver and bronze are different, so order matters. In the second, the same three people form the same committee no matter how you list them, so order does not matter.

Counting ordered arrangements gives permutations; counting unordered selections gives combinations. Each comes in two flavors, depending on whether items may be reused, which gives four cases in total. This lesson builds each formula from the product rule and checks it against Python's math and itertools modules.

Two questions decide the formula

Does order matter? ABC and CBA differ, or they do not.
Can items repeat? Reuse allowed, or each item once.

Two yes/no answers give four counting formulas.

1 / 2

Factorials

The factorial of a non-negative integer n, written n!, is the product n ยท (n-1) ยท ... ยท 2 ยท 1, with 0! = 1. It counts the ways to line up n different objects: n choices for the first spot, n-1 for the second, and so on. Three books can be shelved in 3! = 6 orders. Factorials explode: 10! = 3,628,800 and 20! already exceeds 2 ยท 10ยนโธ.

The convention 0! = 1 is not arbitrary. There is exactly one way to arrange nothing (the empty arrangement), and it makes the formulas below work at the edges.

Permutations: order matters, no repetition

A permutation of r items chosen from n distinct items is an ordered arrangement. The first position has n options, the second n-1, down to n-r+1 for the r-th:

P(n, r) = n ยท (n-1) ยท ... ยท (n-r+1) = n! / (n-r)!

The podium example: P(10, 3) = 10 ยท 9 ยท 8 = 720. When r = n the result is simply n!.

Combinations: order does not matter, no repetition

If order does not matter, each unordered group of r items was counted r! times among the permutations, once for every way of ordering it. Dividing removes the duplicates:

C(n, r) = P(n, r) / r! = n! / (r! ยท (n-r)!)

The committee example: C(10, 3) = 720 / 6 = 120. This is also written n choose r and pronounced "n choose r". Two useful facts: C(n, r) = C(n, n-r) (choosing which items to take is the same as choosing which to leave) and C(n, 0) = C(n, n) = 1.

Python Factorials, nPr and nCr from scratch and from math

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.

Python's math.perm(n, r) and math.comb(n, r) are exact for any size of integer, so prefer them over the float-based math.factorial divisions. The pure functions above are for learning; they build huge intermediate values for big n.

Generating the objects, not just counting them

The itertools module produces the actual arrangements, which is invaluable for checking a formula on a small case:

  • permutations(items, r) yields ordered selections without repetition.
  • combinations(items, r) yields unordered selections without repetition.
  • product(items, repeat=r) yields ordered selections with repetition.
  • combinations_with_replacement(items, r) yields unordered selections with repetition.
Python The four cases side by side

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 output confirms 60, 125, 10 and 35 arrangements for the four cases. Only the last formula is new: counting unordered selections with repetition needs a trick, called stars and bars, which you will meet in Binomial Theorem and Pascal's Triangle.

Repetition allowed

Ordered with repetition: each of the r positions independently has n options, so the count is n^r. A 4-digit PIN has 10โด = 10,000 possibilities, and a 3-letter code over 26 letters has 26ยณ = 17,576.

Unordered with repetition (a multiset): choosing 3 scoops from 5 ice-cream flavors where repeats are fine, and only the count of each flavor matters, gives C(5 + 3 - 1, 3) = C(7, 3) = 35.

Permutations with identical items

When some items are identical, many arrangements coincide. Arranging the letters of BANANA (6 letters: one B, three A, two N): all 6! orders would be right if every letter were different, but swapping the three A's among themselves, and the two N's, changes nothing. Divide by those internal orderings:

6! / (1! ยท 3! ยท 2!) = 720 / 12 = 60

This is a multinomial coefficient; the same idea counts anagrams of any word.

Python Anagrams: brute force versus the formula

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.

Generalized permutations and combinations

Three extensions cover most remaining textbook problems: circular arrangements, identical objects placed into boxes, and arrangements with restrictions.

Circular arrangements

Seat n different people around a round table. If only the relative positions matter (rotating everyone gives the same arrangement), fix one person in place and arrange the others: (n - 1)! ways. If you may also flip the circle (beads on a bracelet), each arrangement is counted twice, so there are (n - 1)!/2 for n โ‰ฅ 3. Rotations of a necklace with repeated colors are subtler; those need Burnside's lemma.

Identical objects into distinct boxes (stars and bars)

Put r identical balls into k different boxes. Write the balls as stars and use k - 1 bars to separate the boxes: for example **|*||*** means 2, 1, 0 and 3 balls in four boxes. Every arrangement of r stars and k - 1 bars is one distribution, so there are

TEXT
C(r + k - 1, k - 1) = C(r + k - 1, r)

ways. This is also the number of non-negative integer solutions of xโ‚ + xโ‚‚ + ... + x_k = r. Variations:

  • At least one in each box (positive solutions): give each box one ball first, then distribute r - k freely: C(r - 1, k - 1).
  • Lower bounds x_i โ‰ฅ m_i: subtract the minimums from r first.
  • Upper bounds: count everything, then remove the violations with inclusion-exclusion.
  • Distinct balls into distinct boxes: each ball independently picks a box, k^r ways.

Restrictions: glue it or subtract it

  • "A and B must sit together": treat the pair as one block. For n people in a row, that is 2 ยท (n - 1)! (the factor 2 orders the pair inside the block).
  • "A and B must not sit together": count all and subtract the together cases, n! - 2 ยท (n - 1)!.
  • "No two vowels adjacent": place the consonants first, then choose gaps for the vowels.
Python Circular seatings, stars and bars, and restrictions

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.

Practice set

  1. How many ways can 8 people sit at a round table? 7! = 5040.
  2. A bakery has 5 pastry types. How many boxes of 12 pastries can you make? Stars and bars: C(12 + 4, 4) = 1820.
  3. How many ways to give 10 identical coins to 3 children if each child must get at least one? C(9, 2) = 36.
  4. How many words can you form from MISSISSIPPI? 11!/(1! 4! 4! 2!) = 34,650.

Choosing the right formula

Before reaching for a formula, ask two questions about what is being counted:

  1. Does rearranging a selection give a new outcome? If yes, count permutations. If no, count combinations.
  2. Can the same item be used more than once? If yes, use the repetition versions.

Some problems need both: "A committee of 3 from 10 people, then one of the three is chosen chair" is C(10, 3) ยท 3 = 360, which equals 10 ยท C(9, 2) = 360 if you choose the chair first. Getting the same answer by two routes is a strong sign that you counted correctly.

Another standard move is to count with order and then divide: poker hands (5 cards from 52) are C(52, 5) = 2,598,960, since the order in which cards arrive does not change the hand.

Python Mixed problems: committees, hands and passwords

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.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many ways can 4 different books be arranged on a shelf?

    All books are used and order matters, so the count is 4! = 4 x 3 x 2 x 1 = 24.
  2. 2. How many ways are there to choose a 4-person team from 9 people?

    Order does not matter, so use C(9, 4) = 9! / (4! 5!) = 126. The value 3,024 is P(9, 4), which counts ordered selections.
  3. 3. How many 3-digit codes can you make from the digits 0-9 if digits may repeat?

    Ordered selection with repetition: 10 options for each of 3 positions, so 10^3 = 1,000.
  4. 4. How many distinct arrangements are there of the letters in LEVEL?

    LEVEL has 5 letters with L twice and E twice, so the count is 5! / (2! 2!) = 120 / 4 = 30.
  5. 5. Which Python call counts the unordered selections of 2 items from 6, without repetition?

    math.comb(n, r) is n choose r. math.perm(6, 2) would give the ordered count 30, while math.comb(6, 2) gives 15.

Summary

  • n! counts the orderings of n different objects; P(n, r) = n!/(n-r)! counts ordered selections without repetition.
  • C(n, r) = n!/(r!(n-r)!) counts unordered selections without repetition, and C(n, r) = C(n, n-r).
  • With repetition, ordered selections number n^r and unordered ones number C(n+r-1, r).
  • Identical items shrink the count: divide n! by the factorials of the repeated counts (multinomial coefficient).
  • Decide first whether order matters and whether repetition is allowed, then confirm with math.perm, math.comb and itertools on a small case.

Next: Binomial Theorem and Pascal's Triangle, which explains where C(n, r) shows up when you expand powers.