Skip to main content

Chapter 16 Compositions of Generating Functions

Exercises Practice Problems

1. Organizing Jurors.

These two problems use composition of ordinary generating functions. Let \({\cal A}\) be a task with \(a_0=0\) and ordinary generating function \(A(x) = \sum_{n=1}^{\infty} a_n x^n\text{.}\) Let \({\cal B}\) be the task "split the interval \([n]\) into nonempty intervals and perform \({\cal A}\) on each interval." Then the ordinary generating function for \({\cal B}\) is

\begin{equation*} B(x) = \frac{1}{1-A(x)}. \end{equation*}

  1. Suppose that we have \(n\) prospective jurors, each assigned a number. We want to split the jurors into some number of intervals (the first \(k_1\) jurors, the next \(k_2\) jurors and so on).

    1. Find the value of \(b_n\text{.}\) Solution.

      \begin{equation*} B(x) = 1 + \frac{x}{1-2x} = 1 + x \sum_{n=0}^{\infty} (2x)^n = 1 + \sum_{n=0}^{\infty} 2^n x^{n+1} = 1 + \sum_{m=1}^{\infty} 2^{m-1} x^{m}. \end{equation*}

      So \(b_0=1\) and \(b_n = 2^{n-1}\) for \(n \geq 1\text{.}\)

    2. Give a combinatorial proof of your value in (b). (Hint: if you haven't yet done so, simplify your answer in (b) to a single term.) Solution.

      Place the jurors in a line. We have to decide where to divide them. There are \(n-1\) spaces between jurors where we can choose to make a new interval. Each of these choices is made independently. So the product principle gives the number of ways as \(2^{n-1}\text{.}\)

  2. Now, once we have split the people into groups, we want to do some further organization. We must choose a foreman, and then the remaining people will be designated as juror, alternate or dismissed. Find the generating function \(B(x)\) for the total process (splitting the pool and then assigning roles). Solution.

    For a group of size \(n\text{,}\) the number of ways to choose a foreman and then choose one of 3 roles for the remaining people is \(n 3^{n-1}\text{.}\) Once again, we must take \(a_0=0\text{,}\) so

    \begin{equation*} \begin{array}{rcl} A(x) &=& \sum_{n=1}^{\infty} n 3^n x^n = 3x \sum_{n=1}^{\infty} n 3^{n-1} x^{n-1} = \frac{3x}{(1-3x)^2} \\ B(x) &=& \frac{1}{1-A(x)} = \frac{1}{1- \frac{3x}{(1-3x)^2}} = \frac{(1-3x)^2}{1-9x+9x^2} = 1 + \frac{3x}{1-9x+9x^2} \end{array} \end{equation*}

2. Organizing Employees.

These three problems use composition of exponential generating functions. Let \({\cal A}\) be a task with \(a_0=0\) and exponential generating function \(A(x) = \sum_{n=1}^{\infty} a_n \frac{x^n}{n!}\text{.}\) Let \({\cal B}\) be the task "partition \([n]\) into nonempty subsets and perform \({\cal A}\) on each subset." Then the exponential generating function for \({\cal B}\) is

\begin{equation*} B(x) = e^{A(x)}. \end{equation*}

  1. Suppose that we have \(n\) employees. We want to partition them into some number of nonempty subsets. Use the composition result above to find a formula for the corresponding exponential generating function \(B(x)\text{.}\) You should recognize this marvelous generating function. Solution.

    Once again, we remember that we must have \(a_0=0\) to use the theorem. Otherwise, we once again consider the "do nothing" task, which can be done in one way.

    \begin{equation*} \begin{array}{rcl} A(x) &=& \sum_{n=1}^{\infty} \frac{x^n}{n!} = e^x -1 \\ B(x) &=& e^{A(x)} = e^{e^x-1} \end{array} \end{equation*}

    This is the generating function for the Bell numbers: the total number of ways to partition a set into any number of parts. We derived this formula a few days ago, starting from the Bell recurrence. This way is much easier!

  2. Now, each subset will become a committee, so we need to elect a chair. Give the exponential generating function \(B(x)\) for the entire process (partitioning and then choosing a chair for each committee.) Solution.

    Of course, we force \(a_0=0\text{.}\) Otherwise, \(a_n = n\text{.}\) So

    \begin{equation*} \begin{array}{rcl} A(x) &=& \sum_{n=1}^{\infty} n\frac{x^n}{n!} = x\sum_{n=1}^{\infty} \frac{x^{n-1}}{(n-1)!} = x\sum_{m=0}^{\infty} \frac{x^{m}}{m!} = x e^x \\ B(x) &=& e^{A(x)} = e^{xe^x} \end{array} \end{equation*}

  3. Instead of forming a committee, we want to seat each group at a circular table.

    1. Find the exponential generating function \(B(x)\) for this process. Solution.

      We force \(a_0=0\text{,}\) and otherwise, \(a_n = (n-1)!\text{.}\) So

      \begin{equation*} \begin{array}{rcl} A(x) &=& \sum_{n=1}^{\infty} (n-1)!\frac{x^n}{n!} = \sum_{n=1}^{\infty} \frac{x^n}{n} = \log \left( \frac{1}{1-x} \right) \\ B(x) &=& e^{A(x)} = \exp \left( \log \left( \frac{1}{1-x} \right) \right) = \frac{1}{1-x} \end{array} \end{equation*}

    2. Use \(B(x)\) to find the value of \(b_n\text{.}\) Be amazed at the simplicity of the answer for this complicated question! Solution.

      Remember that \(B(x)\) is an exponential generating function!

      \begin{equation*} B(x)= \frac{1}{1-x} = \sum_{n=0}^{\infty} x^n = \sum_{n=0}^{\infty} n! \frac{x^n}{n!} \end{equation*}

      So the number of ways to split into any number of groups and then seat each group at a circular table is \(b_n=n!\) This is a ridiculously simple formula for such a complex procedure.