7 Stars and Bars
We wish to find the number of solutions to problems of the following variety:
Suppose we have \(n\) objects (e.g. dollars, apples, books) that are to be distributed among \(m\) people. In how many ways can this be accomplished?
A common notation we will use here is \(x_i\) will be the number of objects distributed to person \(i\). And this will give us the equation or inequality
\[\begin{align*} x_1 + x_2 + \cdots + x_m &= n \\ \text{or } x_1 + x_2 + \cdots + x_m &\le n \end{align*}\]
Example 7.1 If there are \(10\) books and we distribute \(2, 4, 1, 3\) to person \(1, 2, 3, 4\) respectively then \(x_1 = 2, x_2 = 4, x_3 = 1, x_4 = 3\) and \[ x_1 + x_2 + x_3 + x_4 = 2 + 4 + 1 + 3 = 10. \]
7.1 Model 1: shuffling
Consider the numbers from Example 7.1. We can represent this as an arrangement of stars and bars as
\[ \underbrace{* *}_{x_1} \mid \underbrace{* * * *}_{x_2} \mid \underbrace{*}_{x_3} \mid \underbrace{* * *}_{x_4} \]
Notice here that we need only 3 bars to divide the stars into 4 groups. In general, for the equation \(x_1 + \dots + x_m = n\) we need \(m - 1\) bars to divide the \(n\) stars among \(m\) people.
Different shuffles of these 10 stars and 3 bars yield different distributions of objects:
\[\begin{align*} ********** | | | && 10 + 0 + 0 + 0 = 10 \\ | ***** | ***** | && 0 + 5 + 5 + 0 = 10 \\ | | ******* | *** && 0 + 0 + 7 + 3 = 10 \\ ** | ** | ** | **** && 2 + 2 + 2 + 4 = 10 \end{align*}\]
and so on.
In this shuffling model, * a bar can be in any position including the front or end * two or more bars can be touching * this represents the condition \(x_i \ge 0\)
Theorem 7.1 The number of solutions to \[ x_1 + x_2 + \dots + x_m = n, \; x_i \ge 0 \] is \(\binom{m - 1 + n}{m - 1}\) or \(\binom{m - 1 + n}{n}\).
Proof. Each way to write \(n\) as a sum in this way corresponds to a stars and bars arrangement of shuffling \(m - 1\) bars and \(n\) stars. The number of shuffles is equal to choosing where the \(m - 1\) bars go among the \(m - 1 + n\) positions.
Equivalently, we can choose where the \(n\) stars go. Giving
\[\binom{m - 1 + n}{m - 1} \text{ or } \binom{m - 1 + n}{n}. \]
Example 7.2 How many ways are there to distribute 10 apples among 4 people where everyone can get \(0\) or more apples?
Solution: There are \(n = 10\) objects and \(m = 4\) people. The stars and bars arrangement has \(10\) stars and \(3\) bars. By Theorem 7.1 there are \(\binom{3 + 10}{3}\) ways to distribute the apples.
7.2 Model 2: gaps
Another variation on this problem is what do we do when we want to ensure everyone gets at least one object? That is, \(x_i \ge 1\) rather than \(\ge 0\)?
Here we will use an idea that sometimes appears in math competition type problems of “how many ways to shuffle if…”
Example 7.3 How many ways are there to seat \(10\) people in a row such that person \(1\) and person \(2\) are not sat next to each other?
Solution 1: Count all the shuffles and subtract the ones containing the substring “12” or the substring “21”.
- There are \(10!\) ways to shuffle the 10 people: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Now group “12” together into a single symbol
- There are \(9!\) ways to shuffle the symbols ‘12’, 3, 4, 5, 6, 7, 8, 9, 10
- Likewise there are \(9!\) ways if we have “21” instead of “12” in our shuffle
- So the final count is \(10! - 9! - 9!\)
Solution 2: First shuffle the \(8\) people 3, 4, 5, 6, 7, 8, 9, 10 then put 1 and 2 in the gaps created by this shuffle. E.g. if that shuffle is 6, 3, 10, 9, 5, 4, 7, 8 then we can put 1 and 2 in any of these positions \[ \textunderscore 6 \textunderscore 3 \textunderscore 10 \textunderscore 9 \textunderscore 5 \textunderscore 4 \textunderscore 7 \textunderscore 8 \textunderscore \]
Here there are 9 gaps in which we need to choose 2 to put 1 and 2. But the 1 and 2 can go in either order so we multiply by 2. I.e. \(\binom{9}{2} \cdot 2 = P(9, 2)\). Alternatively: there are 9 choices to put the 1 and then 8 choices to put the 2 since it can’t go in the same spot as the 1.
In total therefore, there are \(8! \cdot 9 \cdot 8\) arrangements.
Exercise: double check that the quantities we obtained in these two solutions are in fact equal.
Solution 2 in this previous example is the approach we will take for our stars and bars problem. If we want \(x_i \ge 1\) then the bars cannot touch, there needs to be at least 1 star in between every pair of bars as well as at least one star at the front and at least one at the end.
For example, in our 10 apples, 4 people problem, the bars can go in any of these positions:
\[ * \textunderscore * \textunderscore * \textunderscore * \textunderscore * \textunderscore * \textunderscore * \textunderscore * \textunderscore * \textunderscore * \]
If there are \(n\) stars/objects, there are \(n - 1\) gaps in which to place the bars. This is because the bars can’t go at the very start or very end because the first and last person needs at least one star. So the bars have to go in between.
Theorem 7.2 The number of solutions to \[ x_1 + x_2 + \dots + x_m = n, \; x_i \ge 1 \] is \(\binom{n - 1}{m - 1}\).
Proof. Each way to write \(n\) as a sum in this way corresponds to a stars and bars arrangement with \(n\) stars, \(n - 1\) gaps and \(m - 1\) bars. The number of arrangements is equal to choosing where the \(m - 1\) bars go in the \(n - 1\) gaps. That is, \[\binom{n - 1}{m - 1}. \]
Example 7.4 How many ways are there to distribute 10 apples among 4 people where everyone can get \(1\) or more apples?
Solution: There are \(n = 10\) objects and \(m = 4\) people. The stars and bars arrangement has \(10\) stars, \(9\) gaps and \(3\) bars. By Theorem 7.2 there are \(\binom{9}{3}\) ways to distribute the apples.
7.3 Changing the lower bounds
There are several ways to modify the stars and bars model. The first way is to change the lower bounds from \(x_i \ge 0\) or \(x_i \ge 1\) to some other lower bound.
Example 7.5 How many ways are the distribute 20 apples among 5 people in such a way that person 1 gets at least 4 (\(x_1 \ge 4\)), person 2 gets at least 3 (\(x_2 \ge 3\)), person 3 gets at least 1 and person 4 gets at least 0?
Solution: person 1 wants at least 4 apples so start by given them 4 apples. Likewise give 3 apples to person 2 and 1 to person 3. In total, we have given away 8 apples so now we have 12 apples remaining.
At this point, everybody is satisfied with the number of apples they have received. So the amount of additional apples they will get is 0 or more for everyone. We can represent this with a change of variable \(y_1 = x_1 - 4\), \(y_2 = x_2 - 3\), \(y_3 = x_3 - 1\) and \(y_4 = x_4 - 0\) where \(y_i\) represents the amount of additional apples that person will get beyond the lower bound they have already reveived. Now the problem is
\[ y_1 + y_2 + y_3 + y_4 = 12, \; y_i \ge 0 \]
The number of solutions is therefore \(\binom{4 - 1 + 12}{4 - 1} = \binom{15}{3}\) by Theorem 7.1.
7.4 Slack variables
Suppose instead of the equation
\[ x_1 + x_2 + \dots + x_m = n \]
we have an inequality
\[ x_1 + x_2 + \dots + x_m \le n. \]
Example 7.6 Suppose there are 10 coupons leftover from an event that are being distributed among the 4 volunteers. Everyone will take at least 1 coupon but some may be leftover to fund the next event. How many ways can the coupons be distributed?
Solution: Here we have \[ x_1 + x_2 + x_3 + x_4 \le 10, \; x_i \ge 1 \]
The trick is to create a new variable, \(x_5\) to represent the amount leftover. This is commonly called a slack variable. Notice there might be 0 leftover so \(x_5 \ge 0\). This gives us
\[ x_1 + x_2 + x_3 + x_4 + x_5 = 10, \; x_1, x_2, x_3, x_4 \ge 1, \; x_5 \ge 0 \]
As in Example 7.5, we now subtract the lower bounds for each \(x_i\) to get
\[ y_1 + y_2 + y_3 + y_4 + y_5 = 6, \; y_i \ge 0 \]
Which has \(\binom{4 + 6}{4}\) solutions by Theorem 7.1 (4 bars, 6 stars).
7.5 An upper and lower bound
Example 7.7 How many solutions are there to \[ x_1 + x_2 + x_3 + x_4 \le 20, \; 3 \le x_1 \le 8, \; x_2, x_3, x_4 \ge 0 ? \]
Solution: First, as with Example 7.6, we add a slack variable \(x_5 \ge 0\). This gives us \[ x_1 + x_2 + x_3 + x_4 + x_5 = 20, \; 3 \le x_1 \le 8, \; x_2, x_3, x_4, x_5 \ge 0. \]
Second, as in #exm-sb-lower-bounds, we want to give 3 to the first person. Let \(y_1 = x_1 - 3\) be the amount of additional objects given to person 1. We have \[ 3 \le x_1 \le 8 \implies 0 \le x_1 - 3 \le 5 \] (If they already have 3 objects, they can get at most 5 more before exceeding the upper bound of 8.) So now, our problem looks like \[ y_1 + y_2 + y_3 + y_4 + y_5 = 17, \; y_i \ge 0, y_1 \le 5 \] Ignoring the upper bound, there are \(\binom{4 + 17}{4}\) solutions by Theorem 7.1 (4 bars, 17 stars). But this counts also the cases where \(y_1 \not\le 5\), i.e. \(y_1 \ge 6\). So we correct our count by subtracting the number of solutions to \[ y_1 + y_2 + y_3 + y_4 + y_5 = 17, \; y_i \ge 0, y_1 \ge 6. \] Here again, we distribute 6 objects to person 1, leaving 11 objects. So there are \(\binom{4 + 11}{4}\) solutions with \(y_1 \ge 6\).
Combining our counts, we have \[ \binom{4 + 17}{4} - \binom{4 + 11}{4} \] total solutions.