Número de elementos de a $3n$ binario de tuplas, donde las ordenadas agregar a a $2n$.

Question

Tengo el siguiente problema.

Tome $\Omega_n=\{(a_1, a_2 , \cdots , a_{3n})| a_i= 0\rm{\,or}\, 1\}$. Definir $A_n=\{\omega \in \Omega_n|\exists k, \sum _{i=1}^{3k} a_i = 2k\}$ y $S_m=\{(a_1, a_2 , \cdots , a_{3m}) \in A_m|\inf \{ k,| \sum _{i=1}^{3k} a_i = 2k\}=m\}$ estamos interesados en encontrar $|S_m|$ la cardinalidad de a $S_m$

Existe una sencilla fórmula recursiva$S_n={3n \choose 2n}-\left (S_1 {3(n-1) \choose 2(n-1)}+S_2{3(n-2) \choose 2(n-2)}+ \cdots S_{n-1} {3\cdot(1) \choose 2\cdot(1)} \right )= {3n\choose 2n}-\left (\sum _{i=1}^{n-1}S_i {3(n-i)\choose 2(n-i)} \right )$ I no estaba seguro de cómo calcular que lo que he usado OEIS para ver si tiene alguna buena fórmula. Después de encontrar a mano los primeros valores de $3,6,21,90,429$ me sugirió la fórmula $\frac{2}{3n-1}{3n\choose 2n}$. Me las arreglé para demostrarlo por inducción.

Yo estaría interesado en un poco de combinatoria prueba de que, un bijection sería muy apreciada.

Answer 1

Código cabezas como 1 y colas como 0, y el problema se puede formular de la siguiente manera: Lanza una moneda hasta que haya exactamente dos veces la cantidad de cabezas de las colas, y luego se detiene. El valor de $|S_n|$ es el número de secuencias de tiradas de la moneda que tienen longitud exactamente $3n$.

Para esta versión reformulada, hice la misma pregunta que el OP hace un par de años en este sitio, en virtud de la "Combinatoria prueba de $\binom{3n}{n} \frac{2}{3n-1}$ como la respuesta a un tira la moneda problema." Me tomó un par de semanas antes de encontrar una respuesta a mi propia pregunta, así que yo no llamaría a esto un fácil combinatoria prueba. (De hecho, yo generalizada mi argumento, de refundición en términos de contar ciertas entramado de caminos, y obtuvo el argumento publicado en la Revista Electrónica de la Combinatoria como "la Enumeración de Entramado de Caminos de Tocar o Cruzar la Diagonal en un Número Determinado de Celosía Puntos.")

---

De todos modos, voy a reproducir el original de mi combinatoria argumento aquí. Se utiliza el equivalente a $|S_n| = \frac{3}{3n-1} \binom{3n-1}{n}$ como fórmula para ser probado. También se utiliza el siguiente resultado (véase, por ejemplo, en el artículo 7.5 de Hormigón Matemáticas):

Raney el Lema: Vamos a $a_1, ... a_m$ ser una secuencia de números enteros tales que a $\sum a_i = 1$. No hay un único índice $j$ de manera tal que las sumas parciales de la secuencia de $a_j, a_{j+1}, ... a_{j+m-1}$ cíclica (índices) son positivos.

En la prueba.

Introducción.

Considere la posibilidad de que las secuencias con $2n$ apariciones de $-1$ (es decir, $2n$ cabezas) y $n$ apariciones de $+2$ (es decir, $n$ colas). Queremos mostrar que el número de estas secuencias con todas las sumas parciales distinto de cero es $\binom{3n-1}{n} \frac{3}{3n-1}$. La suma completa y vacío de la suma son claramente $0$, por lo que "suma parcial" excluye a los dos casos. Las secuencias queremos contar pueden ser divididos en tres grupos: (1) todas las sumas parciales positivos, (2) todas las sumas parciales negativos, (3) algunos sumas parciales positivos y algunos negativos.

Grupo 1: El número de estas secuencias con todas las sumas parciales positivo es $\binom{3n-1}{n} \frac{1}{3n-1}$.

Esta es la parte que se utiliza Raney del lexema. Si todas las sumas parciales son positivos, el último elemento de la secuencia deben ser $-1$. Por lo tanto queremos contar el número de secuencias con $2n-1$ apariciones de $-1$ $n$ apariciones de $+2$ que añadir a $+1$ y tiene todas las sumas parciales positivos. Ignorando las sumas parciales de restricción, hay $\binom{3n-1}{n}$ dichas secuencias. Si dividimos estos $\binom{3n-1}{n}$ secuencias en clases de equivalencia basadas en cambios cíclicos, Raney del lema dice exactamente una secuencia en cada clase de equivalencia tiene todas las sumas parciales positivos. Porque hay $3n-1$ elementos de cada secuencia hay $3n-1$ de las secuencias con el mismo conjunto de cambios cíclicos, y por tanto, hay $3n-1$ secuencias en cada clase de equivalencia. Por tanto, el número de secuencias en el Grupo 1 es $\binom{3n-1}{n} \frac{1}{3n-1}$.

Grupo 2: El número de estas secuencias con todas las sumas parciales negativos también es $\binom{3n-1}{n} \frac{1}{3n-1}$.

Para ver esto, basta con invertir las secuencias de contado en la Parte 1.

Grupo 3: El número de estas secuencias con algunos positivos sumas parciales y algunos negativos sumas parciales es, sin embargo, de nuevo, $\binom{3n-1}{n} \frac{1}{3n-1}$.

Este es un poco más complicado. En primer lugar, porque de la $-1$'s, no es posible cambiar de positivo de las sumas parciales negativas de las sumas parciales. Por lo tanto, cualquier secuencia de contado aquí debe tener exactamente un interruptor: a partir del negativo de sumas parciales positivo de las sumas parciales. El interruptor debe ocurrir en algún punto donde la suma parcial es $-1$ y el elemento siguiente es $+2$. Así tenemos algunos secuencia $(a_1, \ldots, a_m, +2, a_{m+2}, \ldots, a_n)$ cuando las cantidades $a_1, a_1 + a_2, \ldots, a_1 + \cdots + a_m$ son todos negativos. Considerar la secuencia de $(+2, a_m, \ldots, a_2, a_1, a_{m+2}, \ldots, a_n)$. Desde $+2 + a_m + \cdots + a_1 = 1$, e $a_k + a_{k-1} + \cdots + a_1 < 0$ para todos los $k$, $1 \leq k \leq m$, debe ser el caso de que $+2 + a_m + \cdots + a_{k+1} > 1$ para todos los $k$, $1 \leq k \leq m-1$. Así que la secuencia $(+2, a_m, \ldots, a_2, a_1, a_{m+2}, \ldots, a_n)$ está en el Grupo 1. Para ver que esta asignación es un bijection, tenga en cuenta que cualquier secuencia en el Grupo 1 debe comenzar con $+2$ y tienen un primer tiempo en el que un parcial de la suma es igual a $+1$. Por lo tanto esta transformación es reversible.

Resumiendo.

Poner los Grupos 1, 2, y 3 juntos, vemos que el número total de secuencias queremos contar es $\binom{3n-1}{n} \frac{3}{3n-1}$.