Distributions: Stars & Bars and Integer Solutions

Study Sheet

Distributions: Stars & Bars and Integer Solutions

Competition counting & probability, Unit 3

Combinations with Repetition

Concept
The multiset counting formula

Suppose you want to choose nn items from kk types, where each type is available in unlimited supply and order does not matter. The number of ways is

( ⁣ ⁣(kn) ⁣ ⁣)=(n+k−1n)=(n+k−1k−1).\left(\!\!\binom{k}{n}\!\!\right)=\binom{n+k-1}{n}=\binom{n+k-1}{k-1}.

This counts multisets of size nn drawn from kk types. Unlike ordinary combinations (kn)\binom{k}{n}, repeats are allowed, so a type may be chosen more than once.

The key contrast to keep straight:

  • Permutations (nkn^k or k!/(k−n)!k!/(k-n)!): order matters.
  • Combinations (kn)\binom{k}{n}: order does not matter, no repeats.
  • Combinations with repetition (n+k−1n)\binom{n+k-1}{n}: order does not matter, repeats allowed.
Example
Choosing donuts

A shop sells 55 kinds of donuts. You buy a box of 88 donuts. How many different boxes are possible?

Solution. Here k=5k=5 types and n=8n=8 chosen, repeats allowed, order irrelevant. The count is

(8+5−18)=(128)=(124)=495.\binom{8+5-1}{8}=\binom{12}{8}=\binom{12}{4}=495.
Example
Nondecreasing sequences

How many nondecreasing sequences 1≤a1≤a2≤a3≤a4≤61\le a_1\le a_2\le a_3\le a_4\le 6 of length 44 are there?

Solution. A nondecreasing sequence is the same as a multiset of size 44 chosen from the 66 values {1,…,6}\{1,\dots,6\}: sorting a multiset gives exactly one such sequence. So the count is (4+6−14)=(94)=126\binom{4+6-1}{4}=\binom{9}{4}=126.

Tip

Tip. “How many ways to pick with repetition allowed, order not mattering” and “how many nondecreasing sequences” are the same problem. Spotting one form in disguise is half the battle.

Stars and Bars (identical items to distinct boxes)

Concept
The stars-and-bars picture

To distribute nn identical items among kk distinct boxes (any box may get zero), draw nn stars and k−1k-1 bars in a row. The bars split the stars into kk groups; group ii becomes the contents of box ii. Every arrangement of

⋆⋆⋯⋆⏟nand∣  ∣  ⋯  ∣⏟k−1\underbrace{\star\star\cdots\star}_{n}\quad\text{and}\quad\underbrace{\mid\;\mid\;\cdots\;\mid}_{k-1}

gives one distribution, so the number of distributions is

(n+k−1k−1)=(n+k−1n).\binom{n+k-1}{k-1}=\binom{n+k-1}{n}.

For example, ⋆⋆∣⋆∣∣⋆⋆⋆\star\star\mid\star\mid\mid\star\star\star with k=4k=4 boxes means box 11 gets 22, box 22 gets 11, box 33 gets 00, box 44 gets 33. There are n+k−1n+k-1 symbol positions; choose which k−1k-1 are bars.

Example
Identical candies to children

In how many ways can 1010 identical candies be given to 44 children (a child may get none)?

Solution. Distribute n=10n=10 identical items into k=4k=4 distinct boxes:

(10+4−14−1)=(133)=286.\binom{10+4-1}{4-1}=\binom{13}{3}=286.
Tip

Careful. Stars and bars requires the items to be identical and the boxes to be distinct. If the objects are distinguishable, this formula does not apply --- see “Distributing Distinct Objects.”

Nonnegative vs. Positive Integer Solutions

Concept
Counting integer solutions of an equation

The number of nonnegative integer solutions (x1,…,xk)(x_1,\dots,x_k) to

x1+x2+⋯+xk=n,xi≥0x_1+x_2+\cdots+x_k=n,\qquad x_i\ge 0

is (n+k−1k−1)\displaystyle\binom{n+k-1}{k-1}. This is stars and bars: each xix_i is the number of stars in box ii.

For positive solutions (xi≥1x_i\ge 1), first give each variable 11 unit. Substitute yi=xi−1≥0y_i=x_i-1\ge 0; then y1+⋯+yk=n−ky_1+\cdots+y_k=n-k, so the count is

