Stars and Bars: Non-Negative Integer Solutions

Welcome back! In our last lesson, we formalized the core tools of counting: the Sum and Product Rules, permutations, and combinations. You learned to systematically break down problems by asking whether order matters and how to correct for overcounting. These are the building blocks we'll use to construct more specialized and powerful techniques.

Today, we'll tackle a very common and important class of counting problems: distributing identical items into distinct containers. Think of allocating identical tasks to different team members, or putting identical balls into numbered bins. We will master a wonderfully elegant and powerful method called "Stars and Bars" to solve these problems. This technique is not just a formula to memorize; it's a way of reframing a problem that turns a potentially messy casework scenario into a simple combination calculation. For your goal of tackling Olympiad problems, this method is an indispensable part of your arsenal.

From Distribution to a String of Symbols

Let's start with a classic problem. Suppose you want to buy a dozen bagels. The shop has four varieties: onion, blueberry, sesame, and plain. How many different combinations of a dozen bagels can you buy?

Notice that the bagels of the same variety are identical (one onion bagel is the same as another), but the "bins" (the varieties) are distinct. We could buy 3 of each, or 12 onion and none of the others, or 5 onion, 4 blueberry, 2 sesame, and 1 plain. Listing all these possibilities would be tedious and error-prone. We need a better system.

The "Stars and Bars" method provides this system by turning the problem into one of arranging symbols. Let's get an intuitive feel for this from a video that frames this as the "bagel problem."

Stars and Bars (and bagels) - Numberphile

This Numberphile video provides a fantastic, intuitive introduction to the core idea. It's engaging and builds the concept from the ground up.

Please watch the following segments: The Problem: Watch from the beginning to this point to understand the setup of the "bagel problem." The Core Idea: Now, jump to the segment from this part. This is the crucial step. Pay close attention to how 12 bagels are represented as "stars" (*) and the divisions between the 4 kinds of bagels are represented by 3 "bars" (|).

As the video explains, any way of choosing a dozen bagels corresponds to a unique arrangement of 12 stars and 3 bars. For example, using the varieties Onion (O), Blueberry (B), Sesame (S), and Plain (P):

The choice "5 O, 4 B, 2 S, 1 P" corresponds to the arrangement: *****|****|**|*
The choice "12 O, 0 B, 0 S, 0 P" corresponds to: ************|||
The choice "0 O, 3 B, 5 S, 4 P" corresponds to: |***|*****|****

This image illustrates the core idea. Distributing 5 items into 3 containers can be visualized as arranging 5 stars and 2 bars. Here, the arrangement `***| |**` corresponds to 3 items in the first container, 0 in the second, and 2 in the third.

The key insight is that this is a bijection: every valid bagel order corresponds to exactly one unique string of stars and bars, and every string of stars and bars corresponds to exactly one valid bagel order. Therefore, to count the number of ways to choose the bagels, we just need to count the number of ways to arrange the symbols.

Counting the Arrangements

So, how many ways can we arrange 12 stars and 3 bars?

This is a problem you already know how to solve from our last lesson! We have a total of $12 + 3 = 15$ positions to fill. Once we decide where to place the 3 bars, the positions of the 12 stars are automatically determined.

The number of ways to choose 3 positions for the bars from 15 available spots is simply:

(3 15) = \frac{15 !}{3 ! ( 15 - 3 )!} = \frac{15 \times 14 \times 13}{3 \times 2 \times 1} = 5 \times 7 \times 13 = 455

There are 455 ways to buy a dozen bagels from four varieties.

Let's watch the video's explanation of this calculation, which beautifully connects to the concepts of combinations we just reviewed.

Stars and Bars (and bagels) - Numberphile

This segment formalizes the counting process.

Please watch from this segment. It shows how the problem reduces to a choice of positions, leading directly to the binomial coefficient formula \binom{n}{k}.

The General Formula and a Key Abstraction

We can now state the general rule.

Stars and Bars (Theorem 1): The number of ways to distribute $n$ identical items into $k$ distinct bins is:

(k - 1 n + k - 1) or equivalently (n n + k - 1)

This is because we have $n$ stars and need $k - 1$ bars to separate them into $k$ groups, giving us a total of $n + k - 1$ symbols. We then choose the positions for the $k - 1$ bars (or the $n$ stars).

Now for the crucial abstraction that unlocks this method's power for Olympiad problems. The problem of distributing $n$ items into $k$ bins is identical to finding the number of non-negative integer solutions to the equation:

x_{1} + x_{2} + \dots + x_{k} = n, where x_{i} \geq 0 for all i

Here, $x_{i}$ represents the number of items in the $i$ -th bin.

Stars and Bars - Discrete Mathematics

This text provides a more formal write-up, explicitly making the connection between distributions and integer solutions.

