Número de secuencias equilibradas

Question

Una secuencia de longitud $2n$ que contiene sólo $1, -1$ (cada vez que digo "secuencia", quiero decir que estas propiedades se mantienen) se dice que es equilibrado si todos los $2n$ las sumas parciales son no negativas.

Me piden que calcule el número de secuencias equilibradas (dado $n$ ).

Ya sé la respuesta, utilizando otro resultado que he demostrado en el pasado: el número de secuencias equilibradas con suma $2m$ para $0\leq m\leq n$ es $\binom{2n}{n+m}-\binom{2n}{n+m+1}$ . Así que cuando sumamos esta expresión sobre todos los valores posibles para $m$ obtenemos la respuesta correcta a mi primera pregunta: $\binom{2n}{n}$ . (Nótese que la suma tiene que ser par).

Ahora, este es exactamente el número de secuencias con suma $0$ Por lo tanto, mi pregunta es si hay una mejor manera de verlo, es decir

¿Existe una biyección natural desde el conjunto de secuencias equilibradas al conjunto de secuencias con suma $0$ ?

Mi intento: Dejemos que $\left\{a_i \right \}_{i=1}^{2n}$ una secuencia equilibrada, y que $2m$ sea su suma. Sea $k_0\geq 1$ sea el primer índice que satisfaga $\sum_{i=1}^{k_0}a_i=m$ (¡existe!) y definir una nueva secuencia: $\bar{a}_i=\left\{\begin{matrix} a_i & 1\leq i \leq k_0 \\ -a_i & i>k_0 \end{matrix}\right.$ La nueva secuencia tiene una suma $0$ ¿pero es una biyección?

Me gustaría escuchar sus sugerencias. Gracias.

Answer 1

La prueba de la siguiente proposición nos da la biyección deseada:

Propuesta. Para $\ell\in\Bbb Z^+$ el número de secuencias de suma cero de longitud $2n$ cuya suma parcial mínima es $-\ell$ es igual al número de secuencias equilibradas de longitud $2n$ cuya suma es $2\ell$ .

Prueba. Dejemos que $\alpha=\langle a_1,\ldots,a_{2n}\rangle$ sea una secuencia de suma cero, y para $k=1,\ldots,2n$ dejar $s_k$ sea la suma parcial $s_k=\sum_{i=1}^ka_i$ . Supongamos que $\min\{s_k:k=1,\ldots,2n\}=-\ell$ para algunos $\ell\in\Bbb Z^+$ . Para $i=1,\ldots,\ell$ dejar $k_i$ sea mínima, tal que $s_{k_i}=-i$ claramente $1\le s_1<\ldots<s_\ell<2n-\ell$ y $a_{k_i}=-1$ para $i=1,\ldots,\ell$ .

Dejemos que $\hat\alpha=\langle\hat a_1,\ldots,\hat a_{2n}\rangle$ sea la secuencia obtenida de $\alpha$ sustituyendo cada $a_{k_i}$ para $i=1,\ldots,\ell$ con $1$ y que $\hat s_k=\sum_{i=1}^k\hat a_i$ para $k=1,\ldots,2n$ . Claramente $\hat s_{2n}=s_{2n}+2\ell=2\ell$ . Además, no es difícil comprobar que $\hat s_k\ge 0$ para $k=1,\ldots,2n$ . De hecho, $\hat s_k\ge 0$ para $1\le k<k_1$ , $\hat s_k\ge 1$ para $k_1\le k<k_2$ , $\hat s_k\ge 2$ para $k_2\le k<k_3$ y así sucesivamente.

Ahora dejemos que $\alpha=\langle a_1,\ldots,a_{2n}\rangle$ sea una secuencia equilibrada, defina las sumas parciales $s_k$ como antes, y supongamos que $s_{2n}=2\ell$ . Para $i=1,\ldots,\ell$ dejar $k_i$ sea mínima, tal que $s_{k_i}=i$ claramente $1\le s_1<\ldots<s_\ell<2n-\ell$ y $a_{k_i}=1$ para $i=1,\ldots,\ell$ .

Dejemos que $\bar\alpha=\langle\bar a_1,\ldots,\bar a_{2n}\rangle$ sea la secuencia obtenida de $\alpha$ reemplazar cada $a_{k_i}$ para $i=1,\ldots,\ell$ con $-1$ y que $\bar s_k=\sum_{i=1}^k\bar a_i$ . Claramente $\bar s_{2n}=s_{2n}-2\ell=0$ y no es difícil comprobarlo para $i=1,\ldots,\ell$ , $k_i$ es mínima, tal que $\bar s_{k_i}=-i$ . Así, $\hat{\bar\alpha}=\alpha$ y los mapas $\alpha\mapsto\hat\alpha$ y $\alpha\mapsto\bar\alpha$ son inversas entre sí y biyecciones entre el conjunto de secuencias de suma cero con suma parcial mínima $-\ell$ y el conjunto de secuencias equilibradas con suma $2\ell$ . $\dashv$