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.