6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I might miss something, but polynomial coefficient seems to work: $\binom{n}{2k} \cdot \binom{n-2k}{2j} \cdot \binom{n-2k -2j}{2m}$ $\endgroup$ – Alex Feb 13 '15 at 13:26
  • $\begingroup$ @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. $\endgroup$ – coredump Feb 13 '15 at 13:39
  • $\begingroup$ Yes, but it seems like not every $\binom{2n}{2k}$ is even, e.g. $\binom{6}{4}$ $\endgroup$ – Alex Feb 13 '15 at 14:56
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – coredump Feb 13 '15 at 21:04
  • 1
    $\begingroup$ @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. $\endgroup$ – Rus May Feb 13 '15 at 23:41
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Harald Feb 13 '15 at 21:10
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Feb 13 '15 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.