Stars and Bars with Constraints

Welcome back! In our last lesson, we developed a formal understanding of the Principle of Inclusion-Exclusion (PIE) and proved its general formula. You now have a powerful tool for counting the elements in unions of overlapping sets.

Today, we will apply this principle to a very common and important class of problems in combinatorics: counting the ways to distribute items under complex constraints. You are already familiar with the "stars and bars" method for basic distribution problems. We will now supercharge this technique by combining it with PIE. This will allow you to solve problems with both lower and upper-bound restrictions—a frequent challenge in competitive mathematics.

Our goal is to master the methods for solving distribution problems involving integer solutions to equations with constraints like $x_{i} \geq c$ (at least $c$ ) and $x_{i} \leq d$ (at most $d$ ).

A Quick Review: Stars and Bars

Let's begin with a quick refresher. The "stars and bars" method is used to count the number of ways to distribute $n$ identical items into $k$ distinct bins. This is equivalent to finding the number of non-negative integer solutions to the equation:
$x_{1} + x_{2} + \dots + x_{k} = n$
The key insight is to represent the $n$ items as "stars" (★) and the divisions between the $k$ bins using $k - 1$ "bars" (|).

In this image, 5 identical items (red circles, or stars) are distributed among 3 distinct bins (yellow containers). The distribution shown is 3 items in the first bin, 0 in the second, and 2 in the third. This corresponds to the arrangement ★★★| |★★, which has $n=5$ stars and $k-1=2$ bars.

Any arrangement of these $n + k - 1$ symbols corresponds to a unique solution. The number of ways to arrange them is the number of ways to choose the positions for the $k - 1$ bars, which is:
$(k - 1 n + k - 1) = (n n + k - 1)$

Handling Lower-Bound Constraints

What if each bin must contain a certain minimum number of items? For example, how many integer solutions are there to $x_{1} + x_{2} + x_{3} = 10$ where $x_{1} \geq 1$ , $x_{2} \geq 2$ , and $x_{3} \geq 0$ ?

This type of problem, with lower bounds, can be solved with a clever pre-distribution strategy. Before distributing the 10 items, we first give each variable enough to satisfy its minimum requirement.

Give 1 unit to $x_{1}$ .
Give 2 units to $x_{2}$ .
Give 0 units to $x_{3}$ .