((n−k)+k−1k−1)=(n−1k−1).\binom{(n-k)+k-1}{k-1}=\binom{n-1}{k-1}.
Example
Two counts, one equation

How many solutions does x1+x2+x3+x4=12x_1+x_2+x_3+x_4=12 have (a) in nonnegative integers, (b) in positive integers?

Solution. (a) Nonnegative: (12+4−14−1)=(153)=455\binom{12+4-1}{4-1}=\binom{15}{3}=455.

(b) Positive: set yi=xi−1y_i=x_i-1, giving y1+⋯+y4=8y_1+\cdots+y_4=8, so (8+4−13)=(113)=165\binom{8+4-1}{3}=\binom{11}{3}=165.

Tip

Substitution is your workhorse. A lower bound xi≥cx_i\ge c is removed by the substitution yi=xi−cy_i=x_i-c. This turns any constant floor into the standard nonnegative problem. Just remember to subtract cc from the right-hand side.

Example
Mixed lower bounds

Count nonnegative solutions to a+b+c=20a+b+c=20 with a≥2a\ge 2, b≥5b\ge 5.

Solution. Let a′=a−2a'=a-2, b′=b−5b'=b-5. Then a′+b′+c=13a'+b'+c=13 with all ≥0\ge 0, giving (13+3−13−1)=(152)=105\binom{13+3-1}{3-1}=\binom{15}{2}=105.

Bounded Variables (upper limits)

Concept
Upper bounds via inclusion--exclusion

Lower bounds are easy (substitute). Upper bounds like xi≤uix_i\le u_i need inclusion--exclusion. To count solutions of x1+⋯+xk=nx_1+\cdots+x_k=n with xi≥0x_i\ge 0 and some cap xi≤uix_i\le u_i: subtract the “bad” cases where a variable exceeds its cap.

If a variable is capped at xi≤ux_i\le u, the bad cases have xi≥u+1x_i\ge u+1; substitute to force that excess and count, then alternate signs over all subsets of violated caps.

Example
One upper bound

How many nonnegative solutions does x+y+z=15x+y+z=15 have with x≤6x\le 6?

Solution. Total (no cap): (15+22)=(172)=136\binom{15+2}{2}=\binom{17}{2}=136. Bad cases have x≥7x\ge 7: set x′=x−7x'=x-7, so x′+y+z=8x'+y+z=8, giving (8+22)=(102)=45\binom{8+2}{2}=\binom{10}{2}=45. Answer =136−45=91=136-45=91.

Example
Two upper bounds (inclusion--exclusion)

Count nonnegative solutions of x+y+z=15x+y+z=15 with x≤6x\le 6 and y≤6y\le 6.

Solution. Let AA be solutions with x≥7x\ge 7, BB with y≥7y\ge 7.

Total=(172)=136,∣A∣=∣B∣=(102)=45,∣A∩B∣=((15−14)+22)=(32)=3.\begin{aligned} \text{Total} &= \binom{17}{2}=136,\\ |A|=|B| &= \binom{10}{2}=45,\\ |A\cap B| &= \binom{(15-14)+2}{2}=\binom{3}{2}=3. \end{aligned}

By inclusion--exclusion the good count is 136−45−45+3=49136-45-45+3=49.

Tip

Sign pattern. Add the unrestricted total, subtract each single-cap violation, add back each double violation, subtract triples, and so on. Any term whose forced excess exceeds nn contributes 00 and can be dropped.

Distributing Distinct Objects

Concept
When the objects are distinguishable

If nn distinct objects are placed into kk distinct boxes and each object is chosen independently, there are

knk^n

ways (each object picks its box). This is a different world from stars and bars: here objects carry identity, so labeling matters.

Grouping distinct objects into unlabeled nonempty groups is counted by Stirling numbers of the second kind S(n,k)S(n,k); distributing into labeled boxes with all nonempty is k! S(n,k)k!\,S(n,k) (a surjection count).

Example
Distinct vs. identical

In how many ways can 55 different books be placed on 33 distinct shelves (order on a shelf ignored, empty shelves allowed)?

Solution. Each book independently chooses one of 33 shelves: 35=2433^5=243.

Contrast: 55 identical books on 33 shelves would be (5+22)=21\binom{5+2}{2}=21.

