Intenté matar los coeficientes binomiales centrales, pero volvieron.

Question

El triángulo de Pascal contiene números enormes. Intenté "domarlo" (hacer los números más pequeños) "eliminando" los números más grandes, es decir, los coeficientes binomiales centrales: $2,6,20,70,252,924,\dots$.

Es decir, a medida que construí las filas (cada número siendo la suma de los dos números encima de él), cada vez que una fila tenía un número central (excepto el $1$ en la parte superior), hacía que el número central fuera $0$ en lugar de sumar los dos números encima de él.

Entonces en lugar de:

$$ 1\\ 1\quad 1\\ 1\quad \color{red}{2}\quad 1\\ 1\quad 3\quad 3\quad 1\\ 1\quad 4\quad \color{red}{6}\quad 4\quad 1\\ 1\quad 5\quad 10\quad 10\quad 5\quad 1\\ 1\quad 6\quad 15\quad \color{red}{20} \quad 15\quad 6\quad 1\\ 1\quad 7\quad 21\quad 35\quad 35\quad 21\quad 7\quad 1\\ \cdots $$

Obtuve: $$ 1\\ 1\quad 1\\ 1\quad \color{red}{0}\quad 1\\ 1\quad 1\quad 1\quad 1\\ 1\quad 2\quad \color{red}{0}\quad 2\quad 1\\ 1\quad 3\quad 2\quad 2\quad 3\quad 1\\ 1\quad 4\quad 5\quad \color{red}{0} \quad 5\quad 4\quad 1\\ 1\quad 5\quad 9\quad 5\quad 5\quad 9\quad 5\quad 1\\ \cdots $$

Pensé que me había deshecho de esos molestos coeficientes binomiales centrales. Pero luego, curioso sobre las propiedades de mi versión "domada" del triángulo de Pascal, decidí calcular la suma de cada fila, y obtuve:

$$1,2,\color{red}{2},4,\color{red}{6},12,\color{red}{20},40,\color{red}{70},140,\color{red}{252},504,\color{red}{924},\dots$$

¡Esos coeficientes binomiales centrales encontraron la manera de regresar!

¿Hay una explicación para esto?

Contexto: Recientemente he estado interesado en el triángulo de Pascal, haciendo preguntas aquí, aquí y aquí.

Answer 1

Sea $g_n(x)$ la función generadora de la fila $n$ de tu triángulo:

$g_0(x) = 1$, $g_1(x) = 1+x$, $g_2(x) = 1 + x^2$, etc.

Parece [empíricamente: no tengo una prueba] que éstas satisfacen la recurrencia

$$4 x (1+x) n g_n(x) - 4 x n g_{n + 1}(x) - (n+3)(1+x) g_{n+2}(x) + (n + 3) g_{n+3}(x) = 0 $$

La suma de la fila $n$ es entonces $g_n(1)$, que satisface

$$ 8 n g_n(1) - 4 n g_{n+1}(1) - 2 (n+3) g_{n+2}(1) + (n+3) g_{n+3}(1) = 0 $$

y la solución de esto con condiciones iniciales $g_0(1) = 1$, $g_1(1) = 2$, $g_2(1) = 2$ es

$$ g_{2n}(1) = {2n \choose n},\ g_{2n+1}(1) = 2 {2n \choose n} $$

EDIT: OK, aquí está una prueba. Sea $h_k(x)$ sea $g_k(x)$ con los signos de los coeficientes de $x^i$ para $i > k/2$ cambiados. Así $$ \eqalign{h_1(x) &= 1-x \cr h_2(x) &= 1 - x^2\cr h_3(x) &= 1 + x - x^2 - x^3\cr h_4(x) &= 1 + 2 x - 2 x^3 - x^4\cr} $$ El coeficiente de $x^{k}$ en $h_n(x)$ es $-$ el coeficiente de $x^{n-k}$ allí. Entonces se puede ver que los coeficientes de $h_n$ forman las entradas de un "triángulo de Pascal" comenzando con la fila $(1,-1)$; no hay necesidad de anular los coeficientes centrales porque la simetría los hace automáticamente $0$. Así $h_n(x) = (1-x) (1+x)^{n-1}$. Por lo tanto, el coeficiente de $x^k$ en $g_n(x)$ es ${n-1 \choose k} - {n-1 \choose k-1}$ para $k < n/2$ (con ${n-1 \choose -1} = 0$) y ${n-1 \choose k-1} - {n-1 \choose k}$ para $k > n/2$. Sumándolos, aprovechando de la telescopia, tenemos $$ \eqalign{g_{2n}(1) &= 2 \sum_{k=0}^{n-1} \left({2n-1 \choose k} - {2n-1 \choose k-1}\right) = 2{2n-1 \choose n-1} = {2n \choose n}\cr g_{2n+1}(1) &= 2 \sum_{k=0}^{n} \left({2n \choose k} - {2n \choose k-1}\right) = 2{2n \choose n}\cr}$$

