Contar palabras con restricciones de paridad en las letras

Question

Que $a_n$ es el número de palabras de longitud $n$ del alfabeto ${A,B,C,D,E,F}$ en que $A$ aparece un número par de veces y $B$ aparece un número impar de veces. Usando funciones generación era capaz de demostrar que %#% $ #%

¿Me preguntaba si la respuesta anterior es correcta y en ese caso lo que podría ser una prueba combinatoria de esa fórmula?

Answer 1

Llame a $s_n$ el número de palabras con números de a y B de la misma paridad, y $d_n$ el número de palabras con números de a o B de diferentes partidos. Ya que hay tantas palabras con un número impar de Una y de un número par de B que las palabras con un número par de a y un número impar de B, es después de $a_n=\frac12d_n$.

Obviamente, $s_n+d_n$ es el número total de palabras de longitud $n$, $s_n+d_n=6^n$.

Por otro lado, la adición de Una o B para una palabra de longitud $n$ produce una palabra de otro tipo, y la adición de C, D, E o F produce una palabra del mismo tipo, por lo tanto $s_{n+1}=4s_n+2d_n$$d_{n+1}=4d_n+2s_n$.

Este rendimientos $s_{n+1}-d_{n+1}=2(s_n-d_n)$. Desde $s_1=4$ y $d_1=2$, $s_n-d_n=2^{n}$.

Finalmente, $a_n=\frac12d_n=\frac14(s_n+d_n)-\frac14(s_n-d_n)=\frac14(6^n-2^n)$.

---

Editar Aquí es una alternativa a la prueba de la relación $s_n-d_n=2^{n}$, basado en el método de probabilidades.

Dibujar uniformemente al azar una palabra de la $6^n$ palabras de longitud $n$ y deje $X_k=-1$ si $k$th carta es a o B y $X_k=+1$ lo contrario. Las variables aleatorias $(X_k)_{1\leqslant k\leqslant n}$ son independientes, $X_k=-1$ con una probabilidad de $\frac13$, $X_k=+1$ con una probabilidad de $\frac23$, por lo tanto $\mathrm E(X_k)=1-2\frac13=\frac13=x$.

Deje $Y_n=X_1X_2\cdots X_n$. A continuación, $Y_n=+1$ si la palabra contiene los números de a y B de la misma paridad y $Y_n=-1$ lo contrario, lo $6^n\mathrm P(Y_n=+1)=s_n$$6^n\mathrm P(Y_n=-1)=d_n$. La independencia de las variables aleatorias $(X_k)_{1\leqslant k\leqslant n}$ implica que el $\mathrm E(Y_n)=\mathrm E(X_1)\mathrm E(X_2)\cdots \mathrm E(X_n)=x^n$, por lo tanto $$ s_n-d_n=6^n\mathrm E(Y_n)=6^nx^n=2^n. $$ Esto también demuestra que, para el mismo problema utilizando un alfabeto de $\color{red}{N\geqslant4}$ letras, $x=1-\frac4N$ por lo tanto $$ \color{red}{a_n=\frac{N^n-(N-4)^n}4}. $$ Esta fórmula sugiere que una prueba por medio de la inclusión-exclusión que esté disponible, lo que permitirá obtener las sucesivas potencias de $4$ en el binomio de expansión de $(N-4)^n$.

Answer 2

1. Primero respecto de las palabras que contienen al menos un $A$ o $C$ y al menos un $B$ o $D$.

   Ahora utilizar las funciones de "convertir la primera letra que es $A$ o $C$ en el otro uno de los dos" y "convertir la primera letra que es $B$ o $D$ en el otro uno de los dos".

   Estas dos funciones están claramente bijections y viajar, así que por estas palabras exactamente una cuarta tiene la propiedad deseada.

2. En segundo lugar, respecto de las palabras que no contienen $A$ o $C$ o no contener $B$ o $D$, pero no ambas propiedades son verdaderas.

   Palabras que no contienen un $B$ o $D$ no contienen un número impar de $B$s.

   Palabras que no contienen una $A$ o $C$ automáticamente contienen un número par de $A$s y la segunda de la función de arriba muestra bijectively que la mitad de las palabras trabajo.

   Juntos, de nuevo un cuarto de todas las palabras que tiene la propiedad deseada.

