Consideremos una secuencia cuaternaria de n dígitos. Quiero contar cuántas secuencias de este tipo tienen TANTO el mismo número de 0s como de 1s y el mismo número de 2s como de 3s (por ejemplo, si n=6, una de estas secuencias es 001123). Gracias de antemano.
Respuestas
¿Demasiados anuncios?
Claramente $n$ es par; digamos $n=2m$ . Hay $\binom{2m}m$ formas de elegir $m$ posiciones para el $0$ y $2$ 's. Si hay $k$ $0$ 's, hay $\binom{m}k$ maneras de elegir qué $k$ de esos $m$ los puestos son para $0$ 's; el otro $m-k$ las posiciones contarán, por supuesto, con $2$ 's. También debe haber $k$ $1$ 's, y hay $\binom{m}k$ maneras de colocarlos entre los $m$ posiciones reservadas para $1$ y $3$ 's. Así, el número deseado es
$$\binom{2m}m\sum_{k=0}^m\binom{m}k^2=\binom{2m}m\sum_{k=0}^m\binom{m}k\binom{m}{m-k}=\binom{2m}m^2$$
por La identidad de Vandermonde .
El resultado también puede derivarse de la siguiente manera. Como antes, hay $\binom{2m}m$ formas de elegir el $m$ plazas que serán ocupadas por $0$ y $2$ '; llame a este conjunto de posiciones $A$ . También hay $\binom{2m}m$ formas de elegir el $m$ puestos que serán ocupados por $0$ y $3$ '; llame a este conjunto de posiciones $B$ . Entonces los conjuntos $A\cap B$ , $[2m]\setminus(A\cup B)$ , $A\setminus B$ y $B\setminus A$ contienen las posiciones de los $0$ 's, $1$ 's, $2$ 's, y $3$ respectivamente. (Aquí $[2m]=\{1,\ldots,2m\}$ .) No es difícil comprobar que
$$|A\cap B|=|[2m]\setminus(A\cup B)|$$
y
$$|A\setminus B|=|B\setminus A|$$
para todos los conjuntos $A,B\subseteq[2m]$ tal que $|A|=|B|=m$ y que toda cadena legal puede formarse de esta manera.
CodeJoust
Puntos
2867
N no puede ser impar.
Divida los n espacios en la mitad y llénelos con 0s y 2s. Naturalmente, la otra mitad se llenará con el mismo número de 1s y 3s según su condición.
Para ello, primero debe asignar un número de 0 a (n/2) para el número de 0s. Esto decide el número de 2s (y naturalmente, 1s y 3s) en su secuencia.
Ahora, para un número determinado de 0s (digamos m), hay secuencias C(m,n).C(m,n-m).C(n/2 - m,n-2m). Esto es n!/m!m![(n/2)-m]![(n/2)-m]! .
Así, el número total de secuencias para un "n" dado es la suma desde m=0 hasta m=(n/2) de la función anterior.
