Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
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. –  Aryabhata Nov 1 '12 at 16:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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