From A Walk Through Combinatorics by Bona in the section on generating functions
We have n cards. We want to split them into an even number of non-empty subsets, form a line within each subset, then arrange the subsets in a line. In how many different ways can we do this?
My immediate reaction was to set $a_n=n!$ for $ n\ge2 $ and $b_n =\begin{cases}
0, & \text{if $n$ is odd} \\
n!, & \text{if $n$ is even} \\
\end{cases}$
And use the exponential compositional formula $G(x)=B(A(x))$ but I realized that this won't work as this counts the number of cards inside each subset as even versus the number of subsets as even. I also failed trying to find a recurrence relation.
Also, on a related problem I ended up with the recurrence relation for the exponential series $G(x)$ as $g_{n+1}=ng_n+ \binom{n}{2}g_{n-2}$. I've had difficulty doing the algebra to show $$G(x)=\frac{e^{-x/2-x^2/4}}{\sqrt{1-x}}$$
from this recurrence relation, help would be greatly appreciated. I've gotten it to
$$G(x)-1=\sum_{n \ge0}\big(ng_{n+2}+ {n \choose 2}g_n)\frac{x^{n+3}}{(n+3)!} $$
and not quite sure where to go with that.
Best Answer
We're in the same class! I am too struggling with the same problem. As for the second problem you referenced, after multiplying your recurrence relation by $\frac{x^{(n+2)}}{(n+2)!}$ and summing for all n, decompose it to a differential equation of $\frac{G'(x)}{G(x)}$ and solve from there. Hopefully that hint will help.