¿Se trata de un nuevo descubrimiento en las diagonales del triángulo de Pascal?

Question

Antes de nada, estoy en el último curso del instituto y mis conocimientos de combinatoria y su notación son bastante limitados. Me topé con el triángulo de Pascal mientras me taladraba la cabeza con las expansiones binómicas, y rápidamente me fascinaron sus diversas propiedades. Cuando me fijé en las diagonales, quise desafiarme a mí mismo ideando fórmulas para las diagonales, y empecé con las dos primeras diagonales.

Una vez más, no estoy familiarizado con la notación estándar, así que, por favor, no le prestes atención por ahora. Sin embargo, agradecería mucho cualquier consejo sobre lo que debería cambiar, y dónde puedo aprender la notación estándar. Estoy haciendo este post de un "papel" que escribí para recoger mis pensamientos, se utilizarán capturas de pantalla de dicho documento.

Para las diagonales, utilizaré D _n donde cada valor de n representa cada diagonal. (ej: D ₂ \= [1, 2, 3, 4, 5, 6...]

Para los números dentro de los conjuntos de D _n utilizaré d _n .
D _n \= [d ₁ , d ₂ , d ₃ ...]

Así que para las dos primeras diagonales

D ₁ : d _n \= 1
D ₂ : d _n \= x

A medida que me acercaba a la tercera diagonal, mi mente saltó inmediatamente a la recursividad, y la fórmula para D _n sería

D ₃ : d _n \= d _n-1 + x; d _n<1 \= 0 (esto se aplica a todas las fórmulas posteriores)

La fórmula para D ₄ me tomó un poco más de tiempo, pero sabía que el conjunto de D ₄ era mayor que D ₃ por lo que su fórmula debe contener la fórmula de D ₃ y otro término positivo. Después de un poco de lío, llegué a hacer el siguiente término de la siguiente manera.

D ₄ : d _n \= d _n-1 + x + (d _n-1 - d _n-2 )

Al día siguiente, continué con mi lluvia de ideas e hice las 2 fórmulas siguientes.

D ₅ : d _n \= d _n-1 + x + 2(d _n-1 - d _n-2 ) - (d _n-2 - d _n-3 )
D ₆ : d _n \= d _n-1 + x + 3(d _n-1 - d _n-2 ) - 3(d _n-2 - d _n-3 ) + (d _n-3 - d _n-4 )

Me topé con un muro durante un rato, y me quedé mirando las fórmulas que tenía durante horas hasta que me di cuenta de algo. Miré los coeficientes de los términos y vi que se formaba un patrón; los coeficientes siguen el triángulo de Pascal. Esto se puede visualizar mejor en la imagen de abajo, que incluye las fórmulas de D ₃ a través de D ₈ .

Disculpas por mi letra

Los coeficientes de las fórmulas parecen seguir indefinidamente los valores del triángulo de Pascal. Cabe señalar que para los conjuntos D _n donde d ₂ es un número impar, los coeficientes son siempre filas binomiales centrales y el último término es siempre negativo. Y para los conjuntos D _n donde d ₂ es un número par, los coeficientes son siempre filas centrales de trinomios y el último término es siempre positivo. Teniendo esto en cuenta, seguí el patrón para hacer la fórmula de D ₁₁ y lo utilizamos para resolver d ₁₀ de D ₁₁ .

de nuevo, escritura a mano

Así que aquí es donde estoy en este momento, nada más aparte de eso, excepto mis preguntas finales y algunas pruebas básicas en la parte inferior.

1. ¿He encontrado algo nuevo? No el uso de la fórmula en sí, porque sé que hay otros métodos mucho más eficientes, sino el patrón que estoy viendo en los coeficientes. ¿Otros métodos para obtener un número en una diagonal del triángulo de Pascal muestran las filas del triángulo de Pascal como lo hace este método?

2. Independientemente de si esto es nuevo o no, ¿me pueden ayudar con la notación? Sé que hay alguna manera de hacer y notar una fórmula para fórmulas.

D ₃ D ₄ D ₅

D ₆ D ₇ D ₈

Answer 1

¡Bien visto!

Esto se debe a importantes propiedades conocidas del coeficientes binomiales .

Lo que escribe como entrada $d_n$ en la diagonal $D_k$ suele escribirse como el coeficiente binomial $\binom {n-1+k-1}{k-1}$ . Para no restar $1$ todo el tiempo, escribiré el patrón que encontraste para la entrada $d_{n+1}$ en la diagonal $D_{k+1}$ . Esto es

$$ \binom {n+k}k=\binom{n+k-1}k+n+1+\sum_{j=1}^{k-2}(-1)^{j+1}\binom{k-2}j\left[\binom{n+k-j}k-\binom{n+k-j-1}k\right] $$

(donde he asumido que, como se ha discutido en los comentarios, querías decir $x$ para representar $n$ - normalmente nos quedamos con un nombre para una variable).

Para simplificarlo, observe que los dos términos a cada lado del signo igual son precisamente los que se obtienen si se amplía la suma hasta $j=0$ por lo que se puede escribir como

$$ 0=n+1+\sum_{j=0}^{k-2}(-1)^{j+1}\binom{k-2}j\left[\binom{n+k-j}k-\binom{n+k-j-1}k\right]\;. $$

Puede sustituir el límite superior de la suma por $n$ porque cualquier término con $j\gt k-2$ no contribuyen ya que el primer factor es cero y cualquier término con $j\gt n$ no contribuyen ya que el segundo factor es cero (hay cero formas de elegir $k$ de $n$ objetos cuando $k\gt n$ ); por tanto, de forma equivalente,

$$ 0=n+1+\sum_{j=0}^n(-1)^{j+1}\binom{k-2}j\left[\binom{n+k-j}k-\binom{n+k-j-1}k\right]\;. $$

A continuación, puede aplicar la relación de recurrencia básica para el triángulo de Pascal ,

$$ \binom nk=\binom{n-1}k+\binom{n-1}{k-1}\;, $$

para sustituir la diferencia entre paréntesis por un único coeficiente binomial:

$$ 0=n+1+\sum_{j=0}^n(-1)^{j+1}\binom{k-2}j\binom{n+k-j-1}{k-1}\;, $$

o

$$ \sum_{j=0}^n(-1)^j\binom{k-2}j\binom{n+k-j-1}{k-1}=n+1\;. $$

Este es el contenido principal de su fórmula, despojado de complicaciones innecesarias. Yo no lo llamaría una ecuación conocida en esta forma exacta, pero es un tipo de relación entre coeficientes binomiales que es bien conocida y a menudo útil. Puedes derivarla aplicando las siguientes transformaciones. En primer lugar, utiliza la simetría de los coeficientes binomiales ,

$$ \binom nk=\binom n{n-k}\;, $$

que conduce a

$$ \sum_{j=0}^n(-1)^j\binom{k-2}j\binom{n+k-j-1}{n-j}=n+1\;. $$

Ahora aplica la fórmula para negar el coeficiente superior, que es

$$ \binom nk=(-1)^k\binom{k-n-1}k\;, $$

al segundo factor. (Aquí estoy utilizando un generalización de los coeficientes binomiales a números enteros negativos ; estos coeficientes no aparecen en el triángulo de Pascal, pero pueden ser muy útiles). Esto nos lleva a

$$ (-1)^n\sum_{j=0}^n\binom{k-2}j\binom{-k}{n-j}=n+1\;. $$

Ahora viene una bonita relación conocida como La identidad de Vandermonde :

$$ \binom{m+n} r=\sum_{k=0}^r\binom mk\binom n{r-k}\;. $$

Si $m$ , $n$ y $r$ son enteros no negativos, esto expresa el hecho de que elegir $r$ de $m+n$ objetos puede hacerse eligiendo $k$ de $m$ de los objetos y $r-k$ del otro $n$ objetos. Cuando (como en nuestro caso) $m$ y $n$ no están restringidas a números enteros no negativos, la identidad también se conoce como la Identidad Chu-Vandermonde . Aplicándolo con $m=k-2$ y $n=-k$ y, por tanto $m+n=-2$ conduce a

$$ (-1)^n\binom{-2}n=n+1\;. $$

Y eso es sólo la definición de $\binom{-2}n$ :

$$ \binom{-2}n=(-1)^n\binom{n-(-2)-1}n=(-1)^n\binom{n+1}n=(-1)^n\binom{n+1}1=(-1)^n(n+1)\;. $$

Por supuesto, he aplicado los pasos en la dirección equivocada, partiendo de tu observación, pero todas son equivalencias, así que puedes ir en la otra dirección para derivar tu fórmula.

Así que, ¡bien hecho! Has encontrado una relación bastante no trivial entre los coeficientes binomiales que requiere una serie de resultados importantes para derivar. Ten en cuenta que puedes obtener muchas relaciones similares utilizando otros números enteros negativos en lugar de $-2$ .

Puede que todo esto le resulte un poco difícil de asimilar. No dude en plantearme más preguntas y, si lo hace, hágamelo saber en los comentarios.

Answer 2

Es más conveniente empezar a indexar las diagonales empezando por $k=0$ y también indexar los elementos de esas diagonales empezando por $n=0$ . Entonces el $n$ ésimo elemento del $k$ diagonal del triángulo de Pascal es $\binom{n+k}{k}$ . Estás viendo las propiedades de la secuencia de las diferencias de sus términos consecutivos, es decir. $$ \binom{n+k}{k}-\binom{n-1+k}{k}. $$ Le gustaría demostrar que $$ \sum_{j=0}^{k-2}{(-1)^j\binom{k-2}{j}\left(\binom{n+k-j}{k}-\binom{n+k-j-1}{k}\right)}=n+1. $$ Recojamos los términos de otra manera. En esta suma reescrita, consideremos el coeficiente en $\binom{n+k-j}{k}$ . Aparece en dos términos, una vez con signo más y otra con signo menos (excepto en los términos $\binom{n+k}{k}$ y $\binom{n}{k}$ que se puede comprobar que tienen coeficientes $1$ para $j=0$ y $(-1)^k$ para $j=k$ ). Por lo tanto, el coeficiente en $\binom{n+k-j}{k}=\binom{n+k-(j-1)-1}{k}$ es $$ (-1)^j\binom{k-2}{j}-(-1)^{j-1}\binom{k-2}{j-1}=(-1)^j\left(\binom{k-2}{j}+\binom{k-2}{j-1}\right)=(-1)^j\binom{k-1}{j}. $$ Como puede ver, esta fórmula es válida para $j=0$ y $j=k$ también. Por lo tanto, realmente queremos demostrar que $$ \sum_{j=0}^{k-1}{(-1)^j\binom{k-1}{j}\binom{n+k-j}{k}}=n+1. $$ Un buen truco que se puede utilizar aquí (por ejemplo, para evitar generar funciones) es que $$ \binom{n+k-j}{k}=\binom{k+n-j}{n-j}=\frac{(k+n-j)(k+n-j-1)\cdots(k+1)}{(n-j)!}=(-1)^{n-j}\frac{(-k-1)\cdots(-k-(n-j-1))(-k-(n-j))}{(n-j)!}=\binom{-k-1}{n-j}. $$ Si no ha visto antes números negativos en los coeficientes binomiales, este truco puede parecer extraño, pero considere que si escribimos $\binom{n}{k}=\frac{n(n-1)\cdots(n-k+1)}{k!}$ el valor $n$ sólo aparece en el numerador y sólo en un número finito de factores, por lo que puede ser cualquier número real ¡! (E incluso más, pero ahora no lo necesitamos).

Así, tenemos $$ \begin{split} \sum_{j=0}^{k-1}{(-1)^j\binom{k-1}{j}\binom{n+k-j}{k}}&=\sum_{j=0}^{k-1}{(-1)^j\binom{k-1}{j}(-1)^{n-j}\binom{-k-1}{n-j}}\\ &=(-1)^n\sum_{j=0}^{k-1}{\binom{k-1}{j}\binom{-k-1}{n-j}}. \end{split} $$ Observa que los índices inferiores siempre suman $n$ y los índices superiores son constantes. Así, por la identidad de Vandermonde, $$ (-1)^n\sum_{j=0}^{k-1}{\binom{k-1}{j}\binom{-k-1}{n-j}}=(-1)^n\binom{k-1+(-k-1)}{n}=(-1)^n\binom{-2}{n}. $$ Pero, como antes, $$ \binom{-2}{n}=\binom{-1-1}{n}=(-1)^n\binom{n+1}{n}=(-1)^n(n+1), $$ así que $$ (-1)^n\binom{-2}{n}=(-1)^n(-1)^n(n+1)=(-1)^{2n}(n+1)=n+1, $$ como desee.

Answer 3

Como han derivado joriki y Alexander, el patrón que has observado es equivalente a $$ \sum_{j=0}^{k-1}{(-1)^j\binom{k-1}{j}\binom{n+k-j}{k}} $$ Podemos dar una prueba combinatoria de esta identidad, utilizando el principio de exclusión de inclusión.

Sea $S$ sea el conjunto de todos los caminos reticulares desde $(0,0)$ a $(n,k)$ compuesto por $n+k$ pasos, donde cada paso es una unidad hacia arriba o una unidad hacia la derecha, por lo que $|S|=\binom{n+k}{k}$ . Entonces, para cada $i\in \{1,\dots,k-1\}$ , dejemos que $E_i$ sea el conjunto de caminos en $S$ que incluyen al menos una arista de la forma $$ (x,i)\to (x+1,i), $$ para algunos $x\in \{0,1,\dots,n\}$ . Es decir, hay al menos un escalón horizontal a una altura de $i$ . Utilizamos el principio de inclusión-exclusión para contar el complemento de $(E_1\cup \dots \cup E_{k-1})$ : $$ \begin{align} |S\setminus (E_1\cup \dots\cup E_{k-1})| &=\sum_{j=0}^{k-1}(-1)^j\sum_{1\le i_1<\dots<i_j\le k-1}|E_{i_1}\cap \dots \cap E_{i_{j}}| \\&= \sum_{j=0}^{k-1}(-1)^j\binom{k-1}j|E_{1}\cap \dots \cap E_{j}| \\&= \sum_{j=0}^{k-1}(-1)^j\binom{k-1}j\binom{n+k-j}{k}. \end{align} $$ Para ver por qué $|E_{1}\cap \dots \cap E_{j}|=\binom{n+k-j}{k}$ imagínate tomar un camino en $S$ que tiene al menos un escalón horizontal en los niveles $1$ a través de $j$ y suprimiendo el primer escalón horizontal de cada nivel $1$ a través de $j$ . El camino se contraerá horizontalmente, de modo que lo que queda es un camino desde $(0,0)$ a $(n-j,k)$ . El procedimiento es reversible, por lo que $|E_{1}\cap \dots \cap E_{j}|$ está en biyección con el conjunto de todos los caminos de a $(n- j)\times k$ rectángulo, que se enumeran mediante $\binom{n+k-j}k$ .

Sólo queda demostrar que $|S\setminus (E_1\cup \dots\cup E_{k-1})|=n+1$ . En efecto, un camino sin escalones horizontales en los niveles $1$ a través de $k-1$ debe constar de $x$ pasos horizontales en el nivel cero, seguidos de $k$ pasos verticales hasta la parte superior de la rejilla, y completado por $n-x$ escalones horizontales. Dado que $x\in \{0,1,\dots,n\}$ hay $n+1$ maneras de elegir ese camino.

---

En términos más generales, la misma prueba demuestra

$$ \sum_{j=0}^k(-1)^k \binom{k}j \binom{n+m-j}{m}=\binom{n+m-k}{n} $$

Answer 4

A modo de enriquecimiento, para demostrar

$$\sum_{j=0}^k (-1)^j {k\choose j} {n+m-j\choose m} = {n+m-k\choose n}$$

podemos utilizar un extractor de coeficientes para obtener en el LHS que es

$$[z^m] (1+z)^{n+m} \sum_{j=0}^k (-1)^j {k \choose j} (1+z)^{-j} = [z^m] (1+z)^{n+m} \left[1-\frac{1}{1+z}\right]^k \\ = [z^m] (1+z)^{n+m-k} z^k = [z^{m-k}] (1+z)^{n+m-k} = {n+m-k\choose m-k} = {n+m-k\choose n}$$

como se afirma.