Simplificar una suma con dos índices

Question

Supongamos que tengo

$$ Sn = \sum{1 \leq j

Objetivo es simplificar la TI. Esto es lo que tengo

$$ Sn = \sum{j=1}^n \sum_{k = j+1}^n a_j ak = \sum{j=1}^n aj \sum{k=j+1}^n a_k $$

¿Es esta una forma correcta de escribir esta suma? ¿Hay otra manera de escribirlo?

Answer 1

Más exactamente $\;\displaystyle Sn = \sum{j=1}^{n-1} aj \sum{k=j+1}^n a_k\quad$ (con $\,n-1\,$ en el lowerBound)

También puede escribir: $\;\displaystyle Sn=\frac{\left(\sum{k=1}^n ak\right)^2-\sum{k=1}^n (a_k)^2}2$

(suponiendo que el producto sobre el $a_k$ conmutativa por supuesto! :-))

Answer 2

Lo que escribes está muy bien. Hay otras formas de escribirlo. El % de condición $1 \leq j

$Sn = \sum{k=2}^{n} ak \sum{j = 1}^{k-1} a_j$

También puede contar las diagonales en el $j$$k$plano:

$Sn = \sum{k=2}^{n} \sum{m = 1}^{n-k+1} a{k+m-1} a_{m}$

o antidiagonals...

Answer 3

La forma esquizofrénica:

Usted puede expresar esto como una simple suma de términos de $n(n-1)/2$

$$\sum{m=1}^{\frac12n(n-1)}a{n-k(m)}a_{n+m-\frac12k(m)(k(m)+1)},$$

donde $k(m):=\left\lfloor\frac{\sqrt{8m-7}+1}2\right\rfloor$.

Answer 4

Me ofrecen una explicación de Yves Daoust la respuesta, así como algunas variaciones.

El número de pares de $(j,k)$ que satisfacer $1\leq j < k \leq n$ es $1 + 2 + 3 + \cdots + (n - 1) = \frac12 n(n-1).$ Con el fin de convertir el doble de la suma en una sola suma, la idea es dejar a $m$ $1, 2, \ldots, \frac12 n(n-1)$ para obtener el número correcto de los términos, y para cada una de las $m$ alguna manera de obtener $i$ $j$ como una función de la $m$ de tal manera que cada par de valores de $(i,j)$ se produce sólo una vez.

Ahora para $n > 1,$ comparar la suma de $1\leq j < k \leq n$ con la suma de $1\leq j < k \leq n - 1.$ La suma más grande tiene exactamente $n - 1$ términos que la suma no, es decir, los términos de $(1,n), (2,n), \ldots, (n-1,n).$ Suponiendo que (por el momento) que usamos las mismas fórmulas para obtener $j$ $k$ $m$ en ambas sumas, los "nuevos" términos en la suma de $1\leq j < k \leq n$ debe ser la última en $n-1$ términos de la suma, es decir, los términos para $\frac12 n(n-1) - (n-2) \leq m \leq \frac12 n(n-1).$ Para realizar este trabajo, necesitamos una función de $f$ tal que $f\left(\frac12 n(n-1) - (n-2)\right) = f\left(\frac12 n(n-1)\right) = n$ pero $f\left(\frac12 n(n-1) - (n-1)\right) = n - 1$ y $f\left(\frac12 n(n-1) + 1\right) = n + 1.$

El hecho de que la función tiene que ser constante para un rango de valores de entrada y, a continuación, aumentar de uno en uno para el siguiente rango de valores de entrada sugiere que se utilice algún tipo de redondeo de la función, tales como el "piso" de la función $\lfloor \cdot \rfloor,$ para forzar los valores de algunos otros que aumenta la función a cero. Si usamos el "piso" de la función para ese propósito, es suficiente encontrar cualquier función de $g$ tal que $g\left(\frac12 n(n-1) - (n-2)\right) = n$ para todos los positivos $n,$ y, a continuación, $f(m) = \lfloor g(m) \rfloor$ nos dará el valor deseado de $k.$

