What is wrong with my solution? Splitting the set [n] into non-empty intervals and choosing a non-empty subset from these intervals

Question

I am trying to solve this problem for my combinatorics class. Here is the problem:

Let $h_n$ be the number of ways to split the set [n] into some number of non-empty intervals and choose a non-empty subset from the set of these intervals. Show that $h_n$ = $2(3)^{n-1}$.

I tried to solve this problem using generating functions.

Here is my attempt so far:

I will use the product rule of generating functions. Let $F_{split}(x)$ be the generating function of splitting the set [n] into some number of non-empty intervals, and let $G_{choosing subset}(x)$ be the generating function of choosing a non-empty subset from the set of these intervals.

Then, $K(x) = F_{split}(x) \times G_{choosing subset}(x) = \sum_{n\geq0} (h_n)x^n$. I want to find $K(x)$, then find the coefficient of $x^n$ so I can find $h_n$.

$F_{split}(x) = \sum_{n\geq0} (2^n-1)x^n$ = $\sum_{n\geq0} (2x)^n - \sum_{n\geq0} (x)^n$

$= (\frac{1}{1-2x} - \frac{1}{1-x})$

and

$G_{choosing subset}(x) = \sum_{n\geq0} (2^{n-1})x^n$

$= \frac{\sum_{n\geq0} (2x)^n}{2}$

$= \frac{1}{2(1-2x)}$

Then,

$K(x) = \frac{1}{2-4x}\times(\frac{1}{1-2x} - \frac{1}{1-x})$

Now, applying partial fraction decomposition:

$= \frac{1-x}{(2-4x)(1-2x)(1-x)} - \frac{1-2x}{(2-4x)(1-x)(1-2x)}$

$= \frac{x}{(2-4x)(1-2x)(1-x)}$

Then,

$\frac{A}{2-4x}+\frac{B}{1-2x}+\frac{C}{1-x} = \frac{x}{(2-4x)(1-2x)(1-x)}$

But I cannot solve this equation because I have 3 unknown variables with 2 equations. So I just get:

$A+2B=-1$ and $C=\frac{1}{2}$

I would appreciate any hint or help!

Answer 1

I think it is quite tricky to make this work with generating functions. Here is the best I can do.

For each $n,k\ge 1$, let $f_{n,k}$ be the number of ways to split a list of length $n$ into exactly $k$ nonempty intervals. You can prove that $f_{n,k}=\binom{n-1}{k-1}$. There are $n-1$ spaces between the $n$ entries of the list; you need to select $k-1$ of these spaces, and break the list at the selected spaces.

Let $F(x,t)$ be the bivariate generating function for $f_{n,k}$. $$ \begin{align} F(x,t)&=\sum_{n\ge 1}\sum_{k=1}^n f_{n,k}\,x^nt^k \\&=\sum_{n\ge 1}x^n \sum_{k=1}^n \binom{n-1}{k-1}t^{k} \\&=\sum_{n\ge 1}x^n t(1+t)^{n-1} \\&=\frac{xt}{1-x(1+t)}. \end{align} $$ Why is this useful? Your question is about splitting the list into nonempty sublists, and then choosing a nonempty subset of those sublists. This means that the answer to your question is $$ \sum_{k=1}^n f_{n,k}\cdot (2^k-1) $$ This explains why we needed to keep track of $k$, the number of intervals. The number of ways to choose a nonempty subset of intervals depends on the number of intervals.

We can write the answer to this question in terms of $F(x,t)$: $$ \begin{align} \sum_{k=1}^n f_{n,k}\cdot (2^k-1) &=\sum_{k=1}^n f_{n,k}\cdot 2^k-\sum_{k=1}^n f_{n,k}\cdot 1^k \\&=[x^n]\Big(F(x,2)-F(x,1)\Big) \\&=[x^n]\left(\frac{2x}{1-3x}-\frac{x}{1-2x}\right) \\&= \boxed{2\cdot 3^{n-1}-2^{n-1}} \end{align} $$ The final answer to your question, as written, is $2\cdot 3^{n-1}-2^{n-1}$, and is not $2\cdot 3^{n-1}$, as your professor claims.

Answer 2

You multiply the generating functions when $h_n=\sum f_ig_{n-i}$, which isn't in this case.
To get powers of $3$, you need $1-3x$ in the denominator, and can't get there by multiplying those of $f$ and $g$.
Here is another way to count: $1$ is either chosen or not in the final collection. Then $i+1$ has three options: attach it to the same interval as $i$; start a new interval that will be chosen; or start a new interval that won't be chosen.
So $2×3^{n-1}$ is the count when the collection of intervals chosen may be empty.