Por favor, ayúdenme a calcular esta suma: $$ \sum\limits_{1\leq i_1 < i_2 <\ldots i_k \leq n} (i_1+i_2+\ldots+i_k). $$
Aquí $n$ y $k$ son números enteros positivos, y todos los números $i_1, i_2, \ldots, i_k$ son enteros positivos.
Respuestas
¿Demasiados anuncios?
Roger Hoover
Puntos
56
La clave es la doble contabilidad. Dado cualquier $m\in[1,n]$ pertenece exactamente a $\binom{n-1}{k-1}$ $k$ -tuplas $(i_1,\ldots,i_k)$ con $1\leq i_1<i_2\ldots<i_{n-1}<i_n\leq n$ Por lo tanto:
$$ \sum_{1\leq i_1<\ldots<i_n\leq n}(i_1+\ldots+i_k) = \sum_{m=1}^{n}m\binom{n-1}{k-1}=\binom{n+1}{2}\binom{n-1}{k-1}.$$
Elaqqad
Puntos
10648
Utilizando el método de Gauss para las sumas: $$2S= \sum_{1\leq i_1<\ldots<i_n\leq n}(i_1+\ldots+i_k)+\sum_{1\leq i_1<\ldots<i_n\leq n}((n+1-i_1)+\ldots+(n+1-i_k))=(n+1)k \dbinom{n}{k} $$
porque hay exactamente $\binom{n}{k}$ $k$ -tuplas $(i_1,\ldots,i_k)$ con $1\leq i_1<i_2\ldots<i_{n-1}<i_n\leq n$
Marko Riedel
Puntos
19255
El lector puede sorprenderse al saber que esto puede resolverse con índices de ciclo.
Supongamos que queremos evaluar $$\sum_{1\le q_1 \lt q_2 \lt \cdots \lt q_k \le n} (q_1+q_2+\cdots+q_k).$$
Utilización del índice del ciclo $Z(P_k)$ del operador de conjunto no etiquetado $\mathfrak{P}_{=k}$ esto es $$\left. \frac{d}{dz} Z(P_k)(z+z^2+\cdots+z^n)\right|_{z=1}.$$
El OGF del operador conjunto es $$G(w) = \exp\left(a_1 w - a_2 \frac{w^2}{2} + a_3 \frac{w^3}{3} - \cdots\right).$$
Haciendo la sustitución obtenemos $$H(w, z) = \exp\left(\sum_{q\ge 1} \frac{(-1)^{q-1} w^q}{q} \sum_{p=1}^n z^{pq}\right).$$
Diferenciar para obtener $$\frac{d}{dz} H(w,z) = \exp\left(\sum_{q\ge 1} \frac{(-1)^{q-1} w^q}{q} \sum_{p=1}^n z^{pq}\right) \sum_{q\ge 1} \frac{(-1)^{q-1} w^q}{q} \sum_{p=1}^n pq z^{pq-1}$$
y establecer $z=1$ para obtener $$\left.\frac{d}{dz} H(w,z)\right|_{z=1} = \exp\left(n\log(1+w)\right) \sum_{q\ge 1} (-1)^{q-1} w^q \sum_{p=1}^n p \\ = {n+1\choose 2} (1+w)^n \frac{w}{1+w} = {n+1\choose 2} w (1+w)^{n-1}.$$
Extrayendo los coeficientes de esto obtenemos finalmente $$[w^k] {n+1\choose 2} w (1+w)^{n-1} = {n+1\choose 2} [w^{k-1}] (1+w)^{n-1} = {n+1\choose 2} {n-1\choose k-1}.$$
