Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 68 ยท Counting

Balls into Boxes: The Twelvefold Way

Count the ways to place n balls into k boxes in all twelve cases (distinguishable or not, any, injective or surjective) using powers, binomials, Stirling and partition numbers.

A huge number of counting problems are the same problem in disguise: put n objects into k containers. Handing out candy to children, assigning tasks to servers, putting keys into hash buckets, splitting a class into study groups. They look different, but each is a case of "balls into boxes", and the answer depends on just three questions:

  1. Are the balls distinguishable (labeled) or identical?
  2. Are the boxes distinguishable or identical?
  3. What is the rule about the boxes: may a box be empty or hold many (any placement), must each box hold at most one ball (injective), or at least one ball (surjective)?

Two choices for each of the first two questions and three for the last gives 2 x 2 x 3 = 12 cases, known as the twelvefold way. This lesson fills in the whole table, explains why each formula is right, and checks all twelve by brute force. It builds on Permutations and Combinations and uses the Stirling and partition numbers from Advanced Counting.

The table

Let n be the number of balls and k the number of boxes. S(n, k) is a Stirling number of the second kind (ways to split n labeled items into k non-empty unlabeled groups), and P(n, j) is the number of partitions of the integer n into exactly j positive parts.

Balls Boxes Any placement At most one per box (injective) At least one per box (surjective)
distinguishable distinguishable k^n k!/(k-n)! k! S(n, k)
identical distinguishable C(n+k-1, k-1) C(k, n) C(n-1, k-1)
distinguishable identical S(n,1) + ... + S(n,k) 1 if n <= k, else 0 S(n, k)
identical identical P(n,1) + ... + P(n,k) 1 if n <= k, else 0 P(n, k)

Why each formula holds

Labeled balls, labeled boxes. Each ball independently picks one of k boxes: k^n ways. If no box may take two balls, the first ball has k choices, the next k - 1, and so on, giving k (k-1) ... (k-n+1). If every box must be used, you are counting surjections from n balls onto k boxes: split the balls into k non-empty groups (S(n, k) ways) and then decide which group goes into which labeled box (k! ways).

Identical balls, labeled boxes. Only the number of balls in each box matters, so you count solutions of x1 + ... + xk = n with xi >= 0. The stars and bars argument lays out n stars and k - 1 dividers in a row and chooses where the dividers go: C(n + k - 1, k - 1). If each box holds at most one ball, you just choose which n of the k boxes get a ball: C(k, n). If each box needs at least one, hand one ball to each box first and distribute the remaining n - k freely: C(n - k + k - 1, k - 1) = C(n - 1, k - 1).

Labeled balls, identical boxes. The boxes have no names, so only which balls are together matters: a set partition. With every box non-empty and exactly k boxes this is S(n, k) by definition. If boxes may stay empty, the number of non-empty boxes can be anything from 1 to k, so you add S(n, 1) + ... + S(n, k). Injective placement needs n <= k, and then there is exactly one way up to renaming boxes: every ball alone.

Identical balls, identical boxes. Now you are only recording how many balls each box has, ignoring which box is which: that is a partition of the integer n. Exactly k non-empty boxes gives partitions with exactly k parts, P(n, k); "at most k" parts sums P(n, j) over j. Injective: all ones, only possible if n <= k.

Python The twelve answers for n = 5 balls, k = 3 boxes

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.

Checking all twelve by brute force

Formulas deserve a sanity check. The program below enumerates every function from balls to boxes, merges the outcomes that count as "the same" under the rules, and compares the number of distinct outcomes with each formula for several small (n, k) pairs.

  • Labeled balls, labeled boxes: an outcome is the assignment itself.
  • Identical balls, labeled boxes: an outcome is the tuple of box counts.
  • Labeled balls, identical boxes: an outcome is the set of groups of balls.
  • Identical balls, identical boxes: an outcome is the sorted tuple of non-zero box counts.
Python Brute-force verification of the twelvefold way

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.

Using the table on real problems

  • Ten identical candies to four children, each child gets at least one? Identical balls, labeled boxes, surjective: C(9, 3) = 84. Without the "at least one" rule: C(13, 3) = 286.
  • Six different tasks to three servers, every server busy? Labeled balls, labeled boxes, surjective: 3! x S(6, 3) = 6 x 90 = 540.
  • Six students into three unnamed study groups, none empty? Labeled balls, identical boxes, surjective: S(6, 3) = 90. Note how it is the previous answer divided by 3!: unnaming the boxes divides surjections by k!.
  • Seven identical coins into three identical piles, none empty? Partitions of 7 into exactly 3 parts: 5 + 1 + 1, 4 + 2 + 1, 3 + 3 + 1, 3 + 2 + 2: P(7, 3) = 4.
  • Hash collisions: n keys into k buckets with no collisions is the injective case k!/(k-n)! out of k^n total assignments; the ratio is the basis of the birthday problem.

When a counting problem feels stuck, translate it: what are the balls, what are the boxes, which are distinguishable, and is there an empty or at-most-one rule? Matching it to one of the twelve cells usually gives the formula immediately.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In how many ways can 8 identical balls be put into 3 distinguishable boxes (empty boxes allowed)?

    Stars and bars: C(8 + 3 - 1, 3 - 1) = C(10, 2) = 45.
  2. 2. How many ways can 4 distinguishable balls go into 2 distinguishable boxes so that neither box is empty?

    Surjections: 2! x S(4, 2) = 2 x 7 = 14. Equivalently 2^4 - 2 = 14, removing the two assignments that leave a box empty.
  3. 3. Which count equals S(n, k)?

    S(n, k) splits labeled items into k non-empty groups with no labels on the groups, which is the labeled-balls, identical-boxes, surjective case.
  4. 4. How many ways can 6 identical balls fill 3 distinguishable boxes with at least one ball in each?

    C(n - 1, k - 1) = C(5, 2) = 10.
  5. 5. Why does 'identical boxes' divide the surjective labeled-ball count by k!?

    With every box non-empty, the k boxes in an arrangement are all different from each other, so removing their labels merges exactly k! labeled arrangements into one.

Summary

  • Counting problems about placing n objects into k containers split into 12 cases by whether balls and boxes are distinguishable and whether placement is unrestricted, injective or surjective.
  • The formulas use powers, falling factorials, binomial coefficients (stars and bars), Stirling numbers S(n, k) and integer partition numbers P(n, k).
  • Surjections onto labeled boxes are k! S(n, k); removing the box labels divides by k!.
  • A brute-force enumeration confirms every cell for small n and k.
  • Translate a word problem into balls and boxes, find its cell, and read off the answer.

Next: Advanced Counting goes deeper into derangements, Catalan numbers and generating functions.