3. Finalmente, respecto de las palabras que no contienen $A$,$B$,$C$,$D$. Hay $2^n$ de ellos.

   Ellos no tienen un número impar de $B$s.

Así que, en resumen, todas las palabras $6^n$, dividir por cuatro, pero tenemos que restar la contribución $2^n/4$ de el último caso, que da la fórmula $$(6^n-2^n)/4.$$

Answer 3

No sé si a usted le llaman ellos combinatoria, pero aquí hay dos completamente primaria argumentos de un tipo que he presentado en un segundo nivel de la matemática discreta curso. Añadido: Ni, por supuesto, es tan bueno como el de Didier, que no me había visto cuando he publicado esto.

Deje $b_n$ el número de palabras de longitud $n$ con un número impar de $A$'s y un número impar de $B$s, $c_n$ el número de palabras de longitud $n$ con un número de $A$'s y un número de $B$'s, y $d_n$ el número de palabras de longitud $n$ con un número impar de $A$'s y un número de $B$'s. Entonces

$$a_{n+1}=4a_n+b_n+c_n\;.\tag{1}$$

Claramente $a_n=d_n$: intercambio $A$'s y $B$'s da un bijection entre los dos tipos de palabra. $(1)$ por lo tanto se reduce a

$$a_{n+1}=4a_n+b_n+c_n\;.\tag{2}$$

Pero $6^n=a_n+b_n+c_n+d_n=b_n+c_n+2a_n$, lo $b_n+c_n=6^n-2a_n$, e $(2)$ se convierte en $$a_{n+1}=2a_n+6^n,a_0=0\;.\tag{3}$$ $(3)$ se puede resolver por la fuerza bruta:

$$\begin{align*} a_n&=2a_{n-1}+6^{n-1}\\ &=2(2a_{n-2}+6^{n-2})+6^{n-1}\\ &=2^2a_{n-2}+2\cdot 6^{n-2}+6^{n-1}\\ &=2^2(2a_{n-3}+6^{n-3})+2\cdot 6^{n-2}+6^{n-1}\\ &=2^3a_{n-3}+2^2\cdot 6^{n-3}+2\cdot 6^{n-2}+6^{n-1}\\ &\;\vdots\\ &=2^na_0+\sum_{k=0}^{n-1}2^k6^{n-1-k}\\ &=6^{n-1}\sum_{k=0}^{n-1}\left(\frac13\right)^k\\ &=6^{n-1}\frac{1-(1/3)^n}{2/3}\\ &=\frac{2^{n-1}3^n-2^{n-1}}{2}\\ &=\frac{6^n-2^n}4\;. \end{align*}$$

Alternativamente, tal vez con un poco más de astucia $(1)$ puede ser ampliado a

$$\begin{align*} a_{n+1}&=4a_n+b_n+c_n\\ b_{n+1}&=4b_n+2a_n\\ c_{n+1}&=4c_n+2a_n\;, \end{align*}\etiqueta{4}$$

de dónde

$$\begin{align*}a_{n+1}&=4a_n+4b_{n-1}+2a_{n-1}+4c_{n-1}+2a_{n-1}\\ &=4a_n+4a_{n-1}+4(b_{n-1}+c_{n-1})\\ &=4a_n+4a_{n-1}+4(a_n-4a_{n-1})\\ &=8a_n-12a_{n-2}\;. \end{align*}$$

Este sencillo recurrencia lineal homogénea (con condiciones iniciales $a_0=0,a_1=1$) de inmediato se obtiene el resultado deseado.

Answer 4

Hay un método combinatorio (por cierto, considero que generar funciones es un método combinatorio, pero no importa) usando inclusión-exclusión. Cuente el número total de$n$ - palabras de letras, reste las que tengan un número impar de$A$, reste las que tengan un número par de$B$, luego agregue nuevamente las que contengan con un número impar de$A$ y un número par de$B$. Por supuesto, debes resolver los detalles ...