2
$\begingroup$

Let $n$ be a positive integer. If each $a_i$ is chosen from $\left\{ 0,1,2, \dots, 9 \right\},\;$ $1\leq i\leq n$, then how many strings of length $n$ ($a_1a_2\dots a_n$) are there such that the number of occurrences of $0$ is even? Thanks!

1 Answers 1

6

Let us fix the alphabet as $\{0, 1, 2, \dots, M\}$ (we'll later take $M = n$). Let $a_n$ be the number of strings of length $n$ which contain an even number of $0$s, and $b_n$ be the number of strings of length $n$ which contain an odd number of $0$s. Note that there are $(M+1)^n$ strings of length $n$ over that alphabet, so $a_n + b_n = (M+1)^n$. For $n = 0$, we can see that $a_0 = 1$ (the empty string) and $b_0 = 0$.

We can write down recurrence relations for $a_n$ and $b_n$. If we consider how we can get a string of length $n+1$ by appending a symbol (either $0$ or one of $1, \dots, M$) to a string of length $n$, we can see that:

$\begin{align} a_{n+1} &= Ma_n + b_n\\ b_{n+1} &= a_n + Mba_n \end{align}$

Writing $X_n = \pmatrix{a_n \\ b_n}$, this means

$\begin{align} X_0 &= \pmatrix{1 \\ 0} \\ X_{n+1} &= \pmatrix{M & 1 \\ 1 & M}X_n \end{align}$

Calling the matrix $T = \pmatrix{M & 1 \\ 1 & M}$, this means $X_n = T^nX_0$. You can verify that $T^n = \frac12 \pmatrix{(M-1)^n+(M+1)^n & (M+1)^n-(M-1)^n \\ (M+1)^n-(M-1)^n & (M-1)^n+(M+1)^n}$ which gives $\pmatrix{a_n \\ b_n} = X_n = T^nX_0 = T^n\pmatrix{1 \\ 0} = \frac12 \pmatrix{(M-1)^n+(M+1)^n \\ (M+1)^n-(M-1)^n}$ and in particular $a_n = \frac{(M-1)^n+(M+1)^n}{2}$ or when $M = n$, $a_n = \frac{(n-1)^n+(n+1)^n}{2}.$


Alternatively, as $b_n = (M+1)^n - a_n$, the recurrence $a_{n+1} = Ma_n + b_n$ is the same as $a_{n+1} = Ma_n + ((M+1)^n - a_n) = (M-1)a_n + (M+1)^n$. Here, letting $c_n = 2a_n - (M+1)^n$, note that the recurrence becomes: $\begin{align} a_{n+1} &= (M-1)a_n + (M+1)^n \\ 2a_{n+1} - (M+1)^{n+1} &= 2(M-1)a_n + 2(M+1)^n - (M+1)^{n+1} \\ &= 2(M-1)a_n + (M+1)^n(2 - (M+1)) \\ &= 2(M-1)a_n - (M+1)^n(M-1) \\ &= (M-1)(2a_n - (M+1)^n) \\ c_{n+1} &= (M-1)c_n \end{align}$ and $c_0 = 2a_0 - 1 = 2 - 1 = 1$, so $c_n = (M-1)^n$, which gives $a_n = ((M-1)^n + (M+1)^n)/2$ as before.


Of course, there is also probably an easy combinatorial proof showing why $a_n = ((n-1)^n+(n+1)^n)/2$; I can't think of one right now.

  • 2
    Partly combinatorial I believe: The number of strings with $2r$ zeroes is $\binom{n}{2r} M^{n-2r}$. Add up and use binomial theorem.2012-11-01