# Counting problem using exponential generating functions

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.

## 2 Answers

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.

• Welcome to Math.SE! Here's a quick guide on how to write math on this site: meta.math.stackexchange.com/questions/5020/… – Newb Nov 6 '13 at 0:42
• Thank you for the edit, Newb. And Eric, if you are able to solve your problem, please report back! – Scott Nov 6 '13 at 2:20
• I'm not any farther than what I've edited in on the second question. On the first one I found this link that may help, page 7, $e^{cosh(x)-1}$: math.berkeley.edu/~mhaiman/math172-spring10/exponential.pdf I'm trying to find a way to adapt it for this problem but the forming a line within each subset part is tripping me up. – Eric Kaschalk Nov 6 '13 at 2:33
• Wouldn't the ways to form a line within each subset simply be (n!) ? The part that I don't understand is splitting [n] into an even number of subsets. – Scott Nov 6 '13 at 2:42
• As for the link you found, that details how to create blocks of even size, not to split into an even number of blocks. – Scott Nov 6 '13 at 3:25

For the first problem you seem to have the combinatorial species $$\mathcal{Q} = \mathfrak{S}_{\mathrm{even}}(\mathfrak{S}_{\ge 1}(\mathcal{Z})).$$ This gives the exponential generating function $$Q(z) = \frac{z^2}{1-z^2} \circ \frac{z}{1-z} = \frac{z^2}{1-2z}$$ so the count is $$q_n = n! [z^n] \frac{z^2}{1-2z} = n! [z^{n-2}] \frac{1}{1-2z} = n! \times 2^{n-2}$$ for $n\ge 2.$ This gives the following sequence: $$2, 12, 96, 960, 11520, 161280, 2580480, 46448640, 928972800,\ldots$$ which is OEIS A014297. I am not sure I have understood your problem correctly but the description at the OEIS entry seems to match what you have.