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?
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$.