Explicación combinatoria de por qué $n^2 = {n \choose 2} + {n+1 \choose 2}$

Question

Un ejercicio en el primer capítulo de Matemáticas discretas, elementales y posteriores pide una prueba de la siguiente identidad:

$$ {n \choose 2} + {n+1 \choose 2} = n^2 $$

La solución algebraica me parece obvia, pero no tanto la lógica combinatoria. Creo que el lado derecho se refiere a la elección de uno de n elementos dos veces seguidas para producir un conjunto de dos elementos, incluyendo la posibilidad de que haya elementos duplicados (por ejemplo, se podría elegir el nº elemento dos veces seguidas). Sin embargo, dado que los conjuntos discutidos hasta ahora sí contienen elementos duplicados, es impar interpretar entonces n^2 como una representación de tal conjunto. Tampoco estoy muy seguro de lo que significan las dos partes del lado izquierdo cuando se toman juntas. ¿Cómo puedo pensar en esto intuitivamente basándome en los significados combinatorios de los términos individuales?

Answer 1

Cuántos pares de números $(k,j)$ están ahí para $1\leqslant j,k\leqslant n$ ? La solución obvia es $n^2$ . La otra solución es contar los que tienen $k<j$ y los que tienen $k\geqslant j$ . El primer número se ve que es $$\binom n2 $$ El segundo es $$\binom n2+\binom n1=\binom{n+1}2$$

Dado que la elección de un subconjunto de dos elementos de un $n+1$ -su tamaño equivale a elegir $2$ de la primera $n$ elementos o fijación $n+1$ y elegir uno de los primeros $n$ elementos.

(La idea geométrica es que un cuadrado compuesto por $n^2$ pequeños cuadrados de tamaño $1\times 1$ es la unión de dos triángulos formados por $\binom n2$ y $\binom{n+1}2$ pequeños cuadrados).

Answer 2

$n^2$ es el número de enteros no negativos menores que $100_n$ .

$2 {n \choose 2}$ es el número de enteros no negativos con dígitos distintos menores que $100_n$

${n \choose 1} = n$ es el número de enteros no negativos con los mismos dos dígitos menos que $100_n$

Ahora, por supuesto, necesitamos un argumento para ${n \choose 2} + n = {n + 1 \choose 2}$ .

Hay $n \choose 2$ formas de elegir dos elementos de un conjunto de $n$ elementos. Para encontrar el número de formas de elegir dos elementos de un conjunto de $n+1$ incluimos todas las posibilidades de los elementos $n$ junto con cada elemento del $n$ emparejado con el nuevo elemento del $n+1$ elemento.

Answer 3

Todas las respuestas publicadas anteriormente son útiles en gran medida. Pero, estoy dando una prueba visual (más que la combinatoria).

Lo que quieres es $$\begin{align} &{n\choose 2}+{n+1\choose 2}=n^2\\ \implies&\frac {n(n-1)}2+\frac {(n+1)n}2=n^2\\ \implies&(1+2+\dots+(n-1))+(1+2+\dots+n)=n^2. \end{align}$$

Ahora, considera este cuadrado, coloreándolo de esta manera. Aquí estoy dando para $n=6$ se puede generalizar fácilmente, tomando $n$ -cuadros laterales.

En este caso, el número de cuadrados coloreados es $$\color{red}{6+5+4+3+2+1=\frac {6\times 7}2={6+1\choose 2}}.$$

Ahora colorea los demás elementos de esta manera,

Por lo tanto, aquí el número de cuadrados coloreados es $$\color{magenta}{5+4+3+2+1=\frac {5\times 6}2={6\choose 2}}.$$

Y ahora, resuma esto. Lo que obtienes es

En este caso, el número de cuadrados coloreados es $$\color{blue}{6\times 6=6^2\text{[total number of squares]}}$$

Así que, en última instancia, lo que obtenemos es $${\color{red}{\text{no. of red coloured squares}}}+{\color{magenta}{\text{no. of pink coloured squares}}}={\color{blue}{\text{total number of squares}}}$$ $$\implies\color{red}{6+1\choose 2}+\color{magenta}{6\choose 2}=\color{blue}{6^2}$$

Así, en general (tomando $n$ -cuadrados de lado), tenemos $$\implies\color{red}{n+1\choose 2}+\color{magenta}{n\choose 2}=\color{blue}{n^2}$$

Answer 4

No veo ninguna explicación directa para esta identidad, pero puedo ver algo muy simple si se aplica ${n+1 \choose 2} = {n\choose2} + {n \choose 1}$ .

$${n \choose 2} + {n \choose 2} + {n \choose 1} = 2{n \choose 2} + {n \choose 1} + n^2$$

$n^2$ es el número de formas de seleccionar dos elementos de un conjunto de $n$ permitiendo los duplicados, y teniendo en cuenta el orden . $n \choose 2$ es el número de formas de seleccionar dos no duplicados de $n$ pero sin tener en cuenta el orden. Como no tenemos en cuenta el orden, tenemos que duplicar para obtener el número total de formas de seleccionar dos elementos distintos. Entonces sólo tenemos que ocuparnos del caso en el que seleccionamos el mismo elemento dos veces, que es $n\choose1$ .

Answer 5

Dados n símbolos, el número de formas en que se pueden llenar 2 locs, permitiendo repeticiones es n².

Se puede dividir en tres grupos. En primer lugar, C(n,2) pares de combinaciones básicas de 2. En segundo lugar otro C(n,2) pares idénticos, pero invertidos, más n dobles.

Para combinar los dos últimos grupos observamos que C(n+1,2) cubre todo C(n,2) más n pares que incluyen el símbolo extra. Si en cada uno de estos n pares sustituimos el símbolo extra por su compañero, el resultado es el siguiente.

Por lo tanto n² = C(n,2) + C(n+1,2)