Answer 2

Defina $\left[\begin{matrix}n\\r\\\end{matrix}\right]$ como el número en la fila $n$, $r$-ésimo desde la izquierda, en el triángulo de Pascal "domesticado". (La fila superior es la fila $0$; el número más a la izquierda en cada fila es el número $0$-ésimo desde la izquierda.)

Defina la proposición $H_n: \left[\begin{matrix}n\\r\\\end{matrix}\right]=\left(\begin{matrix}n-1\\r\\\end{matrix}\right)-\left(\begin{matrix}n-1\\r-1\\\end{matrix}\right)$ para $1\le r\le \lfloor\frac{n}{2}\rfloor$.

---

Cuando $n=2$, tenemos $\left[\begin{matrix}2\\1\\\end{matrix}\right]=0=\left(\begin{matrix}1\\1\\\end{matrix}\right)-\left(\begin{matrix}1\\0\\\end{matrix}\right)$, entonces $H_2$ es verdadero.

Suponga que $H_k$ es verdadero para algún $k\ge2$.

$\left[\begin{matrix}k\\r\\\end{matrix}\right]=\left(\begin{matrix}k-1\\r\\\end{matrix}\right)-\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)$ para $1\le r\le \lfloor\frac{k}{2}\rfloor\text{ por suposición}$

$\begin{align} \left[\begin{matrix}k+1\\r\\\end{matrix}\right] &=\left[\begin{matrix}k\\r\\\end{matrix}\right]+\left[\begin{matrix}k\\r-1\\\end{matrix}\right>\text{para $1\le r\le \lfloor\frac{k}{2}\rfloor$ por definición del triángulo de Pascal domesticado}\\ &=\left(\color{red}{\left(\begin{matrix}k-1\\r\\\end{matrix}\right)}-\color{red}{\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)}\right) + \left(\color{blue}{\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)}-\color{blue}{\left(\begin{matrix}k-1\\r-2\\\end{matrix}\right)}\right)\text{para $2\le r\le\lfloor\frac{k}{2}\rfloor$, por suposición}\\ &=\left(\color{red}{\left(\begin{matrix}k-1\\r\\\end{matrix}\right)}+\color{blue}{\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)}\right) - \left(\color{red}{\left(\begin{matrix}k-1\\r-1\\\end{matrix}\right)}+\color{blue}{\left(\begin{matrix}k-1\\r-2\\\end{matrix}\right)}\right)\text{reordenando}\\ &=\left(\begin{matrix}k\\r\\\end{matrix}\right)-\left(\begin{matrix}k\\r-1\\\end{matrix}\right)\text{por definición del triángulo de Pascal} \end{align}$

Hemos demostrado que $H_k\implies\left[\begin{matrix}k+1\\r\\\end{matrix}\right]=\left(\begin{matrix}k\\r\\\end{matrix}\right)-\left(\begin{matrix}k\\r-1\\\end{matrix}\right)$ para $\color{orange}{2}\le r\le \color{orange}{\lfloor\frac{k}{2}\rfloor}$.

Estamos tratando de obtener $H_{k+1}:\left[\begin{matrix}k+1\\r\\\end{matrix}\right]=\left(\begin{matrix}k\\r\\\end{matrix}\right)-\left(\begin{matrix}k\\r-1\\\end{matrix}\right)$ para $\color{orange}{1}\le r\le \color{orange}{\lfloor\frac{k+1}{2}\rfloor}$.