Tip

Decision rule. Ask: are the items identical or distinct? Identical ⇒\Rightarrow stars and bars, (n+k−1k−1)\binom{n+k-1}{k-1}. Distinct with free choice ⇒\Rightarrow knk^n. Distinct with a fixed size in each box ⇒\Rightarrow multinomial coefficient (next section).

Multinomial Coefficients

Concept
Splitting distinct objects into fixed-size groups

The number of ways to partition nn distinct objects into labeled groups of sizes n1,n2,…,nkn_1,n_2,\dots,n_k (with n1+⋯+nk=nn_1+\cdots+n_k=n) is the multinomial coefficient

(nn1, n2, …, nk)=n!n1! n2!⋯nk!.\binom{n}{n_1,\,n_2,\,\dots,\,n_k}=\frac{n!}{n_1!\,n_2!\cdots n_k!}.

These coefficients appear in the multinomial theorem:

(x1+⋯+xk)n=∑n1+⋯+nk=n(nn1,…,nk) x1n1⋯xknk.(x_1+\cdots+x_k)^n=\sum_{n_1+\cdots+n_k=n}\binom{n}{n_1,\dots,n_k}\,x_1^{n_1}\cdots x_k^{n_k}.
Example
Dealing into fixed hands

In how many ways can 1212 distinct cards be split into three labeled hands of sizes 55, 44, and 33?

Solution. (125,4,3)=12!5! 4! 3!=27720.\displaystyle\binom{12}{5,4,3}=\frac{12!}{5!\,4!\,3!}=27720.

Example
A multinomial coefficient in an expansion

Find the coefficient of x2y3z2x^2y^3z^2 in (x+y+z)7(x+y+z)^7.

Solution. With n=7n=7 and exponents (2,3,2)(2,3,2),

(72,3,2)=7!2! 3! 2!=50402⋅6⋅2=210.\binom{7}{2,3,2}=\frac{7!}{2!\,3!\,2!}=\frac{5040}{2\cdot 6\cdot 2}=210.
Tip

Equal group sizes. If several groups have the same size and the groups themselves are unlabeled, divide by the factorial of the number of equal-size groups to remove overcounting. Labeled groups need no such correction.

Going Deeper: Techniques That Combine

Concept
Layering the tools

Contest problems rarely use one idea in isolation. The strongest solvers layer them:

  • Lower + upper bounds together. First substitute away lower bounds (yi=xi−ciy_i=x_i-c_i), then apply inclusion--exclusion on the remaining upper caps. Order matters: clear floors first, then handle ceilings.
  • Bounded variables via inclusion--exclusion. For x1+⋯+xk=nx_1+\cdots+x_k=n with each xi≤ux_i\le u, the good count is @@BLOCK0@@ dropping any term with a negative top argument.
  • Distributing distinct objects with restrictions. “No box empty” becomes a surjection count k! S(n,k)=∑j=0k(−1)j(kj)(k−j)nk!\,S(n,k)=\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n by inclusion--exclusion on empty boxes.
  • Multinomial expansions. The number of terms in (x1+⋯+xk)n(x_1+\cdots+x_k)^n before combining is knk^n; the number of distinct monomials after combining is (n+k−1k−1)\binom{n+k-1}{k-1} --- stars and bars on the exponents.
Example
Bounded caps by the formula

Count nonnegative solutions of x1+x2+x3+x4=10x_1+x_2+x_3+x_4=10 with each xi≤4x_i\le 4.

Solution. Here k=4k=4, n=10n=10, u=4u=4 so u+1=5u+1=5:

(40)(133)−(41)(83)+(42)(33)=286−4⋅56+6⋅1=286−224+6=68.\begin{aligned} &\binom{4}{0}\binom{13}{3}-\binom{4}{1}\binom{8}{3}+\binom{4}{2}\binom{3}{3}\\ &\quad=286-4\cdot 56+6\cdot 1=286-224+6=68. \end{aligned}

(The j=3j=3 term needs 10−15<010-15<0, so it vanishes.)

Example
Surjections onto boxes

In how many ways can 66 distinct prizes be given to 33 students so that every student gets at least one prize?

Solution. Inclusion--exclusion on empty students:

