1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Welcome to Math.SE! Here's a quick guide on how to write math on this site: meta.math.stackexchange.com/questions/5020/… $\endgroup$ – Newb Nov 6 '13 at 0:42
  • $\begingroup$ Thank you for the edit, Newb. And Eric, if you are able to solve your problem, please report back! $\endgroup$ – Scott Nov 6 '13 at 2:20
  • $\begingroup$ 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. $\endgroup$ – Eric Kaschalk Nov 6 '13 at 2:33
  • $\begingroup$ 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. $\endgroup$ – Scott Nov 6 '13 at 2:42
  • $\begingroup$ As for the link you found, that details how to create blocks of even size, not to split into an even number of blocks. $\endgroup$ – Scott Nov 6 '13 at 3:25
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.