13  Stars and Bars Revisited

Suppose we have \(2\) people and \(n\) identical objects to distribute. Let’s say for now that a person gets \(0\) or more objects but all \(n\) objects are distributed. An example arrangement we might create with stars and bars would look like \[ *****\mid***. \] The key insight is that if we change this to \[ 0\,0\,0\,0\,0\mid1\,1\,1. \] Now it looks like the problem we studied in Section 12.4. The bar here is no longer necessary to know where the first group ends and the second begins.

Now we can check that our stars-and-bars formula agrees with the formula computed in Section 12.4. Indeed, that formula is \[ \binom{n + 1}{1} = n + 1. \]

13.1 From 2 people to k people

Let’s copy the key insight for the \(k = 2\) case. A distribution of \(n\) objects to \(k\) people, with each receiving \(0\) or more, looks like a string \[ 1\cdots12\cdots23\cdots3\cdots\cdots k\cdots k. \] Here the number of \(i\)s in the string is the number of objects person \(i\) receives. E.g. \[ 1122223555 \] means person \(1\) receives \(2\) objects, person \(2\) receives \(4\), person \(3\) receives \(1\), person \(5\) receives \(3\), and everyone else (including person \(4\)) receives none.

13.1.1 Applying the multiplication theorem

Let \(L_i\) be the language of strings consisting of \(0\) or more of the character \(i\). Then the stars-and-bars language for \(k\) people, is \(L_1 L_2 \cdots L_k\). We also know from Section 11.3 that each of these language has a generating function of \(\frac{1}{1-x}\). It follows that our stars-and-bars language has a generating function of \[ \frac{1}{(1 - x)^k} = \sum_{n = 0}^\infty \binom{n + k - 1}{k - 1} x^n. \] We know these are the coefficients because we know there are \(\binom{n + k - 1}{k - 1}\) stars-and-bars strings of length \(n\) (i.e. that many ways to distribute the \(n\) objects among \(k\) people).

Exercise 13.1 Use proof by induction to show that \[ \frac{1}{(1 - x)^k} = \sum_{n = 0}^\infty \binom{n + k - 1}{k - 1} x^n. \] Use the derivative to go from case \(k\) to case \(k + 1\). Take the geometric series as the base case (\(k = 1\)).

Hint: the derivative is going to reduce the exponent from \(x^n\) to \(x^{n - 1}\) so to get a step ahead of that, we can add \(1\) everywhere we see \(n\): \[ \frac{1}{(1 - x)^k} = \sum_{n + 1 = 0}^\infty \binom{n + k}{k - 1} x^{n + 1}. \]

13.2 Variations of Stars and Bars

How do do the stars and bars problem where every person gets at least \(1\) object? Let’s look back at our work:

  1. Broke up the problem into a concatenation \(L_1 L_2 \cdots L_k\)
  2. \(L_i = \{\varepsilon, i, ii, iii, \dots\}\)
  3. The generating function of \(L_i\) is \(\frac{1}{1 - x}\)
  4. Use the multiplication principle to conclude that the generating function of \(L_1 L_2 \cdots L_k\) is \(\frac{1}{(1 - x)^k}\)

The second step is where we need to start making changes; if each person gets at least \(1\) object, then \(L_i\) should instead be \(\{i, ii, iii, \dots\}\) with generating function

\[ x^{f(i)} + x^{f(ii)} + x^{f(iii)} + \dots = x + x^2 + x^3 + \dots = \frac{x}{1 - x}. \]

In general, a geometric series will have some initial term \(a\) and then each succesive term is multiplied by a common ratio \(r\). We can factor out the initial term \(a\) to evaluate: \[ a + ar + ar^2 + ar^3 + \cdots = a(1 + r + r^2 + r^3 + \cdots) = \frac{a}{1 - r}. \] Mnemonic: “initial term over \(1\) minus the common ratio.” E.g. \(3x + 6x^3 + 12x^5 + 24x^7 + \cdots\) has an inital term of \(3x\) and a common ratio of \(2x^2\). So this evaluates to \(\frac{3x}{1 - 2x^2}\).

Substituting this new generating function into our previous steps, we find that the stars-and-bars generating function with everyone getting at least \(1\) object is \[ \left( \frac{x}{1 - x} \right)^k = \frac{x^k}{(1 - x)^k} = x^k \sum_{n = 0}^\infty \binom{n + k - 1}{k - 1} x^n = \sum_{n = 0}^\infty \binom{n + k - 1}{k - 1} x^{n + k}. \]

In order to get the number of solutions with \(m\) objects, we need the coefficient of \(x^m\), so we need \(n + k = m\). Changing \(n + k\) to \(m\), we get

\[ \frac{x^k}{(1 - x)^k} = \sum_{m = k}^\infty \binom{m - 1}{k - 1} x^{m}. \]

This matches our result of \(\binom{m - 1}{k - 1}\) ways to distribute \(m\) objects to \(k\) people, with each person receiving at least \(1\).

