Number of strings, when each character must occur even times

Question

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.

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

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

Answer 3

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

---

In general, given positive integers $n,a,b$ for which $b\le a$, let $E_n(a,b)$ be the number of sequences of length $n$, with entries in $\{1,\dots,a\}$, such that for each $i\in \{1,\dots,b\}$, $i$ appears an even number of times (so only $b$ of the symbols are required to appear evenly). The original problem was about $E_n(4,4)$.

I will give a combinatorial proof that $$ 0<b < a\implies E_n(a,b)=\frac12\Big(E_n(a,b-1)+E_n(a-2,b-1)\Big) $$

Proof: Let $S$ be the set of strings in $\{1,\dots,a\}^n$ where each $i\in \{1,\dots,b-1\}$ appears evenly, so $|S|=E_n(a,b-1)$. We want to count the strings in $S$ that satisfy the additional requirement that $b$ appears evenly. Define a $(\mathbb Z/2\mathbb Z)$-action on $S$ as follows: find the first instance of either $b$ or $a$, and then replace it with the other symbol, $a$ or $b$. Each orbit either has a single sequence, in the case that neither $b$ or $a$ appears, or exactly two sequences. In the either case, exactly one sequence in each pair has an even number of $b$'s, so the number of orbits is the desired answer. The formula above is exactly the result of using Burnside's Lemma to count the number of orbits.

This then immediately leads to a proof by induction that $$ b<a\implies E_{n}(a,b)=2^{-b}\sum_{k=0}^b \binom{b}k (a-2k)^{n} $$

In fact, the above formula is also true in the case where $b=a$, which can be shown in two cases.

• If $n$ is odd, then $2^{-a}\sum_{k=0}^a \binom{b}k (a-2k)^{n}=0$, which is obviously also equal to the number of sequences of length $n$ where each character appears evenly.

• If $n=2m$ is even, then we have $$E_{2m}(a,a)=E_{2m}(a,a-1)=2^{-(a-1)}\sum_{k=0}^{a-1}\binom{a-1}k(a-2k)^{2m}=2^{-a}\sum_{k=0}^a \binom{a}k (a-2k)^{2m}.$$ The first equality is true because if every symbol in $\{1,\dots,a-1\}$ appears evenly, then $a$ appears evenly automatically. The third equality can be proved by some simple algebra. If you collect like terms, noting that $(a-2k)^{2m}=(a-2(a-k))^{2m}$, then the coefficient of $(a-2k)^{2m}$ is equal to $2^{-(a-1)}\left(\binom{a-1}k+\binom{a-1}{a-k}\right)$ for the LHS, and is equal to $2^{-a}\left(\binom{a}k+\binom{a}{a-k}\right)$ for the RHS, and these plainly equal each other.

Therefore, we have proved that the number of sequences of length $n$, in $a$ characters, where every character appears evenly, is $2^{-a}\sum_{k=0}^a \binom{a}k (a-2k)^{n}$.