Number of strings, when each character must occur even times

Solution 1:

Generating functions can be applied to this problem. However, since the order of letters in a string is important, exponential generating functions are appropriate (not ordinary ones). So, suppose the alphabet $S$ has $m$ letters and let $a_n$ be the number of strings of length $n$ over the alphabet $S$ with an even number of each letter. Let $g(x)=\sum_{n\ge0}\frac{a_n}{n!}x^n$ be the exponential generating function of $\langle a_n:n\ge0\rangle$. Then, $$g(x)=\left(\sum_{n\textrm{ even}}\frac{x^n}{n!}\right)^m=\left(\frac{e^x+e^{-x}}2\right)^m.$$

In the case of $m=4$, $g(x)=\frac1{16}(e^{4x}+4e^{2x}+6+4e^{-2x}+e^{-4x})$. Then, $a_n=\left[\frac{x^n}{n!}\right]g(x)$ and if $n$ is even, $a_n=\frac{n!}{16}\left(\frac{2\cdot4^n}{n!}+\frac{8\cdot2^n}{n!}\right)=\frac18(4^n+4\cdot2^n)$. In particular, $a_4=40$.

Note: based on the form of the solution of $a_n$, I suspect there's a direct combinatorial argument (but I don't know it).

Solution 2:

Let $m=|S|$ be the number of distinct characters, and let $a_n$ be the number of strings in $S^n$ having an even number of each character in $S$. Let

$$g(x)=\sum_{n\ge 0}\frac{a_n}{n!}x^n$$

be the exponential generating function (egf) for $\langle a_n:n\in\Bbb N\rangle$. (The egf is wanted because the order of the characters matters.) The egf for the sequence given by $$a_n=\begin{cases}0,&\text{if }n\text{ is odd}\\1,&\text{if }n\text{ is even}\end{cases}$$ is

$$\sum_{n\ge 0}\frac1{(2n)!}x^{2n}=\frac12(e^x+e^{-x})\;,$$

so

$$g(x)=\left(\sum_{n\ge 0}\frac1{(2n)!}x^{2n}\right)^m=\frac1{2^m}(e^x+e^{-x})^m\;.$$

Now

$$\begin{align*} (e^x+e^{-x})^m&=\sum_{k=0}^m\binom{m}ke^{kx}e^{-(m-k)x}\\\\ &=\sum_{k=0}^m\binom{m}ke^{(2k-m)x}\\\\ &=\sum_{k=0}^m\binom{m}k\sum_{n\ge 0}\frac{(2k-m)^n}{n!}x^n\\\\ &=\sum_{n\ge 0}\frac1{n!}\left(\sum_{k=0}^m\binom{m}k(2k-m)^n\right)x^n\;, \end{align*}$$

so

$$a_n=\frac1{2^m}\sum_{k=0}^m\binom{m}k(2k-m)^n\;.\tag{1}$$

Note that $2(m-k)-m=m-2k=-(2k-m)$, so $(1)$ is indeed $0$ when $n$ is odd. When $n$ is even and positive we can rewrite $(1)$ as

$$a_n=\frac1{2^{m-1}}\sum_{k=0}^{\lfloor m/2\rfloor}\binom{m}k(m-2k)^n\;.$$

For instance, if $m=4$, then

$$\begin{align*} a_{2n}&=\frac18\left(\binom40(4-0)^{2n}+\binom41(4-2)^{2n}+\binom42(4-4)^{2n}\right)\\\\ &=\frac18\left(4^{2n}+4\cdot2^{2n}\right)\\\\ &=\frac18\left(4^{2n}+4^{n+1}\right)\\\\ &=2\cdot4^{n-1}\left(4^{n-1}+1\right)\;. \end{align*}$$