Stars and Bars Counting Reference Cheat Sheet

Key Facts

• The number of nonnegative integer solutions to $x_1+x_2+\cdots+x_k=n$ is $\binom{n+k-1}{k-1}$.
• The number of positive integer solutions to $x_1+x_2+\cdots+x_k=n$ is $\binom{n-1}{k-1}$ when $n\ge k$.
• Stars and bars counts distributions of $n$ identical objects into $k$ distinct boxes using $n$ stars and $k-1$ bars.
• The binomial coefficient formula is $\binom{a}{b}=\frac{a!}{b!(a-b)!}$.
• If each variable must satisfy $x_i\ge m_i$, substitute $y_i=x_i-m_i$ so that $y_i\ge 0$.
• If a variable has an upper bound such as $x_i\le r$, count all solutions and subtract the solutions with $x_i\ge r+1$.
• The number of ways to choose $n$ items from $k$ types with repetition allowed is $\binom{n+k-1}{k-1}$.
• Stars and bars does not apply directly when the objects are distinct or when the boxes are identical.

Vocabulary

Stars and bars

A counting method that uses stars for identical objects and bars for dividers between distinct groups.

Nonnegative integer solution

A solution in which every variable is an integer greater than or equal to $0$.

Positive integer solution

A solution in which every variable is an integer greater than or equal to $1$.

Binomial coefficient

The value $\binom{n}{r}$, which counts the number of ways to choose $r$ items from $n$ items.

Upper bound

A maximum allowed value for a variable, such as $x_i\le 5$.

Inclusion-exclusion

A counting strategy that subtracts forbidden cases and adds back cases that were subtracted more than once.