Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 36 ยท Permutations and Combinations

Permutations with Repeated Items (Multinomials)

Count distinct arrangements of words with repeated letters, split people into labelled groups and use multinomial coefficients, verified with Python.

So far all objects were distinct. What if some are identical? The word LEVEL has 5 letters, but swapping the two L's changes nothing. Counting 5! = 120 orders would over-count. This lesson shows how the division rule fixes that and introduces multinomial coefficients.

Words with repeated letters

Suppose an n-letter word has letters that repeat: letter 1 appears n1 times, letter 2 n2 times, and so on, with n1 + n2 + ... = n. Imagine labelling identical letters (L1, L2). All n! arrangements of labelled letters are distinct. But swapping labels among identical letters gives the same word, and each word appears n1! ยท n2! ยท ... times. Dividing:

n! / (n1! ยท n2! ยท ... ยท nr!)

This number is called a multinomial coefficient.

For LEVEL: L twice, E twice, V once. 5! / (2! 2! 1!) = 120 / 4 = 30.

Python Distinct arrangements of LEVEL

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.

MISSISSIPPI has 11 letters: M once, I four times, S four times, P twice, giving 11! / (1! 4! 4! 2!) = 34,650 distinct arrangements.

Binary strings with fixed weight

A string of n bits with exactly k ones is an arrangement of k identical ones and n-k identical zeros. The multinomial formula gives n! / (k! (n-k)!) = C(n, k). So the binomial coefficient is the two-letter case of the multinomial. It also confirms the lattice-path count from Bijections and Double Counting: a path with 3 rights and 2 ups is a word with those letters, so 5!/(3!2!) = 10.

Python Fixed-weight bit strings

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.

Splitting people into labelled groups

Divide 9 people into three labelled teams of sizes 4, 3 and 2. Pick team 1: C(9, 4) = 126. Then team 2 from the remaining 5: C(5, 3) = 10. The last team is forced: C(2, 2) = 1. Product: 126 x 10 = 1260. That equals 9! / (4! 3! 2!), again the multinomial.

If the teams are unlabelled and the same size, you must also divide by the number of orders of the equal-size teams. Splitting 6 people into 3 unlabelled pairs: the multinomial 6!/(2!2!2!) = 90 counts labelled pairs; divide by 3! = 6 to get 15.

Python Labelled and unlabelled teams

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 multinomial theorem

Just as (x + y)^n is controlled by binomial coefficients, (x1 + x2 + ... + xr)^n expands into terms with multinomial coefficients:

(x + y + z)^n = ฮฃ n! / (a! b! c!) ยท x^a y^b z^c, over all a + b + c = n.

For (x + y + z)^3 the coefficient of xyz is 3!/(1!1!1!) = 6, and of x^2 y is 3.

Python Multinomial coefficients with sympy

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.

flowchart LR
    A["n! labelled arrangements"] --> B["divide by n1! n2! ...<br/>(swap identical items)"]
    B --> C["multinomial coefficient"]

Dividing by the factorial of each repeat count removes the order among identical items.

Do not divide by n1! when the repeated objects are actually distinguishable (for example two different people with the same first name). Only truly interchangeable items collapse.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many distinct arrangements does the word BOOK have?

    4! / 2! = 12 because the two O's are identical.
  2. 2. How many 8-bit strings have exactly three 1s?

    C(8, 3) = 56.
  3. 3. What is the coefficient of x^2 y z in (x + y + z)^4?

    4! / (2! 1! 1!) = 12.
  4. 4. Split 8 people into two labelled groups of 4 and 4. How many ways?

    C(8, 4) = 70 for labelled groups. For unlabelled groups it would be 35.

Summary

  • Arrangements of a multiset: n! / (n1! n2! ... nr!).
  • The binomial coefficient is the special case of two letter types.
  • Labelled groups use multinomials; unlabelled equal groups need an extra division by the number of group orders.
  • The multinomial theorem expands powers of sums of many variables.

Next: Stars and Bars