# How do I show that $h_n=\begin{cases}n!2^{\frac{n}{2}-1} , \text {if$n$is even} \\ 0, \text{if$n$is odd} \end{cases}$

We have $n$ distinct cards. We want to split these cards into non-empty subsets so that each subset contains even number of elements. Then we want to order the cards in each subset. Finally we want to order these subsets into a line. Let $h_n$ be the number of ways to build this structure. $h_n$?

Now
$$a_j= \begin{cases} j!, &\text{if j>0 is even}\\ 0, &\text{otherwise} \end{cases},$$ and $b_k=k!, b_0=1$.

So, $$A(x)=\sum_{n\geq 1}(2n)!\frac{x^{2n}}{(2n)!}=\sum_{n\geq 1}x^{2n}=\frac{x^2}{1-x^2}$$ and $$B(x)=\sum_{k\geq 0}(k)!\frac{x^{k}}{(k)!}=\sum_{k\geq 0}x^k=\frac{1}{1-x}$$

Then $h_0=1$ and $$\begin{split} \sum_{n\geq 0}h_n\frac{x^n}{n!} &= H(x)\\ &= B(A(x))\\ &=\frac{1}{1-\frac{x^2}{1-x^2}}=\frac{1}{1-2x^2}-\frac{x^2}{1-2x^2}\\ &=\sum_{n\geq 0}2^nx^{2n}-\sum_{n\geq 0}2^nx^{2n+2}\\ &=1+\sum_{n\geq 1}2^nx^{2n}-\sum_{n\geq 1}2^{n-1}x^{2n}\\ &=1+\sum_{n\geq 1}(2^n-2^{n-1})x^{2n}\\ &=1+\sum_{n\geq 1}2^{n-1}x^{2n}\\ &=1+\sum_{n\geq 1}{2^{n-1}n!}\frac{x^{2n} }{n!} \end{split}$$

Now how do I show that $$h_n=\begin{cases}n!2^{n/2-1}, & \text{if n is even} \\ 0, & \text{if n is odd} \end{cases}$$

## 1 Answer

Note $$\sum h_n \frac{x^n}{n!} = 1 + \sum_{n \ge 1} 2^{n-1}x^{2n} = 1 + \sum_{n \ge 1} 2^{n-1} (2n)! \frac{x^{2n}}{(2n)!}$$ and using $k=2n$ to make sure $k$ is even, we get $$\sum_{k \text{ even}} 2^{k/2-1} k! \frac{x^k}{k!}$$ as desired.