Number of strings, when each character must occur even times I was reading this question on programmers.StackExchange and wanted to try a combinatorics approach to solve the following problem:

Let $S=\{A,B,C,D\}$ be a set of characters and $n$ a positive natural,
  find the number of strings of length $n$ composed of characters in $S$
  such that each character occur even times.

I tried to solve it by myself but I am stuck and I would appreciate a hint to solve this kind of problems. Also, there are similar questions on this site for not quite exactly the same problem, but I didn't find an answer that could help me.
Current attempt
First, when $n$ is odd, the result must be zero. A string satisfying the desired property would necessarly have an even length, as a permutation of the concatenation of substrings of even lengths (each substring being a character from $S$ repeatead even times).
Now, let's suppose that $n$ is even.
If we have a mapping $c$ from $S$ to $\mathbb{N}$ assigning the number of occurence of each character (e.g. $c_A=0, c_B=2, c_C=4, c_D=0$), then the number of strings $N(c)$ we can produce with this mapping would be a k-permutation of characters, as we choose a string of size $n$ with $c_A$ times $A$, $c_B$ times $B$, etc. :
$$N(c) = \frac{n!}{c_A! c_B! c_C! c_D!}$$
Also, I can evaluate the number of such mappings $c$: this is equivalent to finding the number of strings where characters appear in order with varying occurences. For example, with $n=4$:
$$\begin{array}{c|cccc}
&            c_A & c_B & c_C &c_D \\
\hline
     AAAA &  4 & 0 & 0 & 0 \\
     AABB &  2 & 2 & 0 & 0 \\
     AACC &  2 & 0 & 2 & 0 \\
\dots\\
\end{array}
$$
The number of strings of size $n$ with an even number of each character is exactly the same as the number of strings of size $k=n/2$ with single characters (just imagine that AA, BB, CC, DD are characters).
So, the number of mappings is the number of combinations of characters from $S$, with repetition, like the following ones with $k=2$:
AA AB AC AD
BB BC BD
CC CD
DD

That is given as a $k$-combination of 4 elements:
$$ N_{mapping}(k) = \binom{|S|+k-1}{k} = \binom {3+k}{k}$$
This is where I'am stuck. I wanted to combine this number of mappings with the number of permutations computed by each mapping, previously, but I can't ($N(c)$ depends on actual values of the mapping $c$).
Also, I am sure there is a more straightforward approach, but I don't know how to proceed. Thanks for any help you could provide.
 A: 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).
A: 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*}$$
A: As suggested by Rus May at the end of their answer, there is a combinatorial solution. From now on, assume that $n$ is even.
Let $S$ be the set of words of length $n$ where the number of $A$'s plus the number of $B$'s is even. Consequently, for every word in $S$, we also have $\#C's+\#D's$ is even. First of all, I claim $S$ accounts for exactly half of the words in $\{A,B,C,D\}^n$, that is, $|S|=4^n/2$. Indeed, if you take a word in $S$, and change the first letter according to the rule below, then you get a word not in $S$:
$$
A\leftrightarrow C,\qquad B\leftrightarrow D
$$
This correspondence between $S$ and its complement is a bijection.
Now, among the words in $S$, let us count the number of words where all letter counts are even. We do this in several cases:

*

*Let $S_{c,d}$ be the set of words in $S$ which consist only of the letters $C$ and $D$. In exactly half of these words, both $C$ and $D$ appear evenly (why?). Therefore, there are $2^{n-1}$ all-even words in $S_{c,d}$.


*Similarly, letting $S_{a,b}$ be the set of words in $S$ made of $A$ and $B$ alone, there are $2^{n-1}$ all-even words in $S_{a,b}$.


*All that remains are words which have at least one $A$ or $B$, and at least once $C$ or $D$. I claim that exactly one fourth of these words have all letters appearing evenly. Indeed, we can partition these words into groups of four, where exactly one word in each group has all letters appearing evenly. The group containing $w$ consists of...

*

*$w$ itself.

*The word formed by finding the first occurrence of $A$ or $B$ in $w$, and replacing it with the other letter ($B$ or $A$). Call this new word $T_{a,b}(w)$, where $T$ stands for "toggle".

*The word $T_{c,d}(w)$, where you instead toggle the first $C$ or $D$.

*The word $T_{c,d}(T_{a,b}(w))$, where you toggle $A/B$ and $C/D$.

Since there are $4^n/2-2^{n-1}-2^{n-1}$ words in $|S-S_{a,b}-S_{c,d}|$, and exactly one fourth of these are valid, the number of valid words in this group is$$\frac{4^n/2-2^{n-1}-2^{n-1}}4=\tfrac18(4^n-4\cdot 2^n)$$
Adding this altogether, the number of all-even words is $2^{n-1}+2^{n-1}+\tfrac18(4^n-4\cdot 2^n)=\frac18(4^n+4\cdot 2^{n})$.
