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.

Distributing nn identical objects into kk distinct boxes is the same as counting solutions of x1+⋯+xk=nx_1 + \cdots + x_k = n in non-negative integers, and stars-and-bars gives (n+k−1k−1)\binom{n + k - 1}{k - 1}. Lower bounds are handled by giving each box its minimum first; upper bounds by subtracting the overshooting cases.

The key contrast to keep straight:

  • Permutations (knk^n with repeats allowed, k!/(k−n)!k!/(k-n)! without): 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
kind 12kind 21kind 33kind 40kind 528 donuts (dots), 4 dividers between 5 kinds
This box has 2,1,3,0,22, 1, 3, 0, 2 donuts of the five kinds: 1212 symbols, and the 44 divider places determine the box.

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.
Side note
Where it goes wrong

Using stars-and-bars for DISTINCT objects. The formula counts identical stars; distinguishable balls into boxes is knk^n.

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.

Try it
Quick check

A fruit stand sells apples, bananas, and cherries. In how many ways can you buy 44 pieces of fruit if the order does not matter and repeats are allowed?

Work it on paper before revealing the answer.

Show the answer

Answer: Buying 4 pieces from 3 fruits. We choose a multiset of size k=4k=4 from n=3n=3 distinct fruit types (apple, banana, cherry), where order is irrelevant and repeats are allowed. This is a combination with repetition, counted by the stars-and-bars formula

(n+k−1k)=(3+4−14)=(64).\binom{n+k-1}{k}=\binom{3+4-1}{4}=\binom{6}{4}.

Now (64)=(62)=6⋅52=15\binom{6}{4}=\binom{6}{2}=\dfrac{6\cdot 5}{2}=15. Hence there are 15\boxed{15} ways.

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
12345678910111213bars in places 4, 5, 10 of 13children get 3, 0, 4, 3
A distribution is a choice of 33 bar places among 1313: (133)=286\binom{13}{3} = 286.

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.”

Try it
Quick check

An ice-cream shop has 66 flavors. How many ways can you order a cup of 33 scoops if repeated flavors are allowed and order does not matter?

Work it on paper before revealing the answer.

Show the answer

Answer: 3 scoops from 6 flavors. We pick a multiset of size k=3k=3 from n=6n=6 flavors (order ignored, repeats allowed):

(n+k−1k)=(6+3−13)=(83)=8⋅7⋅63⋅2⋅1=56.\binom{n+k-1}{k}=\binom{6+3-1}{3}=\binom{8}{3}=\frac{8\cdot 7\cdot 6}{3\cdot 2\cdot 1}=56.

So there are 56\boxed{56} possible cups.

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
12 stars, 11 gaps, a bar in 3 of the gapsx = (2, 5, 1, 4)
For positive parts a bar may only sit in a gap between two stars, one bar per gap: (113)=165\binom{11}{3} = 165.

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.

Side note
Where it goes wrong

Using the nonnegative formula for a "at least one each" question. Ten identical candies to 44 children, everyone getting at least one: (133)=286\binom{13}{3} = 286 counts distributions where some child gets nothing. Hand out the 44 guaranteed candies first; the remaining 66 go anywhere, (6+33)=(93)=84\binom{6+3}{3} = \binom93 = 84. Check the smallest case to be sure: 44 candies, 44 children, each at least one, is 11 way, and (33)=1\binom{3}{3} = 1.

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.

Try it
Quick check

How many solutions does a+b+c+d=10a + b + c + d = 10 have in positive integers?

Work it on paper before revealing the answer.

Show the answer

Answer: Give each variable its required 11 first: with a′=a−1a' = a - 1 and so on, a′+b′+c′+d′=6a' + b' + c' + d' = 6 in nonnegative integers, which is (6+33)=(93)=84\binom{6+3}{3} = \binom93 = 84. Equivalently, place 33 bars in the 99 gaps between 1010 stars.   84\boxed{84}

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)
x ≥ 7: 45y ≥ 7: 45both: 3dot (x, y) means z = 15 − x − y136 − 45 − 45 + 3 = 49xy
Solid dots are the good solutions: the 7×77 \times 7 square x,y≤6x, y \le 6. The strips x≥7x \ge 7 and y≥7y \ge 7 overlap in 33 dots, which were subtracted twice.

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.

Try it
Quick check

How many solutions does x+y+z=10x + y + z = 10 have in nonnegative integers with each of x,y,zx, y, z at most 55?

Work it on paper before revealing the answer.

Show the answer

Answer: Without caps: (122)=66\binom{12}{2} = 66. Solutions with x≥6x \ge 6: put x′=x−6x' = x - 6, so x′+y+z=4x' + y + z = 4, (62)=15\binom62 = 15; the same for yy and for zz. Two variables cannot both reach 66, since 12>1012 > 10, so nothing is added back:

66−3⋅15=21.66 - 3\cdot 15 = 21.

  21\boxed{21}

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.

Side note
Where it goes wrong

Using stars and bars for distinct objects. Five different books on 33 shelves is 35=2433^5 = 243, not (72)=21\binom{7}{2} = 21. Stars and bars only records how many books each shelf gets; it cannot tell "algebra on the top shelf, poetry below" from the reverse, and with distinct books those are different outcomes.

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).