∑j=03(−1)j(3j)(3−j)6=36−3⋅26+3⋅16=729−192+3=540.\sum_{j=0}^{3}(-1)^j\binom{3}{j}(3-j)^6=3^6-3\cdot 2^6+3\cdot 1^6=729-192+3=540.
Tip

Big picture. Every distribution problem is answered by three questions: (1) Are the items identical or distinct? (2) Are the boxes distinct, and can they be empty? (3) Are there bounds on how much a box holds? Identical items give binomial (stars-and-bars) counts; distinct items give powers, multinomials, or Stirling/surjection counts; bounds are cleared by substitution (lower) and inclusion--exclusion (upper). Name the three answers before you compute, and the right formula chooses itself.

Compositions vs. Partitions

Concept
Ordered and unordered ways to break up nn

A composition of nn is an ordered sequence of positive parts summing to nn; a partition is the same but order is ignored. Thus 3=2+1=1+23=2+1=1+2 gives two compositions but only one partition (2+12+1).

Compositions are just positive stars and bars. The number of compositions of nn into exactly kk positive parts is

(n−1k−1),\binom{n-1}{k-1},

since we place k−1k-1 dividers into the n−1n-1 gaps between nn dots. Summing over kk,

∑k=1n(n−1k−1)=2n−1\sum_{k=1}^{n}\binom{n-1}{k-1}=2^{n-1}

compositions in total: each of the n−1n-1 internal gaps is independently a “cut” or “no cut.”

Partitions are far subtler --- there is no simple closed formula. The number of partitions of nn is written p(n)p(n), and it grows fast: p(1),…,p(6)=1,2,3,5,7,11p(1),\dots,p(6)=1,2,3,5,7,11.

Example
Counting both flavors for n=5n=5

List the compositions and partitions of 55 into parts, and reconcile the counts.

Solution. Total compositions of 55: 25−1=162^{5-1}=16. Compositions into exactly k=3k=3 parts: (5−13−1)=(42)=6\binom{5-1}{3-1}=\binom{4}{2}=6, namely

3 ⁣+ ⁣1 ⁣+ ⁣1, 1 ⁣+ ⁣3 ⁣+ ⁣1, 1 ⁣+ ⁣1 ⁣+ ⁣3, 2 ⁣+ ⁣2 ⁣+ ⁣1, 2 ⁣+ ⁣1 ⁣+ ⁣2, 1 ⁣+ ⁣2 ⁣+ ⁣2.3\!+\!1\!+\!1,\ 1\!+\!3\!+\!1,\ 1\!+\!1\!+\!3,\ 2\!+\!2\!+\!1,\ 2\!+\!1\!+\!2,\ 1\!+\!2\!+\!2.

By contrast the partitions of 55 are 5; 4 ⁣+ ⁣1; 3 ⁣+ ⁣2; 3 ⁣+ ⁣1 ⁣+ ⁣1; 2 ⁣+ ⁣2 ⁣+ ⁣1; 2 ⁣+ ⁣1 ⁣+ ⁣1 ⁣+ ⁣1; 1 ⁣+ ⁣1 ⁣+ ⁣1 ⁣+ ⁣1 ⁣+ ⁣15;\ 4\!+\!1;\ 3\!+\!2;\ 3\!+\!1\!+\!1;\ 2\!+\!2\!+\!1;\ 2\!+\!1\!+\!1\!+\!1;\ 1\!+\!1\!+\!1\!+\!1\!+\!1, so p(5)=7p(5)=7 --- much smaller than 1616, because reorderings collapse.

Tip

Order test. If rearranging the parts gives a different outcome, you are counting compositions --- use stars and bars, (n−1k−1)\binom{n-1}{k-1} or 2n−12^{n-1}. If rearrangements are the same outcome, you are counting partitions, which need generating functions or Ferrers-diagram arguments, not a single binomial.

Integer Partitions and Ferrers Diagrams

Concept
Drawing a partition; the conjugate

A partition λ1≥λ2≥⋯≥λm≥1\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_m\ge 1 of nn is drawn as a Ferrers diagram: left-justified rows of dots, row ii having λi\lambda_i dots. Reflecting the diagram across its main diagonal (swap rows and columns) gives the conjugate partition λ∗\lambda^{*}, another partition of the same nn.

