Tratar con sumas complicadas - $\sum_{1\leq i < j \leq m}\sum_{1\leq k,l \leq n}\binom{n}{k}\binom{n-k}{l}(j-i-1)^{n-k-l}$

Question

Me estoy preparando para un examen de matemáticas discretas, y no tengo ningún problema cuando se trata de una suma simple, pero cuando veo una monstruosa no sé qué hacer. He aquí un ejemplo:

$$\sum_{1\leq i < j \leq m}\sum_{1\leq k,l \leq n}[k+l\leq n]\binom{n}{k}\binom{n-k}{l}(j-i-1)^{n-k-l}$$ para $m,n > 0$ .

Necesito simplificar esta suma. Los coeficientes binomiales sugieren que podemos pensar en esto de forma cominatoria, pero estoy totalmente atascado. ¿Existe alguna técnica general que sirva de ayuda cuando se trata de este tipo de sumas?

Answer 1

Aquí hay otra variación:

Comenzamos reescribiendo los índices de forma algo más cómoda y mostramos

$$\begin{align*} \sum_{j=2}^{m}\sum_{i=1}^{j-1}\sum_{k=1}^{n-1}\sum_{l=1}^{n-k}\binom{n}{k}\binom{n-k}{l}(j-i-1)^{n-k-l}=m^n-m\tag{1} \end{align*}$$

Aunque la expresión parece complicada debido a las numerosas sumas, podemos resolverla directamente. Los ingredientes esenciales son el teorema del binomio y las sumas telescópicas.

Al principio nos centramos en la doble suma interna de (1):

$$\begin{align*} \sum_{k=1}^{n-1}&\sum_{l=1}^{n-k}\binom{n}{k}\binom{n-k}{l}(j-i-1)^{n-k-l}\\ &=\sum_{k=1}^{n-1}\binom{n}{k}\sum_{l=1}^{n-k}\binom{n-k}{l}(j-i-1)^{n-k-l}\tag{2}\\ &=\sum_{k=1}^{n-1}\binom{n}{k}\left[(j-i)^{n-k}-(j-i-1)^{n-k}\right]\tag{3}\\ &=\sum_{k=1}^{n-1}\binom{n}{k}\left[(j-i)^{k}-(j-i-1)^{k}\right]\tag{4}\\ &=\left[(j-i+1)^n-1-(j-i)^n\right]-\left[(j-i)^n-1-(j-i-1)^n\right]\tag{5}\\ &=(j-i+1)^n-2(j-i)^n+(j-i-1)^n\tag{6} \end{align*}$$

Comentario:

• En (2) reorganizamos los coeficientes binomiales para calcular la suma interna

• En (3) aplicamos el teorema del binomio y restamos $(j-i-1)^{n-k}$ como compensación por el índice $l=0$

• En (4) hacemos una transformación de índice $k \mapsto n-k$ sólo por conveniencia

• En (5) aplicamos de nuevo el teorema del binomio y restamos como compensación por $k=0$ y $k=n$

El siguiente paso es calcular la suma doble externa.

$$\begin{align*} \sum_{j=2}^{m}&\sum_{i=1}^{j-1}\left[(j-i+1)^n-2(j-i)^n+(j-i-1)^n\right]\tag{7}\\ &=\sum_{j=2}^{m}\sum_{i=1}^{j-1}\left[(j-i+1)^n-(j-i)^n\right]\\ &\qquad-\sum_{j=2}^{m}\sum_{i=1}^{j-1}\left[(j-i)^n-(j-i-1)^n\right]\tag{8}\\ &=\sum_{j=2}^{m}\sum_{i=1}^{j-1}\left[(j-i+1)^n-(j-i)^n\right]\\ &\qquad-\sum_{j=1}^{m-1}\sum_{i=1}^{j}\left[(j-i+1)^n-(j-i)^n\right]\tag{9}\\ &=\sum_{i=1}^{m-1}\left[(m-i+1)^n-(m-1)^n\right]-\sum_{j=2}^{m-1}\left[1^n\right]-1\tag{10}\\ &=\sum_{i=1}^{m-1}\left[(i+1)^n-i^n\right]-m+1\tag{11}\\ &=m^n-1-m+1\\ &=m^n-m \end{align*}$$

Comentario:

• En (7) utilizamos el resultado (6) y sustituimos las sumas dobles internas en la expresión OPs (1)

• En (8) reorganizamos la doble suma para poder utilizar de nuevo las sumas telescópicas

• En (9) hacemos un cambio de índice de $j$ en la segunda suma doble y observa $2\leq j \leq m-1,1\leq i \leq j-1$ anular

• En (10) recogemos los términos que no se cancelan

• En (11) observamos que podemos utilizar de nuevo la telescopia

---

Notas:

Las técnicas generales se pueden encontrar en el maravilloso libro de H.Wilf Generación de funcionalidades

De gran utilidad son los de Henry W. Gould Tablas de identidades combinatorias

Pistas: Este ejemplo sobre sumas dobles con coeficientes binomiales podría ser interesante. La respuesta contiene la aplicación de algunas técnicas más sofisticadas que suelen ser útiles. A un reto realmente difícil estaba mostrando que este identidad con polinomios de Bell es válido.

Answer 2

