Interpretación combinatoria de la suma de cuadrados y cubos

Question

Considere la suma de la primera $n$ enteros: $$\sum_{i=1}^n\,i=\frac{n(n+1)}{2}=\binom{n+1}{2}$$ Esto siempre ha tenido el siguiente sentido combinatorio para mí. Imagina el conjunto $\{*,1,2,\ldots,n\}$ . Podemos elegir dos de este conjunto, ordenarlos de forma decreciente y obtener así un punto en $\mathbb{N}^2$ . Interpretamos $(i,*)$ como $(i,i)$ . Estos puntos ofrecen una clara representación gráfica de $1+2+\cdots+n$ :

$$ \begin{matrix} &&&\circ\\ &&\circ&\circ\\ &\circ&\circ&\circ\\ \circ&\circ&\circ&\circ\\ \end{matrix} $$

Identidades similares son: $$\sum_{i=1}^n\,i^2=\frac{n(n+1)(2n+1)}{6}=\frac{2n(2n+2)(2n+1)}{24}=\frac{1}{4}\binom{2n+2}{3}$$ $$\sum_{i=1}^n\,i^3=\frac{n^2(n+1)^2}{4}=\binom{n+1}{2}^2$$ Conozco las explicaciones geométricas de estas identidades, pero no las combinatorias similares a la explicación anterior para la suma de primeras potencias que hacen uso directo de la interpretación de "elección" del coeficiente del binomio. ¿Puede alguien ofrecer pruebas combinatorias de las mismas?

Answer 1

Aquí hay una prueba combinatoria para $$\sum_{k=1}^n k^2 = \binom{n+1}{2} + 2 \binom{n+1}{3},$$ que no es más que otra forma de expresar la suma. Ambos lados cuentan el número de triples ordenados $(i,j,k)$ con $0 \leq i,j < k \leq n$ .

Para el lado izquierdo La condición para el valor de $k$ . Para cada $k$ Hay $k^2$ formas de elegir $i$ y $j$ del conjunto $\{0, 1, \ldots, k-1\}$ .

Para el lado derecho Considere los casos $i=j$ y $i \neq j$ por separado. Si $i = j$ entonces hay $\binom{n+1}{2}$ tales triples. Esto se debe a que sólo elegimos dos números de $\{0, \ldots, n\}$ cuanto menor sea el valor de $i$ y $j$ y el mayor debe ser el valor de $k$ . Si $i \neq j$ entonces hay $2\binom{n+1}{3}$ tales triples, ya que podríamos tener $i < j$ o $j < i$ para los dos números más pequeños.

---

Para $$\sum_{k=1}^n k^3 = \binom{n+1}{2}^2,$$ ambos lados cuentan el número de 4tuplas ordenadas $(h,i,j,k)$ con $0 \leq h,i,j < k \leq n$ .

Para el lado izquierdo , una vez más si condicionamos el valor de $k$ vemos que hay $\sum_{k=1}^n k^3$ tales 4-tuplas.

Para el lado derecho existe una biyección desde estas 4 tuplas a pares ordenados de dos tuplas $(x_1,x_2), (x_3,x_4)$ con $0 \leq x_1 < x_2 \leq n$ y $0 \leq x_3 < x_4 \leq n$ . Hay $\binom{n+1}{2}^2$ tales pares, así que veamos la biyección.

La biyección : Si $h < i$ , entonces el mapa $(h,i,j,k)$ a $(h,i),(j,k)$ . Si $h > i$ , a continuación, el mapa $(h,i,j,k)$ a $(j,k), (i,h)$ . Si $h = i$ , a continuación, el mapa $(h,i,j,k)$ a $(i,k), (j,k)$ . Este mapeo es reversible, ya que estos tres casos corresponden a los casos en los que $x_2 < x_4$ , $x_2 > x_4$ y $x_2 = x_4$ .

---

(Ambas pruebas se encuentran en el capítulo 8 de Pruebas que realmente cuentan por Benjamin y Quinn. También dan al menos otra prueba combinatoria para cada una de estas identidades).

Answer 2

Damos una interpretación combinatoria de la fórmula $$ 2^2+4^2+6^2+\cdots +(2n)^2=\binom{2n+2}{3} \qquad\qquad (1) $$ para la suma del primer $n$ incluso cuadrados.

Hay $\binom{2n+2}{3}$ formas de elegir $3$ números de los números $1, 2, \dots, 2n+2$ . Organizamos y contamos las opciones de otra manera.

Tal vez el mayor número elegido sea $2k+1$ o $2k+2$ . Si es $2k+1$ los otros dos pueden ser elegidos en $\binom{2k}{2}$ maneras, y si es $2k+2$ entonces los otros dos pueden ser elegidos en $\binom{2k+1}{2}$ formas. El total es $$\frac{(2k)(2k-1)}{2} +\frac{(2k+1)(2k)}{2}\quad\text{that is,}\quad (2k)^2.\qquad\qquad(2)$$ Tome $k=1, 2, 3, \dots, n$ . Por Fórmula $(2)$ el número de formas de elegir $3$ números de $1, 2, \dots, 2n+2$ es $$ 2^2+4^2+6^2+\cdots +(2n)^2. $$

El argumento anterior no era puramente biyectiva, debido al "cálculo" de la fórmula $(2)$ . Pero hay una solución estándar que produce una prueba puramente biyectiva del hecho de que $$ \binom{m}{2} +\binom{m+1}{2}=m^2. $$ La idea geométrica es que la suma de dos números triangulares consecutivos es un cuadrado. Más formalmente, dejemos que $M$ sea la colección $\{1,2,3,\dots,m\}$ . Entonces el número de pares ordenados $(a,b)$ con $a$ y $b$ en $M$ es $m^2$ . Estos pares ordenados son de dos tipos: (i) los que tienen $a<b$ y (ii) los que tienen $a \ge b$ . El número de pares ordenados $(a,b)$ con $a<b$ es sólo $\binom{m}{2}$ . El número de pares ordenados $(a,b)$ con $a \ge b$ es el mismo que el número de pares ordenados $(b,a+1)$ con $b<a+1$ y esto es $\binom{m+1}{2}$ .

Comentario: Se deduce por "álgebra" de la Fórmula $(1)$ que $$ 1^2+2^2+\cdots +n^2=\frac{1}{4}\binom{2n+2}{3}. \qquad\qquad(3) $$ (La división algebraica por $4$ puede obviarse contando las clases de equivalencia adecuadas, dando una prueba prístinamente biyectiva de $(3)$ .)

Cuando vi por primera vez la expresión habitual $\dfrac{(n)(n+1)(2n+1)}{6}$ para la suma del primer $n$ cuadrados, recuerdo haber pensado que el $2n+1$ de alguna manera parece que no encaja. Pero lo hace, en realidad es $n$ y $n+1$ ¡que son extraños! Podemos pensar en $(n)(n+1)(2n+1)$ como ``realmente'' ser $(1/4)[(2n)(2n+1)(2n+2)]$ .

Answer 3

Esto es viejo, pero aquí hay una prueba diferente de $$ \sum_{k=1}^n k^2 = \frac{1}{4}\binom{2n+2}{3} $$

Primero considere las palabras $w_1w_2w_3$ en $[n+1]$ donde $w_1, w_2 < w_3$ y, además, cada letra de color rojo o azul. Llama al número total de estas $S$ .

Fijación de $w_3 = j+1$ Hay $j^2$ formas de elegir $w_1$ y $w_2$ y luego $8$ formas de colorear el palabra resultante. Suma sobre $j$ concluimos que el h.l. es $S/8$ .

Por otro lado, piense en tener $n+1$ puntos rojos y $n+1$ azules. Evidentemente, hay $\binom{2n+2}{3}$ formas de elegir tres de ellas. El $3$ -donde los índices de los puntos coloreados son distintos se sobrecontabilizan en $S$ por un factor de $2$ ya que si $w_1\neq w_2$ y, a continuación, las palabras coloreadas $w_1w_2w_3$ y $w_2w_1w_3$ se asignan al mismo conjunto de puntos coloreados. En el caso de que $w_1 = w_2$ este sobreconteo no está presente, pero los conjuntos coloreados como corresponden bijetivamente a conjuntos coloreados sin un índice mayor distinto, que no son contados por $S$ en absoluto.

Así, $\binom{2n + 2}{3} = S/2$ y la identidad que queríamos es la siguiente.

Answer 4

En general,

$$ \sum_{i=0}^n\, \binom{i}{k}=\binom{n+1}{k+1}.$$

Una interpretación combinatoria para esto es: el RHS es el número de maneras de elegir un equipo de $k+1$ personas fuera de $n+1$ personas numeradas del 1 al $n+1$ . El LHS es el número de formas de elegir a la persona de mayor número del equipo (persona # $i+1$ ) y luego elija $k$ de la $i$ personas con números más bajos.

En general, puedes hacer cuadrados, cubos, etc. -cualquier polinomio, de hecho- a partir de una combinación lineal de coeficientes de binomios, así que esas sumas son todas combinaciones lineales de las fórmulas anteriores.