How does the stars and bars method correspond to nonnegative integer solutions of an equation?

Conditions

• The variables $x_1, \dots, x_n$ are nonnegative integers.
• The sum of the variables equals $r$.
• Empty groups are allowed, meaning a variable can be zero.

Reasoning, step by step

1. Represent the total sum $r$ as $r$ identical stars.
2. Use $n-1$ bars to divide the stars into $n$ groups.
3. Assign each group to a variable $x_i$.
4. Count the number of stars in each group to determine the value of $x_i$.
5. Allow empty groups to represent variables with a value of zero.

Example

Nonnegative solutions of $x_1+\cdots+x_n=r$ correspond to r identical stars separated into n groups by $n-1$ bars. Empty groups are allowed.

Common misconceptions

• Believing that every group must contain at least one star (which would apply to positive integer solutions, not nonnegative ones).
• Confusing the number of bars with the number of variables (there are $n-1$ bars for $n$ variables).

Watch the explanation

Explore next

• How do you shift a lower bound for a specific variable?
• How does this relate to combinations with repetition?