Integer Equations - Stars and Bars
A frequently occurring problem in combinatorics arises when counting the number of ways to group identical objects, such as placing indistinguishable balls into labelled urns. We discuss a combinatorial counting technique known asstars and barsorballs and urnsto solve these problems, where the indistinguishable objects are represented by stars and the separation into groups is represented by bars.
This allows us to transform the set to be counted into another, which is easier to count. As we have abijection, these sets have the same size.
Contents
Introduction
Consider the equation \(a+b+c+d=12\) where \(a,b,c,d\) are non-negative integers. We're looking for the number of solutions this equation has. At first, it's not exactly obvious how we can approach this problem. One way is brute force: fixing possibilities for one variable, and analyzing the result for other variables. But we want something nicer, something really elegant. We use the above-noted strategy: transforming a set to another by showing a bijection so that the second set is easier to count.
Suppose we have \(15\) places, where we put \(12\) stars and \(3\) bars, one item per place. The key idea is that this configuration stands for a solution to our equation. For example, \(\{*|*****|****|**\}\) stands for the solution \(1+5+4+2=12\). Because we have \(1\) star, then a bar (standing for a plus sign), then \(5\) stars, again a bar, and similarly \(4\) and \(2\) stars follow. Similarly, \(\{|*****|***|****\}\) denotes the solution \(0+5+3+4=12\) because we have no star at first, then a bar, and similar reasoning like the previous.
We see that any such configuration stands for a solution to the equation, and any solution to the equation can be converted to such a stars-bars series. So we've established a bijection between the solutions to our equation and the configurations of \(12\) stars and \(3\) bars. So our problem reduces to "in how many ways can we place \(12\) stars and \(3\) bars in \(15\) places?" This is the same as fixing \(3\) places out of \(15\) places and filling the rest with stars. We can do this in, of course, \(\dbinom{15}{3}\) ways. So the number of solutions to our equation is \[\dbinom{15}{3}=455.\]
恒星和酒吧定理
The stars and bars/balls and urns technique is as stated below.
The number of ways to place \(n\) indistinguishable balls into \(k\) labelled urns is
\[ \binom{n+k-1}{n} = \binom{n+k-1}{k-1}. \ _\square \]
Here is the proof the above theorem.
We represent the \(n\) balls by \(n\) adjacent stars and consider inserting \(k-1\) bars in between stars to separate the bars into \(k\) groups. For example, for \(n=12\) and \(k=5\), the following is a representation of a grouping of \(12\) indistinguishable balls in 5 urns, where the size of urns 1, 2, 3, 4, and 5 are 2, 4, 0, 3, and 3, respectively:
\[ * * | * * * * | \, | * * * | * * * \]
Note that in the grouping, there may be empty urns. There are a total of \(n+k-1\) positions, of which \(n\) are stars and \(k-1\) are bars. Thus, the number of ways to place \(n\) indistinguishable balls into \(k\) labelled urns is the same as the number of ways of choosing \(n\) positions among \(n+k-1\) spaces for the stars, with all remaining positions taken as bars. The number of ways this can be done is \( \binom{n+k-1}{n}. \) \(_\square\)
Note:\( \binom{n+k-1}{n} = \binom{n+k-1}{k-1}\) can be interpreted as the number of ways to instead choose the positions for \(k-1\) bars and take all remaining positions to be stars.
Check out the following example:
How many ordered sets of non-negative integers \( (a, b, c, d) \) are there such that
\[ a + b + c + d = 10 ?\]
We first create a bijection between the solutions to \( a+b+c +d = 10\) and the sequences of length 13 consisting of 10 \( 1\)'s and 3 \( 0\)'s. In other words, we will associate each solution with a unique sequence, and vice versa.
Given a set of 4 integers \( (a, b, c, d) \), we create the sequence that starts with \( a\) \( 1\)'s, then has a \( 0\), then has \( b\) \( 1\)'s, then has a \( 0\), then has \( c\) \( 1\)'s, then has a \( 0\), then has \( d\) \( 1\)'s. For example, if \( (a, b, c, d) = (1, 4, 0, 2) \), then the associated sequence is \( 1 0 1 1 1 1 0 0 1 1 \). Now, if we add the restriction that \( a + b + c + d = 10 \), the associated sequence will consist of 10 \( 1\)'s (from \( a, b, c, d\)) and 3 \( 0\)'s (from our manual insert), and thus has total length 13.
Conversely, given a sequence of length 13 that consists of 10 \( 1\)'s and 3 \( 0\)'s, let \( a\) be the length of the initial string of \( 1\)'s (before the first \( 0\)), let \( b\) be the length of the next string of 1's (between the first and second \( 0\)), let \( c\) be the length of the third string of \( 1\)'s (between the second and third \( 0\)), and let \( d\) be the length of the last string of \( 1\)'s (after the third \( 0\)). These values give a solution to the equation \( a + b + c + d = 10\).
This construction associates each solution with a unique sequence, and vice versa, and hence gives a bijection.
Now that we have a bijection, the problem is equivalent to counting the number of sequences of length 13 that consist of 10 \( 1\)'s and 3 \( 0\)'s, which we count using the stars and bars technique. There are \(13\) positions from which we choose \(10\) positions as 1's and let the remaining positions be 0's. By stars and bars, there are \( {13 \choose 10} = {13 \choose 3} = 286 \) different choices. \(_\square\)
Note:Another approach for solving this problem is the method ofgenerating functions.
Problem Solving
This section contains examples followed by problems to try.
Find the number of non-negative integer solutions to \[a+b+c+d+e+f=23.\]
We have \(6\) variables, thus \(5\) plus signs. So by stars and bars, the answer is
\[\dbinom{23+5}{5}=\dbinom{28}{5}=98280. \ _\square\]
How many ways are there to choose a 5-letter word from the 26-letter English alphabet with replacement, where words that are anagrams are considered the same?
Observe that since anagrams are considered the same, the feature of interest is how many times each letter appears in the word (ignoring the order in which the letters appear). To translate this into a stars and bars problem, we consider writing 5 as a sum of 26 integers \(c_A, c_B, \ldots c_Y,\) and \(c_Z,\) where \(c_A\) is the number of times letter \(A\) is chosen, \(c_B\) is the number of times letter \(B\) is chosen, etc.
Thus, \(n\) = 5 and \(k\) = 26.
Then by stars and bars, the number of 5-letter words is
\[ \binom{26 +5 -1}{5} = \binom{30}{25} = 142506. \ _\square\]
For some problems, the stars and bars technique does not apply immediately. In these instances, the solutions to the problem must first be mapped to solutions of another problem which can then be solved by stars and bars. We illustrate one such problem in the following example:
How many ordered sets of positive integers \( (a_1, a_2, a_3, a_4, a_5, a_6) \) are there such that \(a_i \geq i\) for \(i = 1,2, \ldots, 6\) and
\[ a_1 + a_2 + a_3 + a_4 + a_5 + a_6 \leq 100 ?\]
Because of the inequality, this problem does not map directly to the stars and bars framework. To proceed, consider a bijection between the integers \( (a_1, a_2, a_3, a_4, a_5, a_6) \) satisfying the conditions and the integers \( (a_1, a_2, a_3, a_4, a_5, a_6, c) \) satisfying \( a_i \geq i, c \geq 0,\) and
\[ a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + c = 100 .\]
Now, by setting \(b_i= a_i-i\) for \(i = 1,2, \ldots, 6\), we would like to find the set of integers \( (b_1, b_2, b_3, b_4, b_5, b_6, c) \) such that \(b_i \geq 0, c \geq 0,\) and
\[ b_1 + b_2 + b_3 + b_4 + b_5 + b_6 + c = 100 - (1 + 2 + 3 + 4 + 5 + 6) = 79.\]
由恒星和酒吧,这等于\ \ binom {79 + 7-1}{79} = \binom{85}{79} \). \(_\square\)
Try the following problems:
