En los últimos pregunta "¿Cuál es la probabilidad de que una secuencia de tiradas de la moneda nunca tiene el doble de cabezas de las colas?" Sostengo en mi respuesta que el número de maneras en $S(n)$ para obtener el doble número de cabezas de las colas por primera vez en $3n$ coin flips es $\binom{3n}{n} \frac{2}{3n-1}$. El argumento funciona mostrando que $S(n)$ satisface la recurrencia y, a continuación, utilizando un binomio de convolución de identidad para demostrar que $\binom{3n}{n} \frac{2}{3n-1}$ satisface la recurrencia así.
Sin embargo, a mí me parece que debería ser un agradable, directa combinatoria prueba de que $S(n) = \binom{3n}{n} \frac{2}{3n-1}$. Después de todo, hay $\binom{3n}{n}$ secuencias de $3n$ moneda gira en la que $n$ son las colas, y el número de aquellos para los que vemos el doble número de cabezas de las colas para la primera vez es sólo $\frac{2}{3n-1}$ de eso. He estado pensando sobre este tema en los últimos días, pero han sido incapaces de encontrar una combinatoria explicación de la fracción $\frac{2}{3n-1}$.
Así que mi pregunta es...
Alguien puede proporcionar una combinatoria prueba de que $S(n) = \binom{3n}{n} \frac{2}{3n-1}$?
Y, más en general, si $S(n,r)$ es el número de maneras de obtener la $r$ veces el número de cabezas de las colas, a continuación, mi argumento en la respuesta se mencionó anteriormente muestra que $S(n,r) = \binom{(r+1)n}{n} \frac{r}{(r+1)n-1}$. Sería bueno si las pruebas son generalizables a la $S(n,r)$ de los casos.
Un pensamiento es que podría ser posible la adaptación de una de las combinatorias de las pruebas de que la $n$th catalán número $C_n$ $\binom{2n}{n} \frac{1}{n+1}$ . De hecho, en la $r=1$ caso la pregunta es equivalente a encontrar el número de Dyck rutas de $(0,0)$ $(n,n)$que no toque la diagonal $y=x$, excepto en$(0,0)$$(n,n)$. Esto es conocido por ser $2C_{n-1} = \binom{2n-2}{n-1} \frac{1}{n} = \binom{2n}{n}\frac{1}{2n-1} = S(n,2).$
De hecho, ese último párrafo me pregunto si podría haber algún generalización de los números de catalán en esta dirección. O tal vez la formulación alternativa $S(n,r) = \binom{(r+1)n-2}{n-1} \frac{r+1}{n}$ admite una combinatoria prueba más fácilmente.
Añadido
: creo que Qiaochu de Yuanes, el argumento de más abajo acerca del uso de Raney del lema está en el camino correcto, pero no acaba de llegar a la expresión que estoy buscando. Raney del lexema es acerca de una secuencia en la que todas las sumas parciales son positivos. Sin embargo, en la obtención de $r$ veces el número de cabezas de las colas por primera vez las sumas parciales ($+r$ para cada cola y $-1$ por cada cabeza) no todos tenemos que ser positivos o todos negativos. Por ejemplo, usted podría tener una secuencia como HHHT, con total $+1$, y, a continuación, si el siguiente flip es una cola que habría HHHTT, con total $-1$, y aún no hemos llegado exactamente dos veces la cantidad de cabezas de las colas.
Sospecho que el Raney del lema argumento puede ser adaptado, pero no creo que tenga una respuesta a la pregunta todavía. ¿Alguien a ver cómo lo hacen?
Añadido 2
: he encontrado una completa combinatoria argumento. Véase mi respuesta a continuación.