We have now used $1 + 2 + 0 = 3$ units. We have $10 - 3 = 7$ units remaining to distribute among $x_{1}, x_{2}, x_{3}$ without any further restrictions. This is a standard stars and bars problem. Let $x_{1}^{'} = x_{1} - 1$ , $x_{2}^{'} = x_{2} - 2$ , and $x_{3}^{'} = x_{3}$ . Our new problem is finding non-negative solutions to:
$x_{1}^{'} + x_{2}^{'} + x_{3}^{'} = 7$
The number of solutions is $(3 - 1 7 + 3 - 1) = (2 9) = 36$ .

The following resource provides an excellent review of this technique.

Stars and Bars - Discrete Mathematics

This text from Discrete Mathematics: An Open Introduction covers the pre-distribution method for handling lower bounds.

First, read the section on handling minimum requirements. Pay attention to the logic in this paragraph, which explains the pre-distribution strategy. Then, examine Example 1.5.3, which applies this method to find integer solutions with various lower bounds. Finally, look at Exercise 8 which shows how to handle different lower bounds for each variable.

Handling Upper-Bound Constraints with PIE

Handling upper bounds, such as $x_{i} \leq c$ , is more complex. The pre-distribution trick doesn't work because we don't know how many items to "hold back". This is where the Principle of Inclusion-Exclusion becomes essential.

The strategy is as follows:

Calculate the total number of solutions without any upper bounds, using the standard stars and bars formula. Let this be $∣ U ∣$ .
Define a set of "bad" properties. Let $A_{i}$ be the set of solutions where the $i$ -th variable violates its upper bound. For example, if the constraint is $x_{i} \leq c$ , the "bad" property is $x_{i} > c$ , which is equivalent to $x_{i} \geq c + 1$ .
Use PIE to find the number of solutions that have at least one "bad" property, i.e., $∣ ⋃ A_{i} ∣$ .
The number of "good" solutions (those satisfying all upper bounds) is the total number of solutions minus the number of "bad" solutions: $∣ U ∣ - ∣ ⋃ A_{i} ∣$ .

The crucial insight is that calculating the size of each intersection, like $∣ A_{i} ∣$ or $∣ A_{i} \cap A_{j} ∣$ , turns into a stars and bars problem with lower bounds—a problem we already know how to solve!

Let's see this in action.

Advanced Counting Using PIE

This article demonstrates exactly how to combine PIE with stars and bars to solve problems with upper-bound restrictions.

First, read the introductory section and the explanation of how PIE is used to handle upper bounds, starting from this paragraph. Next, carefully study Example 1.6.3. This example walks through the entire process of finding the number of integer solutions to an equation with an upper bound on each variable. Pay close attention to how each term in the PIE formula is calculated.

Let's break down the logic from the example you just read: "Find the number of solutions to $x_{1} + x_{2} + x_{3} + x_{4} + x_{5} = 13$ with $0 \leq x_{i} \leq 3$ for each $x_{i}$ ".

Total Solutions $∣ U ∣$ : Without any upper bounds, this is a standard stars and bars problem with $n = 13$ stars and $k = 5$ variables (so 4 bars). The total is $(5 - 1 13 + 5 - 1) = (4 17)$ .
Bad Properties: The property $P_{i}$ is that $x_{i} \geq 4$ . Let $A_{i}$ be the set of solutions where $x_{i}$ has this property.
Single Violations ( $\sum ∣ A_{i} ∣$ ): How many solutions are in $A_{1}$ , where $x_{1} \geq 4$ ? We use the pre-distribution trick: give 4 units to $x_{1}$ , leaving $13 - 4 = 9$ units to distribute among the 5 variables. This gives $(5 - 1 9 + 5 - 1) = (4 13)$ solutions. Since any of the 5 variables could be the one to violate the condition, and the calculation is identical for each, the total for this term is $(1 5) (4 13)$ .
Double Violations ( $\sum ∣ A_{i} \cap A_{j} ∣$ ): How many solutions are in $A_{1} \cap A_{2}$ , where $x_{1} \geq 4$ and $x_{2} \geq 4$ ? We give 4 units to $x_{1}$ and 4 to $x_{2}$ , using 8 units. We have $13 - 8 = 5$ units left to distribute. This gives $(5 - 1 5 + 5 - 1) = (4 9)$ solutions. There are $(2 5)$ pairs of variables, so this term is $(2 5) (4 9)$ .
Triple Violations ( $\sum ∣ A_{i} \cap A_{j} \cap A_{k} ∣$ ): If three variables are $\geq 4$ , we use $3 \times 4 = 12$ units, leaving $13 - 12 = 1$ unit to distribute. This gives $(5 - 1 1 + 5 - 1) = (4 5)$ solutions. There are $(3 5)$ such triplets, for a term of $(3 5) (4 5)$ .
Four or More Violations: It's impossible for four variables to each be $\geq 4$ , as this would require at least 16 units, but we only have 13. So these terms are 0.

Putting it all together with PIE, the number of "bad" solutions is:
$(1 5) (4 13) - (2 5) (4 9) + (3 5) (4 5)$
The final answer is the total number of solutions minus this quantity.

Advanced Techniques for Olympiad Problems

Mastering combinatorics for competitions often involves recognizing how to transform a problem into a form you know how to solve. Here are two powerful transformation techniques.

1. Handling Inequalities with Slack Variables

How would you find the number of positive integer solutions to $a + b + c + d < 13$ ? This is an inequality, not an equality. The key is to introduce a "slack variable," $e$ , to take up the difference.

The Stars & Bars Counting Technique - Mastering AMC 8

This video by Sohil Rathi demonstrates a clever trick for converting inequalities into equalities, which is a common strategy in problem-solving.

Watch the segment from this timestamp. The presenter introduces a new variable, e, to transform the inequality a+b+c+d < 13 into the equality a+b+c+d+e = 13. Pay attention to why e must also be a positive integer.

The transformation $a + b + c + d < 13 ⟹ a + b + c + d + e = 13$ works because if the sum of the first four is, say, 10 (which is less than 13), then $e$ simply becomes 3. If the sum is 12, $e$ is 1. Since $e$ must be positive, the sum of the first four variables is at most 12, satisfying the strict inequality. The problem is now a standard stars and bars problem with lower bounds (all variables must be $\geq 1$ ).

2. Handling Parity Constraints with Substitution

What if you have constraints like "the number of items must be even" or "must be odd"? You can handle this with a change of variables.

Stars and Bars - Mastering AMC 10/12

This video, also by Sohil Rathi, shows how to solve a distribution problem with odd and even constraints.

Watch the segment from this timestamp. The problem involves distributing acorns with various constraints: Squirrel 1: positive odd number of acorns (x_1) Squirrel 2: non-negative even number (x_2) Squirrel 3: even number \ge 4 (x_3) Notice how each variable is redefined: x_1 = 2a+1, x_2 = 2b, x_3 = 2c+4. This transforms the original equation into a new, simpler one in terms of a, b, c.

Practice Problems

To solidify your understanding, please solve the following problems. They require you to combine the techniques we've discussed.

Dodgeball Cleanup: You are putting 14 identical dodgeballs into 5 bins. How many ways can you do this if no bin can hold more than 6 balls? (This is Exercise 3 from the "Advanced Counting Using PIE" reading).
Constrained Equation: Find the number of integer solutions to the equation $x_{1} + x_{2} + x_{3} = 20$ where $1 \leq x_{1} \leq 6$ , $2 \leq x_{2} \leq 9$ , and $5 \leq x_{3} \leq 12$ .
Inequality with Slack: How many non-negative integer solutions are there to the inequality $x_{1} + x_{2} + x_{3} + x_{4} \leq 10$ ?

Hint for Problem 2: First, handle the lower bounds by pre-distribution to get a new equation with new variables and only upper bounds. Then, apply PIE.

Conclusion

In this lesson, we have significantly expanded the power of the stars and bars method. You are now equipped to handle a wide variety of complex distribution problems.

Key Takeaways:

Lower-bound constraints ( $x_{i} \geq c$ ) are handled by pre-distributing items to satisfy the minimums and then solving a simpler stars and bars problem for the remainder.
Upper-bound constraints ( $x_{i} \leq c$ ) require the Principle of Inclusion-Exclusion. You count the total number of solutions and subtract the "bad" solutions (those that violate one or more upper bounds).
Calculating the number of solutions that violate a set of upper bounds becomes a stars and bars problem with lower bounds, neatly connecting the two techniques.
Advanced constraints, like inequalities or parity, can often be resolved by cleverly introducing new variables or making substitutions.

In our next lesson, we will continue to explore the power of PIE by applying it to a different domain: permutations. We will solve one of the most famous problems in enumerative combinatorics—counting the number of derangements, which are permutations with no fixed points.