$\left[\begin{matrix}k+1\\1\\\end{matrix}\right]=k-1=\left(\begin{matrix}k\\1\\\end{matrix}\right)-\left(\begin{matrix}k\\1-1\\\end{matrix}\right)$ entonces la ecuación es verdadera para $r=1$.

Si $k$ es par entonces $\lfloor\frac{k}{2}\rfloor=\lfloor\frac{k+1}{2}\rfloor$, así que obtenemos $H_{k+1}$.

Si $k$ es impar entonces $\left[\begin{matrix}k+1\\\lfloor\frac{k+1}{2}\rfloor\\\end{matrix}\right]=0=\left(\begin{matrix}k\\\lfloor\frac{k+1}{2}\rfloor\\\end{matrix}\right)-\left(\begin{matrix}k\\\lfloor\frac{k+1}{2}\rfloor-1\\\end{matrix}\right)$ entonces aún obtenemos $H_{k+1}$.

$\therefore$ Por el principio de inducción matemática, $H_n$ es verdadero para todos los enteros $n\ge2$.

---

Usando este resultado, tenemos:

$\begin{align} \sum\limits_{r=0}^n\left[\begin{matrix}n\\r\\\end{matrix}\right] &=2\times\sum\limits_{r=0}^{\lfloor n/2\rfloor}\left[\begin{matrix}n\\r\\\end{matrix}\right]\text{por simetría}\\ &=2\times\left(\left[\begin{matrix}n\\0\\\end{matrix}\right]+\sum\limits_{r=1}^{\lfloor n/2\rfloor}\left[\begin{matrix}n\\r\\\end{matrix}\right]\right)\text{extrayendo $r=0$}\\ &=2\times\left(\left[\begin{matrix}n\\0\\\end{matrix}\right]+\sum\limits_{r=1}^{\lfloor n/2\rfloor}\left(\left(\begin{matrix}n-1\\r\\\end{matrix}\right)-\left(\begin{matrix}n-1\\r-1\\\end{matrix}\right)\right)\right)\text{usando el resultado anterior}\\ &=2\times\left(\begin{matrix}n-1\\\lfloor n/2\rfloor\\\end{matrix}\right)\text{por telescópicas}\\ \end{align}$

Si $n=2m$ donde $m\in\mathbb{Z^+}$, entonces $\sum\limits_{r=0}^n\left[\begin{matrix}n\\r\\\end{matrix}\right]=\left(\begin{matrix}2m\\m\\\end{matrix}\right)$.

Si $n=2m+1$ donde $m\in\mathbb{Z^+}$, entonces $\sum\limits_{r=0}^n\left[\begin{matrix}n\\r\\\end{matrix}\right]=2\times\left(\begin{matrix}2m\\m\\\end{matrix}\right)$.

Answer 3

Se me ocurrió una prueba combinatoria simple, en el espíritu de la prueba de la fórmula para los números catalanes. Si bien esta respuesta es mucho más larga que las anteriores publicadas, personalmente me gusta mucho la intuición de esta solución visual.

Solo me enfocaré en el lado derecho del triángulo, y mostraré que la suma de los números en el lado derecho de la $2n$-ésima fila es $2n \choose n$.

Mirando la entrada más a la izquierda del lado derecho de la $2n$-ésima fila, como ustedes notaron, vemos el número catalán $C_n$. Esto se debe a que hay $C_n$ posibles caminos desde la parte superior hasta este cuadrado.

Los números catalanes a menudo se visualizan con el siguiente diagrama, donde $C_n$ es el número de caminos desde la esquina superior izquierda hasta la esquina inferior derecha, que no cruzan por debajo de la diagonal (y solo van hacia la derecha y hacia abajo).

Este es en realidad lo mismo que observar los caminos en los triángulos de arriba después de girar nuestras cabezas $45$ grados, y estirar un poco la imagen.

En el diagrama, también podemos encontrar la suma del lado derecho de la $2n$-ésima fila, que es $2n\choose n$, como el número de caminos desde la esquina superior izquierda hasta la esquina inferior derecha, tomando solo pasos hacia la derecha o hacia abajo (ahora permitimos cruzar por debajo de la diagonal).

