Prueba de combinación para $n(n+1)2^{n-2}=\sum_{k=1}^{n}k^2\binom{n}{k}$

Question

¿Cómo puedo demostrar que

dejar $n$ y $k$ sean números enteros. $n(n+1)2^{n-2}=\sum_{k=1}^{n}k^2\dbinom{n}{k}$

Me parece un poco confuso el lado izquierdo. Tiene un conjunto de $n$ personas en un equipo y sigues eligiendo $k$ gente que va a jugar un partido y se elige antes un capitán $k^2$ .

Answer 1

He visto exactamente el mismo problema antes en un examen. Usted sabe que

$$(1+x)^{n}=\sum\limits_{k=0}^{n}\binom{n}{k}x^k$$

Diferencia ambos lados dos veces, reordena un poco, deja x=1 y todo debería encajar.

Answer 2

Ambos lados de la identidad responden a la pregunta: "Dado $n$ miembros candidatos, ¿cuántas formas hay de formar un comité con un presidente y un tesorero, si se permite que la misma persona desempeñe ambas funciones?"

Para el lado derecho, se elige $k$ miembros, y luego elige a uno de ellos como presidente y a otro como tesorero. De este modo se obtiene inmediatamente la suma de la derecha.

Para la parte izquierda, se elige un presidente y un tesorero de entre toda la lista de candidatos, y luego se selecciona el resto del comité. Hay dos maneras de hacerlo:

• Elija una persona para ser presidente y tesorero (en $n$ posibles formas). Luego, para cada uno de los otros $n-1$ miembros candidatos, decidir si están en el comité o no (en $2^{n-1}$ posibles formas). Hay un total de $n2^{n-1}$ formas de hacerlo.
• Elija un presidente (en $n$ posibles), un tesorero distinto del presidente (en $n-1$ posibles) y decidir si cada una de las otras $n-2$ candidatos está en el comité (en $2^{n-2}$ posibles formas). Hay un total de $n(n-1)2^{n-2}$ formas de hacerlo.

Así que hay un total de $n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}$ formas de elegir, lo que completa la prueba.

Answer 3

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

Answer 4

Lo siguiente es casi combinatoria (biyectiva). Se puede convertir en totalmente biyectiva.

Estamos entregando medallas a algunas personas de un grupo de $n$ , $1$ oro, $1$ de plata, el resto de plástico. Regla curiosa: la misma persona puede recibir el oro y la plata, los plásticos preciosos son como máximo uno por persona.

El lado derecho cuenta el número de formas de hacerlo.

Afirmamos que el lado izquierdo cuenta lo mismo de una manera diferente. Podemos elegir diferentes personas para obtener el oro y la plata, y del resto $n-2$ personas, elige un subconjunto, posiblemente vacío, para obtener el plástico. O podemos elegir una sola persona para obtener el oro, y un subconjunto de los restantes $n-1$ para conseguir el plástico. Por lo tanto, el número de formas es $n(n-1)2^{n-2}+n2^{n-1}$ . Un poco álgebra muestra que esto es $n(n+1)2^{n-2}$ .

Observación: Se puede inventar una historia para sustituir el paso del álgebra por un paso biyectivo.

Answer 5

El número de equipos de tamaño arbitrario (no vacíos) que puedes formar de $n$ personas y declarar un capitán y un recaudador de fondos (ambos pueden ser la misma persona) entre ellos en $\sum_{k=1}^{n}k^2\dbinom{n}{k}$ .

De nuevo puedes realizar la misma tarea eligiendo al capitán y al recaudador de fondos entre $n$ personas más $1$ maniquí en $n+1 \choose 2$ manera y elegir el equipo restante en $2^{n-1}$ formas.

Por lo tanto, $\sum_{k=1}^{n}k^2\dbinom{n}{k}= {n+1 \choose 2}2^{n-1}$ .