Conjugation is a bijection on partitions of nn, so it proves facts by symmetry. For instance: the number of partitions of nn into at most kk parts equals the number of partitions of nn into parts of size at most kk (conjugation swaps “number of rows” with “length of longest row”).

For λ=(4,2,1)\lambda=(4,2,1) of n=7n=7, the diagram and its conjugate λ∗=(3,2,1,1)\lambda^{*}=(3,2,1,1) are

∙ ∙ ∙ ∙∙ ∙∙∙ ∙ ∙∙ ∙∙∙λ=(4,2,1)λ∗=(3,2,1,1)\begin{array}{ll} \begin{array}{l} \bullet\,\bullet\,\bullet\,\bullet\\[-1pt] \bullet\,\bullet\\[-1pt] \bullet \end{array} & \begin{array}{l} \bullet\,\bullet\,\bullet\\[-1pt] \bullet\,\bullet\\[-1pt] \bullet\\[-1pt] \bullet \end{array} \\[2pt] \lambda=(4,2,1) & \lambda^{*}=(3,2,1,1) \end{array}

Reading the column heights of the left diagram (3,2,1,13,2,1,1) gives exactly the rows of the right one.

Example
Distinct parts == odd parts (Euler)

Show, for n=6n=6, that the number of partitions into distinct parts equals the number into odd parts.

Solution. Distinct-part partitions of 66: 6; 5 ⁣+ ⁣1; 4 ⁣+ ⁣2; 3 ⁣+ ⁣2 ⁣+ ⁣16;\ 5\!+\!1;\ 4\!+\!2;\ 3\!+\!2\!+\!1 --- there are 44. Odd-part partitions of 66: 5 ⁣+ ⁣1; 3 ⁣+ ⁣3; 3 ⁣+ ⁣1 ⁣+ ⁣1 ⁣+ ⁣1; 1 ⁣+ ⁣1 ⁣+ ⁣1 ⁣+ ⁣1 ⁣+ ⁣1 ⁣+ ⁣15\!+\!1;\ 3\!+\!3;\ 3\!+\!1\!+\!1\!+\!1;\ 1\!+\!1\!+\!1\!+\!1\!+\!1\!+\!1 --- also 44.

Why (the bijection). Write each odd-part partition by grouping equal parts: a part dd appearing mm times contributes d⋅md\cdot m. Expand the multiplicity mm in binary, m=∑2jm=\sum 2^{j}, and send it to the distinct parts d⋅2jd\cdot 2^{j}. Every distinct part factors uniquely as (odd)×\times(power of 22), so the map reverses --- proving the two counts are always equal, matching Euler's generating-function identity

∏i≥1(1+xi)=∏i≥111−x2i−1.\prod_{i\ge 1}(1+x^{i})=\prod_{i\ge 1}\frac{1}{1-x^{2i-1}}.
Tip

Bijections beat formulas. Since p(n)p(n) has no elementary closed form, partition identities are proved by matching objects: conjugate diagrams (rows ↔\leftrightarrow columns) or the odd/binary trick above. When a problem claims two partition counts are equal, look for a reversible construction rather than a formula.

The Generating-Function View of Stars and Bars

Concept
Distributions as coefficients

Each box contributes a factor recording what it can hold; multiplying the factors and reading off the coefficient of xnx^{n} counts the distributions summing to nn. An unrestricted box (any count 0,1,2,…0,1,2,\dots) contributes 1+x+x2+⋯=11−x1+x+x^{2}+\cdots=\dfrac{1}{1-x}, so kk free boxes give

1(1−x)k=∑n≥0(n+k−1k−1)xn\frac{1}{(1-x)^{k}}=\sum_{n\ge 0}\binom{n+k-1}{k-1}x^{n}

--- the stars-and-bars formula, now as a coefficient. Restrictions just change the factor:

  • box must be nonempty: x+x2+⋯=x1−xx+x^{2}+\cdots=\dfrac{x}{1-x};
  • box holds at most uu: 1+x+⋯+xu=1−xu+11−x1+x+\cdots+x^{u}=\dfrac{1-x^{u+1}}{1-x};
  • box holds only even amounts: 1+x2+x4+⋯=11−x21+x^{2}+x^{4}+\cdots=\dfrac{1}{1-x^{2}};
  • coin of value vv, any number used: 11−xv\dfrac{1}{1-x^{v}}.

