# 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.

• I might miss something, but polynomial coefficient seems to work: $\binom{n}{2k} \cdot \binom{n-2k}{2j} \cdot \binom{n-2k -2j}{2m}$ – Alex Feb 13 '15 at 13:26
• @Alex In your formula, do $k$ $j$ and $m$ stand for half the number of occurences of each character? I understand it as: choose first $2k$ elements from $n$, then $2j$ from $n-2k$, and so on...? Are $k$, $j$ and $m$ supposed to be known? Sorry, I have very little experience with this. – coredump Feb 13 '15 at 13:39
• Yes, but it seems like not every $\binom{2n}{2k}$ is even, e.g. $\binom{6}{4}$ – Alex Feb 13 '15 at 14:56

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).

• I am very impressed. I should have a look at generating functions. Thanks a lot, I'll study this and try to understand what it all means. – coredump Feb 13 '15 at 21:04
• @coredump: If you want to take a look at generating functions, one excellent place to start is Herb Wilf's free book: math.upenn.edu/~wilf/gfologyLinked2.pdf. After reading his book, I was hooked. – Rus May Feb 13 '15 at 23:41

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*}

• May I ask you to explain how you get from the line headed by 'is' to the line headed by 'so'. Do you have a pointer to a book or literature where I could look this up? – Harald Feb 13 '15 at 21:10
• @Harald: This PDF is a concise introduction to exponential generating functions. This PDF has a more general introduction to generating functions. Miklós Bóna, Introduction to Enumerative Combinatorics, is very readable and has everything that you need on the subject. I suspect that the same goes for his A Walk Through Combinatorics, but I’ve not actually seen it. – Brian M. Scott Feb 13 '15 at 21:26