How to form a recurrence for a $n$-digit sequence using digits $0,1,2,3$ so that we have even no of $0$'s?

Question

If we assume $T(n)$ to be the function representing the case where we have even number of $0$'s then $T(1)=3$ precisely strings $1, 2$ and $3$. $T(2)= 10$ ($00,11,22,33,12,21,13,31,23,32$). Likewise I got $T(3)=36$ and $T(4)=124$.

Now how to proceed from here?

Answer 1

Here is a variation of the theme based upon regular expressions. We can describe all valid strings as \begin{align*} (0(1+2+3)^*0+1+2+3)^* \end{align*}

Comment:

• Valid strings consist of zero or more occurrences of $1$ or $2$ or $3$ or

• when we start with a $0$ it has to be followed by another $0$ possibly with zero or more occurrences of $1,2$ or $3$ in between.

This was the hard part, namely finding an appropriate regular expression. Everything what follows is a matter of technique.

Using the notation from P. Flajolet's and R. Sedgewicks Analytic Combinatorics with the sequence $SEQ(x)$ defined as \begin{align*} SEQ(x)=1+x+x^2+\cdots=\frac{1}{1-x} \end{align*}

we can translate the regular expression into the generating function

\begin{align*} SEQ&(xSEQ(3x)x+3x)\\ &=\frac{1}{1-\left(\frac{x^2}{1-3x}+3x\right)}\\ &=\frac{1-3x}{1-6x+8x^2}\\ &=1+3x+10x^2+36x^3+136x^4+\cdots \end{align*}

We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain the wanted sequence numbers $T(n)$ by partial fraction decomposition of the generating series \begin{align*} T(n)&=[x^n]\frac{1-3x}{1-6x+8x^2}\\ &=[x^n]\left(\frac{1}{2(1-4x)}+\frac{1}{2(1-2x)}\right)\\ &=[x^n]\frac{1}{2}\sum_{k\geq 0}4^kx^k+[x^n]\frac{1}{2}\sum_{k\geq 0}2^kx^k\\ &=\frac{1}{2}\left(4^n+2^n\right) \end{align*}

Answer 2

Consider a representation with even number of zeros at step $n-1$. At the next step $n$, you can construct $3$ even number of zeros by following it with $1,2,3$. Similarly if you have a representation with odd number of zeros, you have to follow it with $0$ to keep it still even $0$s.

So at $i$th step let $n_{odd,i}$ be the number of odds and $n_{even,i}$ be the number of even. We have that \begin{equation} n_{even,i+1}=3n_{even,i}+n_{odd,i},~n_{odd,i+1}=3n_{odd,i}+n_{even,i} \end{equation} These are your recurrence relations. The starting point is $n_{even,1}=3$, $n_{odd,1}=1$.

You can verify by induction that $n_{even,i}=2^{i-1}(1+2^i)$ is the general formula.

Answer 3

Here is a different approach:

Let $0$ have weight $x$, and let $1$,$2$, $3$ have weight $1$ each. The weight of a word over $\{0,1,2,3\}$ is the product of the weights of its letters. The total weight of all one-letter words is then $x+1+1+1=3+x$, and the total weight of all $n$-letter words is $(3+x)^n$. It follows that the total weight of all $n$-letter words with an even number of ixes is given by $$f_n(x):={1\over2}\bigl((3+x)^n+(3-x)^n\bigr)\ .$$ Putting $x=1$ here gives each occurring letter the weight $1$, hence counts all words with weight $1$. It follows that $$T(n)=f_n(1)={1\over2}(4^n+2^n)\ .$$

Answer 4

Its:

$3^n$ ...... no occurence of 0

$+3^{n-2}(\binom{n-1}1)$ ...... occurence of two consecutive 0's

$+3^{n-2}(\binom{n-1}2)$ ...... occurence of two separated 0's

$+3^{n-4}(\binom{n-3}1+\binom{n-3}2\binom{3}1+\binom{n-3}3\binom{3}2+\binom{n-3}4\binom33) $ ..... occurence of 4 gathered or separated 0's

$+...$

$+3^{n-2k}(\binom{n-2k+1}1+\binom{n-2k+1}2\binom{2k-1}1+\binom{n-2k+1}3\binom{2k-1}2+\binom{n-2k+1}4\binom{2k-1}3 ....) $

$+...+1$ where all sequence is filled by 0's

---

for n=1:20;
h=0;for k=n:-2:1
a=3^k;v=1;s=0;
while (v<=n-k+1)&(v<=k)
s=s+nchoosek(n-k+1,v)*nchoosek(k-1,v-1);v=v+1;
end
h=a*s+h;
end
fprintf('%d ',h+mod(n+1,2));
end

• Writing this piece of code through matlab gives following results:

3 10 36 136 528 2080 8256 32896 131328 524800 2098176 8390656 33558528 134225920 536887296

which matches OEIS A007582