The whole distribution problem becomes: extract [xn][x^{n}] from a product of such factors.

Example
Coin change by coefficient extraction

In how many ways can you make 66 cents using pennies (11), nickels (55), and unlimited 22-cent pieces?

Solution. The generating function is

11−x⋅11−x2⋅11−x5,\frac{1}{1-x}\cdot\frac{1}{1-x^{2}}\cdot\frac{1}{1-x^{5}},

and we want [x6][x^{6}]. Since we need only up to x6x^{6}, truncate each factor. A nickel is used 00 or 11 time (≤6\le 6). With no nickel we need [x6][x^{6}] of 1(1−x)(1−x2)\frac{1}{(1-x)(1-x^{2})}, i.e. pennies++twos summing to 66: the twos number 0,1,2,30,1,2,3, giving 44 ways. With one nickel we need [x1][x^{1}] of the same, i.e. sum 11 from pennies and twos: only 11 way. Total =4+1=5=4+1=5.

Example
Recovering a bounded-cap count

Use generating functions to count nonnegative solutions of x1+x2+x3=8x_1+x_2+x_3=8 with each xi≤4x_i\le 4.

Solution. Each capped box contributes 1−x51−x\dfrac{1-x^{5}}{1-x}, so we need

[x8] (1−x5)3(1−x)3=[x8] (1−3x5+⋯ )∑n(n+22)xn.[x^{8}]\ \frac{(1-x^{5})^{3}}{(1-x)^{3}} =[x^{8}]\,(1-3x^{5}+\cdots)\sum_{n}\binom{n+2}{2}x^{n}.

Only the 11 and −3x5-3x^{5} terms reach degree 88:

(102)−3(52)=45−3⋅10=15.\binom{10}{2}-3\binom{5}{2}=45-3\cdot 10=15.

This is exactly the inclusion--exclusion answer --- the (1−x5)3(1-x^{5})^{3} factor is the alternating sum.

Tip

One factor per box. Build the generating function box by box: unrestricted →11−x\to\frac{1}{1-x}, capped →1−xu+11−x\to\frac{1-x^{u+1}}{1-x}, step-v→11−xvv\to\frac{1}{1-x^{v}}. The binomial series 1(1−x)k=∑(n+k−1k−1)xn\frac{1}{(1-x)^{k}}=\sum\binom{n+k-1}{k-1}x^{n} turns coefficient extraction back into stars and bars, and the numerator polynomials reproduce inclusion--exclusion automatically.

The Twelvefold Way

Concept
One table for every distribution problem

Placing nn balls into kk boxes has 2×2×3=122\times2\times3=12 variants: balls identical or distinct, boxes identical or distinct, and the map unrestricted / injective (“at most one per box”) / surjective (“no box empty”). Every counting formula on this sheet is one cell of the table. Below, S(n,k)S(n,k) is a Stirling number of the second kind and pk(n)p_{k}(n) is the number of partitions of nn into at most kk parts.

balls\boxesany (distinct)injectivesurjective (distinct)distinctknkn‾k! S(n,k)identical(n+k−1k−1)(kn)(n−1k−1)dist., boxes ident.∑j=1kS(n,j)[n≤k]S(n,k)ident., boxes ident.∑j=1kpj(n)[n≤k]pk(n) (exactly k)\small \begin{array}{|l|c|c|c|} \hline \text{balls}\backslash\text{boxes} & \text{any (distinct)} & \text{injective} & \text{surjective (distinct)}\\ \hline \text{distinct} & k^{n} & k^{\underline{n}} & k!\,S(n,k)\\ \hline \text{identical} & \dbinom{n+k-1}{k-1} & \dbinom{k}{n} & \dbinom{n-1}{k-1}\\ \hline \text{dist., boxes ident.} & \sum_{j=1}^{k}S(n,j) & [n\le k] & S(n,k)\\ \hline \text{ident., boxes ident.} & \sum_{j=1}^{k}p_{j}(n) & [n\le k] & p_{k}(n)\text{ (exactly }k\text{)}\\ \hline \end{array}

Here kn‾=k(k−1)⋯(k−n+1)k^{\underline{n}}=k(k-1)\cdots(k-n+1) is the falling factorial and [ ⋅ ][\,\cdot\,] is 11 if true, else 00.