Las sumas de este tipo pueden ser muy complicadas, pero esta es bastante accesible paso a paso. Mi consejo general cuando se abordan estos sería pensar con polinomios, en lugar de combinatoria. Estoy seguro de que hay algún "fuera de $n$ bolas de pintura $k$ rojo y $l$ negro", pero es difícil dar con una regla que funcione siempre, y la mayoría de las veces sólo en retrospectiva te das cuenta de lo que se estaba contando.

Veamos esto paso a paso. Lo primero de los coeficientes binomiales es que hacen cumplir limpiamente las desigualdades sobre los números implicados arriba y abajo. Así que en este caso, el hecho de que multipliquemos el término de la suma por ${n-k} \choose {l}$ garantiza que $l \leq n-k$ porque para todas las demás opciones de números ese coeficiente binomial es cero. Por lo tanto, el agregado $[k+l \leq n]$ no hace nada y puede omitirse.

El segundo paso es intentar razonar utilizando un parámetro/eje a la vez. ¿Podemos hacer algo utilizando sólo los términos que implican $i, j, k$ o $l$ ? En este caso, $l$ parece el más prometedor, porque está en un solo coeficiente binomial y no se eleva a ninguna potencia (se puede desarrollar la intuición sobre esto haciendo muchas sumas, pero en cualquier caso se puede probar con los 4 parámetros y debería atascarse rápidamente en los otros 3).

Podemos dividir la suma doble interna en el $l$ partes y la no $l$ partes, que podemos llevar fuera del $l$ -suma:

$\sum\limits_{k=0}^n {n \choose k} \sum\limits_{l=0}^{n-k} {{n-k} \choose l} (j-i-1)^{n-k-l}$

Ahora esta suma interna sobre $l$ es básicamente de la forma $\sum_l {{u \choose l} t^{u-l}}$ para la elección correcta de $u$ y $t$ y es por definición $(t+1)^u$ . De nuevo, el consejo general es buscar coeficientes binomiales que complementen el exponente del término de la suma.

Así que nos las arreglamos para eliminar el $l$ completamente, y ahora nuestra suma interna se convierte en $\sum\limits_{k=0}^n {n \choose k} (j-i)^{n-k}$ que tiene de nuevo la misma forma de expansión binomial, por lo que puede simplificarse aún más a $(j-i+1)^n$ .

Así que ahora toda nuestra suma es $\sum\limits_{1\leq i < j \leq m} (j-i+1)^n$ que ya es bastante simple, pero podemos llevarlo un poco más allá:

De todos esos $(i,j)$ pares, $(1,2), (2,3) ... (m-1, m)$ tienen una diferencia $1$ . Eso es $m-1$ de ellos. $(1, 3), (2, 4) .. (m-2,m)$ tienen la diferencia 2, y hay $m-2$ de ellos, etc, hasta llegar al único $(1,m)$ que tiene una diferencia $j-i=m-1$ . Así que nuestra doble suma es en realidad una única suma sobre la diferencia, digamos $j-i=d$ y es $\sum\limits_{d=1}^{m-1} (m-d) (d+1)^n$ que se puede dividir en dos partes $(m+1)\sum (d+1)^n - \sum (d+1)^{n+1}$ . Sospecho que esto es lo más sencillo que se puede hacer, las fórmulas para las sumas de las potencias son un poco complicadas, pero puede que haya algún otro truco que se me haya pasado por alto.

De todas formas, mucha suerte con el examen; como he dicho antes, intenta hacer las cosas paso a paso, las sumas monstruosas suelen desmoronarse desde dentro. :)

Answer 3

En realidad, un argumento combinatorio es bastante sencillo.

Considere una función $f:[n]\to[m]$ . Sea $r_f=\min\operatorname{ran}f$ , $s_f=\max\operatorname{ran}f$ , $R_f=f^{-1}[\{r_f\}]$ y $S_f=f^{-1}[\{s_f\}]$ . Sea $R$ y $S$ sean subconjuntos disjuntos y no vacíos de $[n]$ , $k=|R|$ y $\ell=|S|$ y que $i,j\in[m]$ sea tal que $i<j$ . Entonces hay $(j-i-1)^{n-k-\ell}$ funciones $f:[n]\to[m]$ tal que $r_f=i$ , $s_f=j$ , $R_f=R$ y $S_f=S$ . Hay $\binom{n}k\binom{n-k}\ell$ formas de elegir subconjuntos disjuntos $R$ y $S$ de $[n]$ para que $|R|=k$ y $|S|=\ell$ , por lo que hay

$$\binom{n}k\binom{n-k}\ell(j-i-1)^{n-k-\ell}$$

funciones $f:[n]\to[m]$ tal que $r_f=i$ , $s_f=j$ , $|R_f|=k$ y $|S_f|=\ell$ . Llama a este conjunto de funciones $F(i,j,k,\ell)$ . Entonces

$$\sum_{1\le i<j\le m}\sum_{1\le k,\ell\le n}\binom{n}k\binom{n-k}\ell(j-i-1)^{n-k-\ell}$$

es la cardinalidad de

$$\bigcup_{1\le i<j\le m}\bigcup_{1\le k,\ell\le n}F(i,j,k,\ell)\;,$$

que es precisamente el conjunto de funciones no constantes de $[n]$ a $[m]$ . Así,

$$\sum_{1\le i<j\le m}\sum_{1\le k,\ell\le n}\binom{n}k\binom{n-k}\ell(j-i-1)^{n-k-\ell}=m^n-m\;.$$