gen-define-the-twelvefold-way-and-give-one-short-worked-example-d715

Define the twelvefold way and give one short worked example.

# The Twelvefold Way The **twelvefold way** is a systematic classification of counting problems based on: - **N balls** being placed into **k boxes** - Whether balls are **distinguishable** or **indistinguishable** - Whether boxes are **distinguishable** or **indistinguishable** - What **restrictions** apply: any number per box, at most one per box, or at least one per box This creates 12 cases (3 restrictions × 2 ball types × 2 box types). ## Summary Table | Balls | Boxes | Any number | ≤ 1 per box | ≥ 1 per box | |-------|-------|------------|-------------|-------------| | Dist. | Dist. | k^n | k!/(k-n)! | k! S(n,k) | | Dist. | Indist. | Σ S(n,j) | 1 or 0 | S(n,k) | | Indist. | Dist. | C(n+k-1,n) | C(k,n) | C(n-1,k-1) | | Indist. | Indist. | p_k(n) | 1 or 0 | p(n,k) | *Note: S(n,k) = Stirling numbers of 2nd kind; p(n,k) = partitions of n into k parts* ## Worked Example **Problem:** How many ways can we distribute 4 distinguishable balls into 3 distinguishable boxes with at least one ball per box? **Solution:** - Balls: distinguishable - Boxes: distinguishable - Restriction: ≥ 1 per box Formula: **k! · S(n,k)** = 3! · S(4,3) S(4,3) = 6 (partitions of {1,2,3,4} into 3 non-empty subsets) Answer: **3! × 6 = 36 ways**