The four rows are exactly the four big ideas of this unit: distinct balls into distinct boxes (powers, falling factorials, surjections), identical balls into distinct boxes (stars and bars, positive stars and bars), distinct balls into identical boxes (Stirling numbers), and identical balls into identical boxes (integer partitions).

Example
Reading four cells off one scenario

Distribute balls into 33 boxes; compare the counts for n=4n=4 balls across the four ball/box types (unrestricted maps).

Solution.

distinct balls, distinct boxes:34=81,identical balls, distinct boxes:(4+22)=(62)=15,distinct balls, identical boxes:S(4,1)+S(4,2)+S(4,3)=1+7+6=14,identical balls, identical boxes:p3(4)=4  (4; 3 ⁣+ ⁣1; 2 ⁣+ ⁣2; 2 ⁣+ ⁣1 ⁣+ ⁣1).\begin{aligned} \text{distinct balls, distinct boxes} &: 3^{4}=81,\\ \text{identical balls, distinct boxes} &: \binom{4+2}{2}=\binom{6}{2}=15,\\ \text{distinct balls, identical boxes} &: S(4,1)+S(4,2)+S(4,3)=1+7+6=14,\\ \text{identical balls, identical boxes} &: p_{3}(4)=4\ \ (4;\,3\!+\!1;\,2\!+\!2;\,2\!+\!1\!+\!1). \end{aligned}

The same physical setup gives four wildly different answers --- which is why naming the ball/box types first is essential.

Example
AIME-flavored classification

How many ways can 1010 identical marbles be split among 44 identical bags with each bag nonempty?

Solution. Identical balls, identical boxes, surjective == partitions of 1010 into exactly 44 positive parts. Subtract 11 from each part: partitions of 10−4=610-4=6 into at most 44 parts, i.e. p4(6)p_{4}(6). The partitions of 66 into ≤4\le 4 parts are

6; 5 ⁣+ ⁣1; 4 ⁣+ ⁣2; 3 ⁣+ ⁣3; 4 ⁣+ ⁣1 ⁣+ ⁣1; 3 ⁣+ ⁣2 ⁣+ ⁣1; 2 ⁣+ ⁣2 ⁣+ ⁣2; 3 ⁣+ ⁣1 ⁣+ ⁣1 ⁣+ ⁣1; 2 ⁣+ ⁣2 ⁣+ ⁣1 ⁣+ ⁣1,6;\ 5\!+\!1;\ 4\!+\!2;\ 3\!+\!3;\ 4\!+\!1\!+\!1;\ 3\!+\!2\!+\!1;\ 2\!+\!2\!+\!2;\ 3\!+\!1\!+\!1\!+\!1;\ 2\!+\!2\!+\!1\!+\!1,

which is 99. (Contrast distinct bags: that would be the positive stars-and-bars count (93)=84\binom{9}{3}=84.)

Tip

Master decision procedure. Fix three switches before computing: (1) balls identical or distinct? (2) boxes distinct or identical? (3) map unrestricted, injective, or surjective? Distinct boxes ⇒\Rightarrow closed-form binomials/powers; identical boxes ⇒\Rightarrow Stirling numbers (distinct balls) or integer partitions (identical balls), which have no simple closed form. The Twelvefold Way is not twelve formulas to memorize --- it is one triple of questions that routes you to the right tool on this sheet.

Formulas, Proofs & Tips

Tip
Stars and bars
x1+x2+⋯+xk=n, xi≥0 ⟹ (n+k−1k−1) solutionsx_1+x_2+\cdots+x_k=n,\ x_i\ge 0 \ \Longrightarrow\ \binom{n+k-1}{k-1} \text{ solutions}

What it means. Counts the ways to split nn identical items among kk distinct groups.

Example. x+y+z=5x+y+z=5 with xi≥0x_i\ge0 has (5+22)=21\binom{5+2}{2}=21 solutions.

Why it works. Lay out nn stars and insert k−1k-1 bars to cut them into kk groups. Every arrangement of n+k−1n+k-1 symbols corresponds to exactly one solution, and choosing where the bars go is (n+k−1k−1)\binom{n+k-1}{k-1}.

Tip. For xi≥1x_i\ge 1, hand each group one item first, then distribute the remaining n−kn-k: (n−1k−1)\binom{n-1}{k-1}.