Please read the following sections from the article: Start from the paragraph discussing a wrong answer. This reinforces why simpler methods fail. Continue reading through the development of the stars and bars chart, down to the final calculation deriving the formula. This solidifies the mapping of distributions to symbol strings. Finally, read Example 1.5.3, which explicitly poses the problem as finding integer solutions to an equation. This is the key abstraction you must master.

Variation: What if every bin must have at least one item?

Consider the problem: How many ways are there to distribute 7 cookies to 4 kids, such that each kid gets at least one cookie?

This translates to finding the number of positive integer solutions to the equation:

x_{1} + x_{2} + x_{3} + x_{4} = 7, where x_{i} \geq 1 for all i

Our previous formula assumed solutions could be zero (x_i >= 0). We can't use it directly.

The solution is simple and elegant: first, give one cookie to each of the 4 kids to satisfy the condition. This uses up 4 cookies. Now, we are left with $7 - 4 = 3$ cookies to distribute among the 4 kids with no restrictions.

We are now solving a new, unrestricted problem:

x_{1}^{'} + x_{2}^{'} + x_{3}^{'} + x_{4}^{'} = 3, where x_{i}^{'} \geq 0

Here, $n = 3$ (remaining cookies) and $k = 4$ (kids). Using the standard formula:

(4 - 1 3 + 4 - 1) = (3 6) = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20

This pre-distribution method is sometimes called the "saving process." It's a fundamental technique for handling lower-bound constraints.

Stars and Bars (Theorem 2): The number of ways to distribute $n$ identical items into $k$ distinct bins such that each bin has at least one item is:

(k - 1 n - 1)

This comes from first giving one item to each of the $k$ bins, then distributing the remaining $n - k$ items without restriction: $(k - 1 ( n - k ) + k - 1) = (k - 1 n - 1)$ .

Let's watch a clear, Olympiad-focused explanation of this technique.

[PMO Tutorial #15] Counting: Stars and Bars - Combinatorics

This video is from a tutorial for the Philippine Mathematical Olympiad (PMO). It explains the method for handling "at least one" constraints in a very practical way.

Watch the segment from this part. The speaker introduces what he calls the "saving process" to solve a PMO problem where each jar must have at least one ball. This is exactly the technique we just discussed.

Practice Problems

It's time to put this into practice. For each problem, first identify $n$ (the items/stars) and $k$ (the bins/variables). Then, check for any constraints (like x_i >= 1) and adjust your $n$ accordingly before applying the formula.

Integer Solutions I: Find the number of non-negative integer solutions to the equation $x_{1} + x_{2} + x_{3} + x_{4} = 15$ .
Candy Distribution: You have 20 identical pieces of candy to distribute among 5 children.
a. How many ways can this be done if there are no restrictions?
b. How many ways can this be done if each child must receive at least two pieces of candy?
Investment Portfolio: An investor wants to invest 100 thousand dollars into 4 different funds. The investment must be in multiples of 1 thousand dollars. How many different ways can she allocate her money? (Assume the entire 100 thousand must be invested).
Rolling Dice: You roll three standard 6-sided dice. How many possible outcomes are there where the sum of the faces is 12? (The order of the dice doesn't matter, so a roll of (4, 4, 4) is one outcome, and (3, 4, 5) is another, but (3, 4, 5) is the same as (5, 4, 3)).
Hint: Let $x_{1}, x_{2}, x_{3}$ be the values on the dice. You are solving $x_{1} + x_{2} + x_{3} = 12$ . What are the constraints on the $x_{i}$ ? This problem is more complex as it has both lower and upper bounds.

(Solutions will be provided in the next lesson's recap)

Conclusion

Today, we've unlocked a powerful method for solving a wide range of distribution problems. By reframing the problem from distributing items to arranging symbols, we transformed a complex counting task into a simple combination calculation.

Key Takeaways:

The Model: The "Stars and Bars" method is used for distributing $n$ identical items into $k$ distinct bins.
The Abstraction: This model is equivalent to finding the number of integer solutions to $x_{1} + \dots + x_{k} = n$ .
Formula for Non-Negative Solutions ( $x_{i} \geq 0$ ): The number of solutions is $(k - 1 n + k - 1)$ . This corresponds to arranging $n$ stars and $k - 1$ bars.
Formula for Positive Solutions ( $x_{i} \geq 1$ ): The number of solutions is $(k - 1 n - 1)$ . This is found by "pre-distributing" one item to each bin and then solving the remaining unrestricted problem.
General Lower Bounds ( $x_{i} \geq c_{i}$ ): For more general constraints, you can pre-distribute the required amounts and solve for the remainder.

In our next lesson, we will formalize the idea of a bijection, which was the logical engine behind the stars and bars method. You'll learn to construct bijective proofs, which are an elegant and powerful way to prove that two different sets have the same number of elements without doing any algebraic manipulation.