Seemingly simple combinatorial problem

Question

Count all $n$-length strings of digits $0, 1,\dots, m$ that have an equal number of $0$'s and $1$'s. Is there a closed form expression?

Answer 1

Assuming we want the number of strings of $n$ characters over the alphabet $\{0,\ldots,m\}$ with the same number of "zeroes" and "ones" we just have to compute: $$\sum_{j=0}^{\lfloor n/2\rfloor}\binom{n}{2j}\binom{2j}{j}(m-1)^{n-2j}.$$ Reason: set $j$ as the number of zeroes, then choose the $2j$ over $n$ places where putting all the zeroes and ones, then choose where to put the zeroes over such $2j$ positions, the choose how to fill the remaining part of the string with characters from $\{2,\ldots,m\}$ ($(m-1)$ possible choices).

Expanding $(m-1)^{n-2j}$ with the binomial theorem we get: $$\sum_{j=0}^{\lfloor n/2\rfloor}\binom{n}{2j}\binom{2j}{j}\sum_{k=0}^{n-2j}\binom{n-2j}{k}m^k (-1)^{n-2j-k},$$ and the balanced strings are generated by the grammar: $$ S \to 0S1,1S0,SS,\varepsilon.$$

Answer 2

This can be computed recursively. For $m\ge1$, let $f_m(n,d)$ be the number of $n$-letter strings over the alphabet $\{0,\dots,m\}$ containing exactly $d$ more $0$’s than $1$’s. Then $f$ satisfies the following, which provides a recursive definition:

$$\begin{align} f_m(0,0)&=1\\ f_m(0,d)&=0\mbox{ if }d\ne0\\ f_m(n,d)&=f_m(n-1,d-1)+(m-1)f_m(n-1,d)+f_m(n-1,d+1)\\ \end{align}$$

The last of these equestions can be explained by considering how a string of length $n$ containing $d$ more $0$’s than $1$’s can be built by appending a digit to a string of length $n-1$. It can be built by appending a $0$ to a string among those counted by $f_m(n-1,d-1)$, by appending a digit other than a $0$ or $1$ (there are $m-1$ such digits) to a string counted by $f_m(n-1,d)$, or by appending a $1$ to a string counted by $f_m(n-1,d-1)$.

For $m=9$, this gives the following sequence of answers to the original question, beginning with $n=0$:

$1$, $8$, $66$, $560$, $4870$, $43248$, $390804$, $3582048$, $33213510$, $310850480$, $2931397756$.

This sequence does not appear (yet) in the Online Encyclopedia of Integer Sequences.

(These results agree with the sum Jack D’Aurizio gave in his answer.)