$n$ -palabras del alfabeto $A=\{0, 1, 2, 3\}$ . ¿Cuántos de ellos tienen un número par de ceros y unos?

Question

Considere todos $n$ -palabras del alfabeto $A=\{0, 1, 2, 3\}$ . ¿Cuántos de ellos tienen un número par de ceros y unos? Demostré que el número de $n$ -palabras de $\{0, 1, 2, 3\}$ con un número par de ceros es $\displaystyle X_n=\frac{4^n+2^n}{2}$ y con un número impar de ceros es $\displaystyle Y_n=\frac{4^n-2^n}{2}$ . Pero no me han demostrado el número $T_n$ de $n$ -Las palabras tienen un número par de ceros y unos. Gracias por su ayuda

Answer 1

Por una palabra $w$ , dejemos que $w(k)$ sea el número de veces que $k$ aparece en $w$ y $l(w)$ la longitud de $w$ .

Dejemos que $A_n=\{w:l(w)=n,w(0)\text{ even and }w(1)\text{ even}\}$ .

Dejemos que $B_n=\{w:l(w)=n,w(0)\text{ odd and }w(1)\text{ even}\}$ .

Dejemos que $C_n=\{w:l(w)=n,w(0)\text{ even and }w(1)\text{ odd}\}$ .

Dejemos que $D_n=\{w:l(w)=n,w(0)\text{ odd and }w(1)\text{ odd}\}$ .

Toma la palabra $w$ de longitud $n$ y tratemos de generar una palabra de longitud $n+1$ añadiendo un dígito al final.

Si $w\in A_n$ entonces el nuevo dígito puede ser $2$ o $3$ .

Si $w\in B_n$ el nuevo dígito debe ser $0$ .

Si $w\in C_n$ el nuevo dígito debe ser $1$ .

Si $w\in D_n$ ninguna palabra válida puede ser generada de esta manera.

Entonces:

$$|A_{n+1}|=2|A_n|+|B_n|+|C_n|$$

Del mismo modo, obtenemos:

$$|B_{n+1}|=|A_n|+2|B_n|+|D_n|$$

$$|C_{n+1}|=|A_n|+2|C_n|+|D_n|$$

$$|D_{n+1}|=|B_n|+|C_n|+2|D_n|$$

Para la palabra de longitud $1$ tenemos: $|A_1|=2$ , $|B_1|=1$ , $|C_1|=1$ , $|D_1|=0$ .

Este conjunto de ecuaciones permite encontrar recursivamente cualquier $|A_n|$ .

De hecho, dada la matriz $$M=\left(\begin{matrix}2&1&1&0\\1&2&0&1\\1&0&2&1\\0&1&1&2\end{matrix}\right)$$ the values for $|A_n|$, etc. are given by $$M^n\left(\begin{matrix} 2\\ 1\\ 1\\ 0\end{matrix}\right)$$