Para encontrar una función de este tipo, vamos a $m = \frac12 k(k-1) - (k-2),$ de modo que $g(m) = k,$ y resolver para $k.$ Para un valor dado de a $m,$ un poco de manipulación algebraica nos da una ecuación de segundo grado en $k$ a resolver, $$ k^2 - 3k + 4 - 2m = 0, $$ que tiene las soluciones $$ k = \frac{3 \pm \sqrt{8m - 7}}{2}. $$

Resulta que, si tomamos las $\pm$ en el lado derecho se $+,$ y la vuelta de la cosa entera hacia abajo a un número entero, tenemos una función de $f$ que hace lo que queríamos: $$ f(m) = \left\lfloor \frac{3 + \sqrt{8m - 7}}{2} \right\rfloor. $$

También resulta que debido al redondeo, la derivación de esta fórmula es un poco indulgente; nada en el formulario $\left\lfloor \frac12 (3 + \sqrt{8m + h}) \right\rfloor$ va a hacer el truco mientras $-7 \leq h < 1.$

En este punto, hemos encontrado la manera de obtener $k = n$ en los últimos $n-1$ términos de la suma, $m,$ de tal manera que la suma ha $1$ plazo con $k=2$ seguido por $2$ términos con $k=3,$ $3$ términos con $k=4,$ y así sucesivamente. Ahora si podemos conseguir $j$ a cuenta de $1$ $k-1$en cada uno de esos grupos de términos, hemos terminado.

Reconociendo que los términos con un determinado valor de $k$ han $\frac12 k(k-1) - (k-2) \leq m \leq \frac12 k(k-1),$ podemos ver que la configuración de $$j = m - \frac12 k(k-1) - (k-2) + 1 = m + 2 - \frac12 k(k+1)$$ se producen valores de $j$ tal que $1 \leq j \leq k - 1.$

Recordando que decidimos $k = f(m),$ la suma es entonces $$ \sum_{m=1}^{n(n-1)/2} a_{m + 2 - f(m) f(m)+1)/2}a_{f(m)}. $$

Usted puede notar que esta expresión se ve muy diferente de la de Yves Daoust la respuesta. Eso es porque hemos hecho un número de opciones arbitrarias en decidir el orden en que los que habría que añadir los términos. En lugar de dejar que $j$ cuenta dentro de cada secuencia de términos con un valor dado de a $k,$ nos podría haber dejado la cuenta atrás de $k-1$ $1.$Alternativamente, podríamos haber tomado todos los términos para $j=1$ primera (hay $n-1$ términos con $2 \leq k \leq n$), en los términos de $j=2,$ y así sucesivamente, terminando con un único término para $j=n-1$ ($k=n$).

O podríamos haber empezado con el término de $j=n-1$ y terminó con la $n-1$ términos de $j=1.$ Que es como Yves Daoust arreglar las cosas. La función $$ k(m) = \left\lfloor \frac{1 + \sqrt{8m - 7}}{2} \right\rfloor $$ es igual a $f(m) - 1$ (de acuerdo a la definición de $f$ anterior), así que en lugar de tomar en valores $2, \ldots, n$ $1 \leq m \leq \frac12 n(n-1)$ toma los valores de $1,\ldots,n-1.$ Es decir, para $m=1,$ el subíndice $n - k(m)$$n-1$; para los próximos dos términos ($2 \leq m \leq 3$) el subíndice $n - k(m)$$n-2$; y así sucesivamente. Así es como el subíndice en $a_{n-k(m)}$ es elegido.

Por el otro subíndice, se puede observar que la $\frac12 k(m)(k(m)+1) \geq m,$ con la igualdad cuando $m=\frac12 p(p-1)$ para algunos entero $p.$ La cantidad de $\frac12 k(m)(k(m)+1) - m$ siempre está en el rango de $\{0, \ldots, k(m) - 1\},$ por lo $n + m - \frac12 k(m)(k(m)+1)$ siempre está en el rango de $\{n - k(m) + 1, \ldots, n\}.$

---

Una nota sobre la utilización práctica de estas fórmulas:

En realidad he utilizado una fórmula relativa a estos con el fin de utilizar un uniformemente repartida, pseudoaleatoria valor para simular una distribución de probabilidad en $\{1,\ldots,n\}$ tal que $P(k)$ era proporcional a $k.$

Una técnica similar se puede reducir el espacio de almacenamiento necesario para una matriz triangular por aproximadamente la mitad.