Math Core

How many ways can you hand out $10$ identical candies to $4$ kids? How many ways can $4$ dice show a total of $12$ ? How many terms does $(a + b + c + d)^6$ have? These look like different questions, but they are all the same question: how many ways can you split a number into an ordered list of parts? Stars and bars answers it with a single binomial coefficient.

The picture

Suppose you want nonnegative integers $x_1, x_2, x_3, x_4$ with

$x_1 + x_2 + x_3 + x_4 = 10.$

Draw $10$ stars in a row and insert $3$ bars to cut them into $4$ groups. The number of stars before the first bar is $x_1$ , between the first and second bars is $x_2$ , and so on. For example,

$\star\star \mid \star\star\star\star\star \mid \mid \star\star\star$

means $x_1 = 2$ , $x_2 = 5$ , $x_3 = 0$ , $x_4 = 3$ . Two bars side by side mean an empty group.

Every solution gives exactly one row of $10$ stars and $3$ bars, and every such row gives exactly one solution. A row is $13$ symbols, and you only need to decide which $3$ of the $13$ positions hold bars. So there are $\dbinom{13}{3} = 286$ solutions.

Stars and bars

The number of solutions to $x_1 + x_2 + \cdots + x_k = n$ in nonnegative integers is

$\binom{n + k - 1}{k - 1}.$

The number of solutions in positive integers is $\dbinom{n - 1}{k - 1}$ : choose $k - 1$ of the $n - 1$ spaces between stars to hold a bar.

The formula counts ways to put $n$ identical objects into $k$ distinct boxes. If the objects are different (distinct balls), stars and bars does not apply; that's $k^n$ instead.

Lower bounds: pre-fill the boxes

If $x_i \ge 3$ , give box $i$ its $3$ first and write $x_i = 3 + y_i$ with $y_i \ge 0$ . Substitute, and you're back to a plain nonnegative problem with a smaller total.

Upper bounds: subtract the violators

If $x_i \le 5$ , count all solutions, then subtract those where some $x_i \ge 6$ (pre-fill $6$ into that box). If two boxes could both be over the limit, add those back. This is inclusion-exclusion, covered in the next module, and it usually only needs one or two terms.

Disguises

Stars and bars often hides behind other wording:

Dice sums. The number of ways $k$ dice can sum to $n$ is a positive-integer problem with an upper bound of $6$ on each part.
Terms of an expansion. Each term of $(a + b + c + d)^6$ is $a^{i}b^{j}c^{k}d^{l}$ with $i + j + k + l = 6$ .
Nondecreasing sequences. A sequence $1 \le a_1 \le a_2 \le \cdots \le a_m \le N$ is determined by how many times each value $1, \dots, N$ appears. That is $m$ stars in $N$ boxes.
Inequalities. $x_1 + \cdots + x_k \le n$ becomes an equation by adding a slack variable $s = n - (x_1 + \cdots + x_k) \ge 0$ .

Worked example: Pre-filling

In how many ways can $20$ identical candies be given to $4$ children so that each child gets at least $3$ ?

Give each child $3$ candies first. That uses $12$ , leaving $8$ to be handed out with no restriction: $y_1 + y_2 + y_3 + y_4 = 8$ with $y_i \ge 0$ . The count is $\dbinom{8 + 3}{3} = \dbinom{11}{3} = 165$ .

Worked example: An upper bound

How many solutions does $x + y + z = 12$ have in nonnegative integers with each variable at most $5$ ?

All solutions: $\dbinom{14}{2} = 91$ .

Solutions with $x \ge 6$ : set $x = 6 + x'$ , so $x' + y + z = 6$ , giving $\dbinom{8}{2} = 28$ . The same holds for $y$ and for $z$ , so subtract $3 \cdot 28 = 84$ .

Two variables at least $6$ : that uses all $12$ , so $x = y = 6$ , $z = 0$ is the only case. There are $3$ such pairs, and we subtracted each of these solutions twice, so add $3$ back.

The answer is $91 - 84 + 3 = 10$ . (Check by listing: the permutations of $(5, 5, 2)$ and $(5, 4, 3)$ give $3 + 6 = 9$ , plus $(4, 4, 4)$ makes $10$ .)

Worked example: Nondecreasing digits

How many four-digit positive integers have digits that never decrease from left to right and contain no zero (such as $1334$ or $2299$ )?

Such a number is determined by how many of each digit $1$ through $9$ it uses. That's $4$ stars in $9$ boxes: $\dbinom{4 + 8}{8} = \dbinom{12}{4} = 495$ .

Common mistake

Don't mix up the two formulas. "Each box may be empty" is $\dbinom{n+k-1}{k-1}$ ; "each box gets at least one" is $\dbinom{n-1}{k-1}$ . When in doubt, convert to the nonnegative version by pre-filling, and use only the first formula.

Worked example: Exponents of a product

How many ordered triples $(a, b, c)$ of positive integers satisfy $abc = 2^5 \cdot 3^4$ ?

Write $a = 2^{a_1}3^{a_2}$ , and similarly for $b$ and $c$ . The exponents of $2$ must satisfy $a_1 + b_1 + c_1 = 5$ , which has $\dbinom{7}{2} = 21$ solutions. The exponents of $3$ satisfy $a_2 + b_2 + c_2 = 4$ , which has $\dbinom{6}{2} = 15$ solutions. The two choices are independent, so the answer is $21 \cdot 15 = 315$ .

Practice

Practice 1

In how many ways can $12$ identical balls be placed into $3$ different boxes? (Boxes may be empty.)

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 2

How many ordered $5$ -tuples $(a, b, c, d, e)$ of positive integers satisfy $a + b + c + d + e = 12$ ?

Practice 3

After $(a + b + c + d)^6$ is expanded and like terms are combined, how many terms are there?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 4

How many three-digit positive integers have digits whose sum is $10$ ?

Practice 5

How many ordered triples $(a, b, c)$ of nonnegative integers satisfy $2a + b + c = 10$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 6

How many ordered triples $(x, y, z)$ of positive odd integers satisfy $x + y + z = 25$ ?

Practice 7

Four standard six-sided dice are rolled, and the dice are distinguishable. In how many of the $6^4$ outcomes is the sum of the four numbers equal to $12$ ?

Practice 8

How many sequences $(a_1, a_2, a_3, a_4, a_5)$ of integers satisfy $1 \le a_1 \le a_2 \le a_3 \le a_4 \le a_5 \le 7$ ?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 9

How many ordered quadruples $(a, b, c, d)$ of positive integers satisfy $abcd = 2^3 \cdot 5^3$ ?

Real contest practice

2018 AMC 10A, Problem 11: the number of ways several dice can reach a given sum.
2016 AMC 10A, Problem 20: counting the terms of a multinomial expansion that contain every variable.