¿Por qué $\binom{n}{2} =[ (n-1) + (n-2) + (n-3)+\cdots +1]$?

Question

Hace poco estuve haciendo una tarea de problemas que involucraban a encontrar el número de líneas que se utilizan para conectar un número determinado de puntos en un círculo. Mirando lógicamente, vi que para el primer punto, no sería $n-1$ líneas se pueden dibujar (donde $n$ es el número de puntos en el círculo) y el siguiente punto en el que habrían $n-2$ líneas porque no estás repitiendo la línea entre el punto de $1$ y el punto de $2$. Tiene sentido que esto continuaría hasta el punto de $n$, punto en el cual no sería cero líneas puede dibujar.

Esto significa que, si usted acaba de sumar a todos aquellos, que obtendría el número.

Por ejemplo, en la imagen de abajo, hay $12$ puntos, por lo que

$11+10+9+8+7+6+5+4+3+2+1 = 66$ líneas.

Todo eso está bien, pero lo extraño era que, cuando miré en la parte de atrás del libro, la respuesta fue dada como $\binom{n}{2}$, que también es igual a $66$. ¿Cuál es la relación? ¿Por qué son los dos iguales?

Answer 1

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

Y

$$\binom nk = \frac{n!}{k!(n-k)!} = \frac{n\cdot(n-1)\cdots(n-k+1)}{k!}$$

En particular

$$\binom n2 = \frac{n(n-1)}{2} = \sum_{k=0}^{n-1} k$$

Otra forma de verlo es por inducción. En particular $\binom 1 2 = 0$ y $\binom {n+1}{2} = \binom{n}{1} + \binom{n}{2}$, que probablemente hace que la identidad parecen un poco menos "al azar".

Answer 2

Tienes $\binom n 2 = \frac{n(n-1)}2$. Ahora, una fórmula famosa dice que \sum_{k=1}^{n-1}k $$ = \frac{n(n-1)} 2. $$ Esto puede demostrarse por inducción. Para entenderlo - por lo menos cuando es impar $n$ - escribir $$ 1 + \ldots + (n-1) = (1 + (n-1)) + (2 + (n-2)) + \ldots, $$ $(n-1)/2$ veces $n$.

Answer 3

SBareS ha proporcionado una buena respuesta. Aquí está una combinatoria de la prueba.

Hay $\binom{n}{2}$ subconjuntos de a $\{1, 2, 3, \ldots, n\}$ con dos elementos. De estos subconjuntos, hay $k - 1$ subconjuntos con mayor elemento $k$,$1 \leq k \leq n$. Por lo tanto, $$\sum_{k = 1}^{n} (k - 1) = \binom{n}{2}$$

En el problema que usted hizo, creo que de los vértices numerados. Se cuentan las diagonales en el que el vértice con el número más pequeño se $k$,$1 \leq k \leq 12$. Que la suma de los rendimientos $$\sum_{k = 1}^{12} (12 - k) = 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0 = 66$$ Observe que $$\sum_{k = 1}^{n} (n - k) = \sum_{k = 1}^{n} (k - 1) = \binom{n}{2}$$ desde los sumandos son iguales, acaba de escribir en el orden opuesto.

Answer 4

Una manera de obtener el resultado indicado directamente es tener en cuenta que si usted tiene $n$ vértices, a recoger una diagonal es seleccionar un par de vértices, que quiere decir en todos hay $\binom{n}{2}$ diagonales.

Otra forma es elegir cada uno de lo $n$ vértices, participa en $n - 1$ diagonales conectando a los otros vértices, así $n (n - 1)$ en todos. Pero esta cuenta cada diagonal dos veces, una vez para cada uno de sus extremos. Así $n (n - 1) / 2 = \binom{n}{2}$

Answer 5

Usted acaba de explicar.

Supongamos que tenemos una mezcla de azul y blanco bolas. Dibujar 11 y dos de ellos son de color azul. De cuántas maneras puede el dos bolas de color azul ser arreglado?

Si la primera bola en la posición 1, la otra bola podría estar en cualquiera de los otros 10 posiciones. Si la primera bola está en la posición 2, la segunda bola puede estar en cualquiera de las 9 posiciones porque no el doble cómputo de la {1,2} combinación que tenía la primera bola en la posición 1. Y así sucesivamente. Puede ser más fácil ser que el triangular de la suma es igual a la conbination función al uso de las bolas. Pero tge líneas están siendo contados de la misma manera.