13.2.1 Other restrictions

Let’s take the problem \[ x_1 + x_2 + \cdots + x_k = n, \] where \(x_i \ge 1\). Now consider a restriction like \(5 \le x_1 \le 13\). This changes the language \(L_1\) to \(\{11111, 111111, \cdots, 1111111111111\}\) and the generating function of \(L_1\) to \[ x^5 + x^6 + \cdots + x^{13} = \frac{x^5 - x^{14}}{1 - x}. \]

Suppose we have a finite geometric sum with initial term \(a\), common ratio \(r\) and proceeding for some number of steps. Then using the same method as Section 11.3, we can compute the sum \[\begin{align*} S &= a + ar + ar^2 + \cdots + ar^m \\ rS &= \phantom{a + {}} ar + ar^2 + \cdots + ar^m + ar^{m + 1} \\ S - rS &= a \phantom{{}+ar + ar^2 + \cdots + ar^m} - ar^{m + 1}. \end{align*}\] This yields the formula \(S = \frac{a - ar^{m + 1}}{1 - r}\). Mnemonic: take the initial term and subtract from it the term which would come after the last term (first minus next) over \(1 - r\).

Combining this with the generating functions \(\frac{x}{1 - x}\) for \(L_2, L_3, \dots, L_k\), our restricted problem has an overal generating function of \[ \frac{x^5 - x^{14}}{1 - x} \cdot \left( \frac{x}{1 - x} \right)^{k - 1} = \frac{x^{k - 1}(x^{5} - x^{14})}{(1 - x)^k}. \]

We will cover how to read the number of solutions from such a generating function in the next section. For now, let’s address one last modification.

General Method

Let \(L_1\) represent the possible number of objects person \(1\) can receive. E.g.

  • if person \(1\) receives \(0\) or more, then \(L_1 = \{\varepsilon, 1, 11, 111, \dots\}\)—with OGF \(x^0 + x^1 + x^2 + \cdots = \frac{1}{1 - x}\)
  • if person \(1\) receives \(1\) or more, then \(L_1 = \{1, 11, 111, \dots\}\)—with OGF \(x^1 + x^2 + x^3 + \cdots = \frac{x}{1 - x}\)
  • if person \(1\) receives \(0, 1, 2\), then \(L_1 = \{\varepsilon, 1, 11\}\)—with OGF \(x^0 + x^1 + x^2\)
  • if person \(1\) receives an even number, then \(L_1 = \{\varepsilon, 11, 1111, \dots\}\)—with OGF \(x^0 + x^2 + x^4 + \cdots = \frac{1}{1 - x^2}\).

Do this for each person and then multiply the OGFs together for the full problem.

13.3 Slack variables

Consider the problem \[ x_1 + x_2 + \dots + x_k \le n \] with \(x_i \ge 0\).

The method for solving this is to add a slack variable \(y\) with \(y \ge 0\). This adds to our proceedure a \(k + 1\)-st language \(L_y\). This gives us the generating function

\[ \frac{1}{(1 - x)^{k + 1}} = \sum_{n = 0}^\infty \binom{n + k}{k} x^n \]

Indeed, the coefficient \(\binom{n + k}{k}\) matches our previous solution to this problem.

If on the other hand we had \(x_i \ge 1\) then the generating functions for the \(L_i\) languages is \(\frac{x}{1 - x}\) and we multiply this still by \(\frac{1}{1 - x}\) for \(L_y\). Here there is an asymmetry between \(L_y\), which contains the empty string, and the languages \(L_i\) which don’t. So for this problem, we have

\[ \frac{x^k}{(1 - x)^{k + 1}} = x^k \sum_{n = 0}^\infty \binom{n + k}{k} x^n = \sum_{n = 0}^\infty \binom{n + k}{k} x^{n + k} = \sum_{n = k}^\infty \binom{n}{k} x^n. \]

13.4 Summary

  1. For \(x_1 + \dots + x_k = n\) and \(x_i \ge 0\), we have the OGF \[ \frac{1}{(1 - x)^k} = \sum_{n = 0}^\infty \binom{n + k - 1}{k - 1} x^n. \]
  2. For \(x_1 + \dots + x_k = n\) and \(x_i \ge 1\), we have the OGF \[ \frac{x^k}{(1 - x)^k} = \sum_{n = k}^\infty \binom{n - 1}{k - 1} x^n. \]
  3. For \(x_1 + \dots + x_k \le n\) and \(x_i \ge 0\), we have the OGF \[ \frac{1}{(1 - x)^{k + 1}} = \sum_{n = 0}^\infty \binom{n + k}{k} x^n. \]
  4. For \(x_1 + \dots + x_k = n\) and \(x_i \ge 1\), we have the OGF \[ \frac{x^k}{(1 - x)^{k + 1}} = \sum_{n = k}^\infty \binom{n}{k} x^n. \]