¿Cuántos $n$ -secuencias de $0,1 \ \text{or} \ 2$ s contienen un número impar de $0$ s?

Question

Problema : Hay $3^n$ secuencias de n dígitos en las que cada dígito es $0$ , $1$ o $2$ . ¿Cuántas de estas secuencias tienen un número impar de $0$ 's ?

Sea $o(n)$ = el número de secuencias de n dígitos que tienen un número impar de $0$ y $e(n)$ = el número de secuencias de n dígitos que tienen un número par de $0$ 's.

Obviamente $o(n) + e(n) = 3^n$ y por ejemplos puedo ver que $o(n)=e(n)-1$ pero no sé cómo mostrarlo. Además, si tenemos $x$ dígitos para elegir entonces por ejemplos veo que $o(n) = e(n) - {n}^{x-2}$ . Y si consideramos el número de secuencias que tienen un número congruente con $0$ , $1$ respectivamente $2$ (modulo $3$ ) de $0$ s vemos que estos números están en progresión aritmética.

¿Puede alguien demostrarme estas suposiciones o refutarlas si no son correctas?

Answer 1

Una forma de ver $o(n)=e(n)-1$ (que como has señalado es suficiente para terminar): Considere la siguiente operación, que se define en todas las secuencias excepto en la secuencia all $2$ secuencia:

Tome el primer dígito que es $0/1$ y cambiar entre $0$ y $1$ .

Por ejemplo, $2101$ se asigna a $2001$ . Dos cosas que puede comprobar rápidamente sobre este mapa son

• Si aplicas el mapa dos veces, volverás a la secuencia original. Así que el mapa empareja efectivamente el $3^n-1$ secuencias que no son todas $2$ .

• En cada par, una secuencia tiene un número par de ceros, la otra tiene un número impar.

Así que esos $3^n-1$ secuencias se reparten a partes iguales entre par e impar. La única secuencia sobrante no tiene ceros, por lo que es par.

El mismo argumento funciona si tiene $x$ dígitos entre los que elegir, con la única diferencia de que ahora hay $(x-2)^n$ secuencias que no contengan $0$ ni $1$ que no están emparejados.

En combinatoria, este tipo de argumento se denomina involución con inversión de signo.

Answer 2

Dada una cadena de longitud $n$ Si la última cifra es $0$ entonces querrá tener un número par de $0s$ en la primera $n-1$ dígitos, por lo tanto $e(n-1)$ . Si el último dígito es mayor $1$ o $2$ entonces necesitas un número impar de ceros en el primer $n-1$ dígitos, por lo tanto $2o(n-1)$ .

Así que tenemos $o(n)=2o(n-1)+e(n-1)=2o(n-1)+3^{n-1}-o(n-1)=3^{n-1}+o(n-1)$ .

Multiplicando ambos lados por $x^n$ para obtener

$x^no(n)=x^n3^{n-1}+x^no(n-1)$ entonces

$\sum_{n=1}^{\infty}x^no(n)=\sum_{n=1}^{\infty}x^n3^{n-1}+\sum_{n=1}^{\infty}x^no(n-1)$

deje $F(x)=\sum_{n=0}^{\infty}x^no(n)$ entonces

$F(x)-o(0)=x\sum_{n=1}^{\infty}x^{n-1}3^{n-1}+x\sum_{n=1}^{\infty}x^{n-1}o(n-1)$

$F(x)-o(0)=x\sum_{n=1}^{\infty}(3x)^{n-1}+xF(x)$

$F(x)(1-x)=x\sum_{n=1}^{\infty}(3x)^{n-1}$

$F(x)=\frac{x}{1-x}\sum_{n=1}^{\infty}(3x)^{n-1}$

$F(x)=\frac{x}{1-x}\frac{1}{1-3x}$

$F(x)=(\frac{-1}{2}+\frac{3^n}{2})\sum_{n=0}^{\infty}x^n$

así que $o(n)=(\frac{3^n-1}{2})$

Answer 3

Supongamos que $n$ es impar, $n = 2s+1$

Tenga en cuenta que el número de $n$ -secuencias de dígitos con $k$ número de ceros es ${N_k}(n) =$ $n \choose k$$ 2^{n-k}$ .

Así, $$o(n) = \sum_{m=0}^s{N_{2m+1}}(n) = \sum_{m=0}^s{n \choose 2m+1}{2^{n-2m-1}} = \sum_{m=0}^s{n \choose 2m+1}{1^{2m+1} 2^{n-2m-1}} \\ = \frac{(2+1)^n-(2-1)^n}{2} = \frac{3^n-1}{2}$$

Si $n$ es par, que $n = 2t$ . Entonces $o(n) = \sum_{m=0}^{t-1}{n \choose 2m+1}{2^{n-2m-1}} = \frac{3^n-1}{2}$ y ya está.

Además, $$o(n-1) = \frac{3^{n-1}-1}{2} \implies \fbox{$ o(n-1) + 3^{n-1} = o(n) $}$$

Del mismo modo, para $e(n)$ , $$e(n)=\begin{cases}{\sum_{m=0}^s{n \choose 2m}{2^{n-2m}}}&n=2s+1 \\ \sum_{m=0}^t{n \choose 2m}{2^{n-2m}}& n = 2t\end{cases}$$

Así, $$e(n) = \frac{(2+1)^n+(2-1)^n}{2} = \frac{3^n+1}{2}$$

Ahora, haciendo más cálculos, se puede averiguar que $\fbox{$ e(n)-o(n) = 1 $}$ .

Answer 4

También puedes utilizar funciones generadoras exponenciales para resolver este problema.

Sea $f(n)$ sea el número de secuencias ternarias de longitud $n$ con un número impar de ceros y que $F(z)=\sum_{n=0}^\infty f(n)\frac{z^n}{n!}$ sea la función generadora exponencial asociada. Entonces $$ \begin{align*} \left(z+\frac{z^3}{3!}+\frac{z^5}{5!}+\dotsb\right)\left(1+z+\frac{z^2}{2!}+\dotsb\right)^2 &=\sum_{n=0}^\infty\left(\sum_{k_1+k_2+k_3=n\; k_1\, \text{odd}, k_2, k_3\geq 0}\frac{n!}{k_1!k_2! k_3!}\right)\frac{z^n}{n!}\\ &=\sum_{n=0}^\infty f(n)\frac{z^n}{n!} \end{align*} $$ es decir, tenemos que $$ F(z)=e^{2z}\times\frac{e^z-e^{-z}}{2}=\frac{e^{3z}-e^{z}}{2}=\sum_{n=0}^\infty \frac{3^n-1}{2}\frac{z^n}{n!} $$ de donde $$ f(n)=\frac{3^n-1}{2}\quad (n\geq 0). $$