Ahora, ¿a qué corresponden los otros números en el lado derecho de la $2n$-ésima fila? Podemos ilustrarlos de la misma manera: caminos que no cruzan la diagonal, pero dan más pasos hacia la derecha que hacia abajo. Esto fue mencionado en un comentario por @Phicar también. Más precisamente, el número que está $k$ lugares a la derecha de $C_n$ en nuestro "triángulo de Pascal" corresponde al número de caminos que parten desde $L$ en el siguiente diagrama, yendo $n+k$ pasos a la derecha y $n-k$ pasos hacia abajo, sin cruzar por debajo de la diagonal, llegando a $P_k$.

Ahora, viene la pregunta: ¿Por qué el número de caminos desde $L$ hasta $P_0$ es igual a la suma del número de caminos desde $L$ hasta cualquiera de los puntos $P_i$, sin cruzar por debajo de la diagonal roja?

Encontraremos una biyección entre el primer tipo de caminos y el segundo tipo de caminos. Escribimos cada camino como una secuencia binaria con $2n$ bits, donde $1$ corresponde a dar un paso a la derecha, y $0$ corresponde a dar un paso hacia abajo. Queremos encontrar una función biyectiva del conjunto de secuencias binarias de longitud $2n$, con exactamente $n$ unos y $n$ ceros, al conjunto de secuencias binarias de longitud $2n$, con la característica de que si se divide la secuencia en dos en cualquier punto, y se mira la primera parte, se obtiene una secuencia con más unos que ceros (esto corresponde a no cruzar por debajo de la diagonal).

Si se cuenta el número de caminos desde $L$ hasta $P_0$, que cruzan la diagonal pero no cruzan la siguiente diagonal (marcada en amarillo en el siguiente diagrama), se notará que es exactamente el número de caminos desde $L$ hasta $P_1$ que no cruzan la diagonal roja. Similarmente, el número de caminos desde $L$ hasta $P_0$ que cruzan la diagonal amarilla, pero no la siguiente, es igual al número de caminos desde $L$ hasta $P_2$ que no cruzan la diagonal roja, y así sucesivamente (donde el número de caminos yendo todo el camino hasta el punto inferior izquierdo es exactamente el número de caminos yendo a $P_3$: solo un camino). Esto da una pista, de que tal vez la función que estamos buscando debería cambiar $k$ bits de $0$ a $1$, para caminos que vayan $k$ pasos por debajo de la diagonal.

Esto me llevó a la siguiente función: Leer la secuencia binaria bit por bit. Si en algún momento, se lee un cero tal que la secuencia hasta ese punto tiene más ceros que unos, cambie este cero a un uno, y continúe leyendo la secuencia. En el lenguaje de los caminos en el diagrama - sigue con el camino, y cada vez que se supone bajar por debajo de la diagonal, cambia este movimiento a uno hacia la derecha, luego sigue adelante (y cambia de nuevo si cruzas de nuevo). Otra forma de expresar esto es - cambia el primer paso que cruza la diagonal roja, el primer paso que cruza la diagonal amarilla, y así sucesivamente.

La función inversa es bastante similar. Supongamos que tienes un camino que termina en $P_k$. Entonces su secuencia de bits tiene $2k$ unos más que ceros. Lee la secuencia de bits en reversa, y cada vez que veas un bit $1$, tal que la secuencia hasta ese momento tiene más unos que sumar los ceros más $k$, cambia este uno a un cero, y continúa.

Verificar que estas dos funciones son inversas entre sí termina la prueba. Aquí hay un diagrama que muestra un camino azul desde $L$ hasta $P_0$, y el nuevo camino verde desde $L$ hasta $P_2$ que genera la función después de cambiar los bits. Los pasos marcados con flechas moradas son exactamente los que fueron "cambiados" por la función, y los que serán cambiados de vuelta por la función inversa.

Si llegaste hasta aquí - ¡Realmente disfruté encontrar esta respuesta, y espero que hayas disfrutado leyéndola!