Secuencias binarias de longitud 2n

Question

Había publicado un problema de probabilidad de la urna que no tenían una buena motivación. Me gustaría tratar de explicar la motivación aquí, y reintroducir el problema.

Consideremos secuencias binarias de longitud $2n$ . Digamos que ponemos un marcador en dicha secuencia en cuanto vemos un total de $n$ 0 o $n$ 1's, leyendo de izquierda a derecha. Por ejemplo, si $n=4$ entonces la secuencia 00101011 recibiría un marcador así: 001010|11. Ahora escribe los bits a la derecha del marcador. En el caso de nuestro ejemplo, sería 11. Haga esto para cada secuencia binaria de longitud $2n$ . Observamos que hemos escrito $2n\binom{2n}{n}$ bits, mitad 0 y mitad 1. Es posible demostrar esta observación utilizando identidades de coeficientes binomiales, pero me pregunto si existe una prueba biyectiva sencilla.

El problema de la urna anterior era una formulación probabilística equivalente del caso $n=5$ .

Answer 1

Dada la simetría entre 0 y 1 después del final de la primera "serie" de n dígitos iguales, no importa si contamos ceros o unos después de una "serie" de n ceros. Es decir, si sólo contamos ceros después de n ceros y unos después de n unos, deberíamos obtener $n\binom{2n}{n}$ . Este recuento es el número total de dígitos sobrantes (sobre n) en todos los patrones de bits de longitud 2n, y éstos se dividen equitativamente entre ceros y unos, denotados por $S=\sum_{k=0}^{n}k\binom{2n}{n+k}$ esta media cuenta.

Tenemos $\binom{2n}{n+k}(n+k) = \binom{2n}{n+k-1}(n-k+1)$ -- ambos son el número de particiones de 2n elementos en conjuntos de tamaño n+k-1, n-k y 1. Por lo tanto $$S+\sum_{k=0}^{n} n\binom{2n}{n+k} = \sum_{k=0}^{n} \binom{2n}{n+k}(n+k) = \sum_{k-1=-1}^{n-1} \binom{2n}{n+(k-1)}(n-(k-1)) =$$ $$= \sum_{k-1=-1}^{n} \binom{2n}{n+(k-1)}(n-(k-1)) = \binom{2n}{n-1}(n+1) + \sum_{k=0}^{n} n\binom{2n}{n+k} - S$$ y tenemos $2S=(n+1)\binom{2n}{n-1} = n\binom{2n}{n}$ según sea necesario.

Se trata esencialmente de contar todos los ceros en los patrones que tienen un exceso de ceros con peso -1 y todos los unos en los patrones que tienen al menos tantos unos como ceros con peso +1, y observar que obtenemos $n\binom{2n}{n}$ por conteo rectilíneo (sólo los patrones n+n no se aniquilan por pares con su secuencia complementaria) por un lado y $2S$ por otro lado (podemos emparejar un patrón de bits con un dígito mayoritario seleccionado con un patrón con un dígito minoritario seleccionado y contar cada dígito mayoritario sobrante dos veces al hacerlo).

Answer 2

Para ver que debe obtener la mitad de 0s y la mitad de 1s: voltee todos los bits de una cadena que termine en k 1s y obtenga una cadena que termine en k 0s. Por ejemplo, 001010|11 se empareja con 110101|00.

No estoy seguro de cómo demostrar bijetivamente que hay $n {2n \choose n}$ de cada uno.

Answer 3

Digamos que consideramos el conjunto de cadenas en las que vemos $n$ ceros primero (por simetría, debería ser la mitad del número total). Fije el número de 1s también encontrado para ser $k$ . entonces el número total restante de bits es $n-k$ por lo que podemos ver todas las cadenas posibles en n-k bits, cada una de las cuales es de longitud $n-k$ .

Pero hay $\binom{n+k-1}{k}$ formas de colocar el $k$ para dar prefijos distintos, por lo que la suma deseada parece ser (sustituyendo $k$ por $n-i$ ) $$ \sum_{i=0}^n i 2^i \binom{2n-i-1}{n-i}$$

No soy lo suficientemente experto en la manipulación de identidades binomiales para averiguar lo que esto debería ser.