I am faced with the following question from my undergraduate Combinatorics class:
There are n aisles in a shop. We want to separate them into consecutive nonempty groups for different categories of items. Also, each category will be colored white, black, or grey, and we'll select a nonempty subset of the categories to be shown in a magazine. Let hn = the number of ways to do this. Express H(x) = $\sum_{n\ge0} h_nx^n$ as a rational function.
We are currently studying compositions of generating functions. I understand that the idea is to let $a_n$ be a sequence which is the number of ways to pick something of order, $b_n$ is the number of ways to pick the subsets,... and then compose H(x)=B(A(x)).
What I am struggling with is how exactly to define $a_n$ and $b_n$ in terms of the given information. For example, I thought about saying $a_n$ = # ways to assign white/black/grey to n aisles and $b_n$ = # ways to pick a non-empty subset of n items. But, I don't know how to account for the fact that the aisles will be given colorings.
Any help would be greatly appreciated, thank you for your time!
Let's start with the number of ways to break $n$ aisles into groups of consecutive aisles. One group may contain $1,2,3, \dots$ aisles, so its GF is $$z + z^2 + z^3 + \cdots = \frac{z}{1-z}$$ The shop consists of a sequence of such groups, so the GF for the number of ways they can be selected is $$F(z) = \frac{1}{1 -\frac{z}{1-z}} = \frac{1-z}{1-2z}$$ (You may recognize $F(z)$ as the GF for the number of "compositions" of an integer.)
A set of $n$ objects can be three-colored in $3^n$ ways, so if the GF for some collection objects is $a_0 + a_1 z + a_2 z^2 + a_3 z^3 + \dots$, then the GF for the number of ways to three-color the objects is $a_0 + 3 a_1 z + 3^2 a_2 z^2 + 3^3 a_3 z^3 + \dots$.
So the GF for the number of ways to three-color our collection of aisles is $$G(z) = F(3z)$$
Finally, the number of ways to select a non-empty subset of $n$ objects is $2^n-1$. If a collection of objects has GF $a_0 + a_1 z + a_2 z^2 + a_3 z^3 + \dots$, then the GF for the number of ways to select a non-empty subset is $(2-1) z + (2^2-1)z^2 + (2^3-1)z^3 + \dots$.
So the GF for the number of ways to select a non-empty subset of the three-colored aisle collection is $$H(z) = G(2z) - G(z)$$