Trouble with counting the number of closed walks on a $n$-cube I was trying to understand the second answer to the post Number of closed walks on an n-cube by @Ira Gessel.
I understand the first part, that the closed walks of length $r$ on a n-cube can equals $2^n$ times the number of words of length $r$ using the alphabet ${1,2, \cdots, n}$ in which every letter appears an even number of times.
This argument is the starting point of the second and third answer, and I actually can see how the third proceeds further from there to the final result.
The second answer is nevertheless obscure to me.
it says, mid of first paragraph, "<...>The words that encode walks that start and end at the origin are encoded as shuffles of words of the form $ i -i \,\,\,  i -i \cdots i -i   $, for $i$  from $1$ to $n$.
Since for each $i$ there is exactly one word of this form for each even length, the number of shuffles of these words of total length $m$ is the coefficient of $x^m / m! $ in $$\Big( \sum_{k=0}^{\infty} \frac{x^{2k}}{(2k)!} \Big)^n = \Big( \frac{e^x + e^{-x}}{2}\Big)^n$$ <...>"
I cannot figure this out. I am not so sure I understand the encoding itself, but even more puzzling is where from does the conclusion comes, that the he number of shuffles of these words of total length $m$ is the coefficient of $x^m / m! $  in that hyperbolic function, cannot grasp it, would anyone please care to give us a hint?
 A: In order to understand @IraGessel's answer, we need to first understand what is meant by the word shuffle. The shuffle here means an interleaving of the two words, e.g. the shuffle of $ab$ and $c$ can either be
$$cab,\ acb,\text{ or } abc. $$
The number of these for words $u$,$v$ with letters from distinct letter sets is always
$$\frac{(|u|+|v|)!}{|u|!|v|!}.$$
This is because there are there are $(|u|+|v|)!$ ways to order all the letters, and we divide by $|u|!$ since we know the order of the letters in $u$, and $|v|!$ since we know the order of the letters in $v$.
Repeating this for $u_1,u_2,\cdots,u_n$ with letters from distinct letter sets, we get
$$\frac{(|u_1|+\cdots+|u_n|)!}{|u_1|!\cdots|u_n|!}$$
Now, letting $u_i$ be the sequence of $i\ - i\cdots$, then letting $2k_i=|u_i|$ and $m=\sum_i 2k_i$, we get the number of shuffles of these is
$$\frac{m!}{\prod_i (2k_i)!}$$
And to find the number of these for some total length $m$, we just range over all possible $k_i$, so we get
$$m!\sum_{\sum_i 2k_i = m}\prod_i \frac{1}{(2k_i)!} $$
And to represent this in a succinct way, we use generating functions and look for the coefficient of $x^m$ in
$$ m!\prod_i \sum_{k_i=0}^\infty \frac{x^{2k_i}}{(2k_i)!} = m! \left(\sum_{k=0}^\infty \frac{x^{2k}}{(2k)!} \right)^n$$
The idea behind using generating functions here is that exponents add in multiplication, so we know that $\prod_i x^{2k_i} = x^m$ iff $\sum_i 2k_i = m$.
