Tengo el patrón: 1 + 2 + 3 + 4 + 5 + 6, pero necesito la fórmula para ello

Question

Estoy escribiendo un software que toma un grupo de usuarios y compara cada usuario con todos los demás usuarios del grupo. Necesito mostrar la cantidad de comparaciones necesarias para una función de tipo cuenta atrás.

Por ejemplo, este grupo [1,2,3,4,5] se analizaría así:

1-2, 1-3, 1-4, 1-5
2-3, 2-4, 2-5
3-4, 3-5
4-5

Creando pequeños diagramas como este he averiguado el patrón que es el siguiente:

Users - Comparisons
2     -   1
3     -   3 (+2)
4     -   6 (+3)
5     -   10 (+4)
6     -   15 (+5)
7     -   21 (+6)
8     -   28 (+7)
9     -   36 (+8)

Necesito ser capaz de tomar cualquier número de usuarios, y calcular cuántas comparaciones se necesitarán para comparar cada usuario con todos los demás.

¿Puede alguien decirme cuál es la fórmula para esto?

Answer 1

Quieres saber cuántas formas hay de elegir $2$ usuarios de un conjunto de $n$ usuarios.

En general, el número de formas de elegir $k$ elementos de un conjunto de orden $n$ (es decir, todos los elementos del conjunto son distintos) se denota por $$ \binom{n}{k} $$

y equivale a $$ \frac{n!}{(n-k)!k!} $$

En el caso de $k=2$ este último es igual a $$ \frac{n!}{(n-2)!2!}=\frac{n(n-1)}{2} $$

que también es la suma de $1+2+...+n-1$ .

Para más información, consulte Coeficiente binomial y Progresión aritmética

Answer 2

La suma de $0+\cdots + n-1$ es $$\frac12(n-1)n.$$

Aquí $n$ es el número de usuarios; se necesitan 0 comparaciones sólo para el primer usuario, 1 para el segundo (para compararlo con el primero), 2 para el tercer usuario, y así sucesivamente, hasta el $n$ usuario que debe ser comparado con el $n-1$ usuarios anteriores.

Por ejemplo, para $9$ gente que está sumando $0+1+2+3+4+5+6+7+8$ que es igual a $$\frac12\cdot 8\cdot 9= \frac{72}{2} = 36$$ y para $10$ personas que pueden computar $$\frac12\cdot9\cdot10 = \frac{90}2 = 45.$$

Answer 3

La siguiente forma de obtener la solución es hermosa y se dice que fue encontrada por el joven Gauss en la escuela. La idea es que el orden de sumar $1+2+\cdots+n=S_n$ no cambia el valor de la suma. Por lo tanto:

$$1 + 2 + \ldots + (n-1) + n=S_n$$ $$n + (n-1) + \ldots + 2 + 1=S_n$$

Sumando las dos ecuaciones término a término se obtiene

$$(n+1)+(n+1)+\ldots+(n+1)=2S_n$$

así que $n(n+1)=2S_n$ . Para $n$ personas, hay $S_{n-1}$ posibilidades, como ya han mostrado muy bien otras respuestas.

Answer 4

La suma discreta hasta un valor finito $N$ está dada por,

$$\sum_{n=1}^{N} n = \frac{1}{2}N(N+1)$$

Prueba:

La prueba por inducción se reduce aproximadamente a:

$$S_N = 1+ 2 +\dots+N$$

$$S_{N+1}= 1+ 2 + \dots + N + (N+1) = \underbrace{\frac{1}{2}N(N+1)}_{S_N} + (N+1)$$

asumiendo que la hipótesis de inducción es verdadera. El lado derecho:

$$\frac{N(N+1)}{2}+(N+1)=\frac{(N+1)(N+2)}{2}$$

que es precisamente la hipótesis de inducción aplicada a $S_{N+1}$ .

---

Sólo por curiosidad, el caso $N=\infty$ es, por supuesto, divergente. Sin embargo, con el uso de la función zeta, se puede regularizar para obtener,

$$\sum_{n=1}^{\infty}n = \zeta(-1)=-\frac{1}{12}$$

Answer 5

$$N=2:\ 1 + 2 = (1 + 2) = 1\times3$$

$$N=4:\ 1 + 2 + 3 + 4 = (1 + 4) + (2 + 3) = 2\times5$$

$$N=6:\ 1 + 2 + 3 + 4 + 5 + 6 = (1 + 6) + (2 + 5) + (3 + 4) = 3\times7$$

$$N=8:\ 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8= (1 + 8) + (2 + 7) + (3 + 6)+ (4 + 5) = 4\times9$$

De manera más general, $N/2\times(N + 1)$ .

Para impar $N$ , sume el $N-1$ primeros términos (utilizando la fórmula par) junto con $N$ , dando $(N-1)/2\times N+N=N\times(N+1)/2$ .