Try it
Quick check

In how many ways can 44 different letters be put into 33 different mailboxes (a mailbox may stay empty)?

Work it on paper before revealing the answer.

Show the answer

Answer: Each letter independently chooses one of 33 mailboxes, so 3⋅3⋅3⋅3=34=813\cdot3\cdot3\cdot3 = 3^4 = \boxed{81}. (Stars and bars would give (62)=15\binom{6}{2} = 15, the number of ways to choose how many letters each box gets, which ignores which letters they are.)

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.
Side note
Where it goes wrong

Forgetting that equal-size groups may be unlabeled. Nine players split into three teams of 33: if the teams are Red, Blue, Green, the count is 9!3! 3! 3!=1680\tfrac{9!}{3!\,3!\,3!} = 1680. If the teams have no names, each split was counted once for each of the 3!=63! = 6 ways to paint the colours on, so the answer is 1680/6=2801680/6 = 280.

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.

Try it
Quick check

In how many ways can 99 players be split into three teams of 33 named Red, Blue and Green?

Work it on paper before revealing the answer.

Show the answer

Answer: Choose Red's players, then Blue's from the rest, then Green gets the last three:

(93)(63)(33)=84⋅20⋅1=1680=9!3! 3! 3!.\binom93\binom63\binom33 = 84\cdot 20\cdot 1 = 1680 = \frac{9!}{3!\,3!\,3!}.

  1680\boxed{1680}

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.

Try it
Quick check

How many ways are there to place 1212 identical balls into 44 distinct boxes?

Work it on paper before revealing the answer.

Show the answer

Answer: 12 identical balls into 4 distinct boxes. Nonnegative solutions of b1+b2+b3+b4=12b_1+b_2+b_3+b_4=12; use 1212 stars and 4−1=34-1=3 bars:

(12+4−14−1)=(153)=15⋅14⋅133⋅2⋅1=455.\binom{12+4-1}{4-1}=\binom{15}{3}=\frac{15\cdot 14\cdot 13}{3\cdot 2\cdot 1}=455.

Therefore 455\boxed{455} ways.

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
1 + 1 + 31 + 2 + 21 + 3 + 12 + 1 + 22 + 2 + 13 + 1 + 1
Each composition of 55 into 33 parts is a choice of 22 cuts among the 44 gaps: (42)=6\binom42 = 6.

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.

Try it
Quick check

How many compositions of 77 into exactly 33 positive parts are there? How many partitions of 77 into exactly 33 parts?

Work it on paper before revealing the answer.

Show the answer

Answer: Compositions: choose 22 of the 66 gaps between 77 dots, (62)=15\binom62 = 15. Partitions ignore order, so list them largest part first: 5+1+15+1+1, 4+2+14+2+1, 3+3+13+3+1, 3+2+23+2+2, which is 44. (The 1515 compositions are these four rearranged: 3+6+3+3=153 + 6 + 3 + 3 = 15.)   15 and 4\boxed{15 \text{ and } 4}

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.

n balls, k boxesanyat most one per boxno box emptydistinct balls, distinct boxesknkn‾k! S(n,k)identical balls, distinct boxes(n+k−1k−1)(kn)(n−1k−1)distinct balls, identical boxes∑j=1kS(n,j)[ n≤k ]S(n,k)identical balls, identical boxespk(n)[ n≤k ]pk(n−k)\begin{array}{l|c|c|c} n \text{ balls},\ k \text{ boxes} & \text{any} & \text{at most one per box} & \text{no box empty}\\\hline \text{distinct balls, distinct boxes} & k^{n} & k^{\underline{n}} & k!\,S(n,k)\\ \text{identical balls, distinct boxes} & \dbinom{n+k-1}{k-1} & \dbinom{k}{n} & \dbinom{n-1}{k-1}\\ \text{distinct balls, identical boxes} & \sum_{j=1}^{k}S(n,j) & [\,n\le k\,] & S(n,k)\\ \text{identical balls, identical boxes} & p_{k}(n) & [\,n\le k\,] & p_{k}(n-k) \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 last row follows from the definition of pk(n)p_k(n) as partitions into at most kk parts: identical balls in identical boxes, empty boxes allowed, is a partition of nn into at most kk nonzero parts, so it is pk(n)p_k(n) itself. With no box empty, first put one ball in each box; the other n−kn-k balls then form a partition into at most kk parts, which is pk(n−k)p_k(n-k).

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.

Why It Works

Write nn stars in a row and insert k−1k - 1 bars to cut them into kk groups; the sizes of the groups are the xix_i. Every arrangement of nn stars and k−1k - 1 bars corresponds to exactly one solution and vice versa, and there are (n+k−1k−1)\binom{n + k - 1}{k - 1} ways to choose the bar positions among the n+k−1n + k - 1 symbols. For positive solutions, place the bars in the n−1n - 1 gaps between stars instead: (n−1k−1)\binom{n - 1}{k - 1}.

Tip
Reading a proof

Do not read a proof the way you read a rule. Cover the last line, ask what the previous line forces, and only then uncover it. If a step feels like magic, that is the step to work by hand with a concrete number.

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}.