Dar una combinatoria prueba de la identidad

Question

Dar una combinatoria prueba de la identidad:

$$\sum_{k=1}^n k \binom{n}{k}^2 = {n}\binom{2n-1}{n-1}$$

No estoy exactamente seguro de por dónde empezar. Desde $\binom{n}{k}^2 = \binom{n}{k}\binom{n}{k}$, por lo tanto, la ecuación de arriba dice que vamos a elegir k elementos de n elementos y lo estamos haciendo dos veces donde k empieza en el 0 y va todo el camino a n y añadimos todos ellos. Sin embargo, sobre el lado derecho, no tengo idea de qué decir y cómo encaja en esta situación.

Cualquier ayuda será grately apreciado.

Answer 1

Vamos a no ser $n$ de las niñas y $n$ varones, por lo tanto, $2n$ personas en total, y de estos, usted debe hacer un grupo de $n$ de la gente que contiene al menos una niña, y nombrar a una chica del grupo elegido el "jefe" del grupo.

De cuántas maneras se puede hacer esto?

Una manera de contar esta, es la elección que la cabeza de la chica en $n$ formas y, a continuación, elegir el resto de la gente en el grupo en $\binom{2n-1}{n-1}$ maneras. Así que le da el lado derecho.

Otra forma de hacer esto, es decir,fijar el número de muchachas que usted quiere en su grupo, es decir $k$. Ahora, Elija $k$ de las niñas de su grupo, esto se hace en $\binom nk$ maneras. Excluir $k$ niños $n$ del grupo que se quiere hacer, esto también se hace en $\binom nk$ maneras. Ahora, el grupo de chicas que eligió, junto con los no excluidos los niños, le da a un grupo de $n$ de la gente. Usted puede elegir a un jefe de entre los $k$ de las niñas en $k$ maneras.

Desde arriba se puede hacer para cada $k=1$ $n$(esto sería un grupo que tiene sólo niñas) $\sum_{k=1}^n k\binom nk^2$(primer elegir a las chicas, luego de excluir a los chicos, a continuación, elija la cabeza de la muchacha). Por lo tanto, la igualdad de la siguiente manera.

EDIT: UNA combinatoria de prueba para cualquier identidad es esencialmente un conjunto cuya cardinalidad se puede encontrar en dos formas diferentes, dada la derecha y a la izquierda lados de la parte de la identidad, junto con las explicaciones de estos countings.

Normalmente (y por lo tanto no siempre), una suma que implica una ruptura de los casos. Para cada valor del parámetro toma, se termina el conteo de algún subconjunto del conjunto a la mano (en nuestro caso, la inconexión subconjunto es exactamente aquellos casos donde exactamente $k$ chicas hay en el grupo, para cada una de las $k$), y estos subconjuntos disjuntos y su unión es el conjunto.

Por otro lado, una combinación de $\binom mn$ es indicativo de la "libre" elección, y en el conteo de la cardinalidad de libre elección a menudo juega un papel importante, como ocurrió en nuestro caso.

Habitual de las pruebas consiste en tomar un conjunto : una manera de contar está mirando a la libre elección y ponerlos juntos, y la otra es por la ruptura de los casos y, a continuación, la solución de cada caso, como lo hicimos aquí. Trucos para un conjunto vienen sólo con la práctica, por ejemplo, la introducción de la "cabeza" chica de aquí.

Answer 2

Una mayor elaboración en JMoravitz de la pista (el cual fue publicado como yo estaba escribiendo esto):

• La reescritura de la mano izquierda como $\sum_{k=1}^n \binom{n}{k} \binom{n}{n-k}$
• Piensa en una situación con bolas rojas numeradas $1,\ldots,n$ y azul bolas numeradas $1,\ldots,n$. Pensar en los resultados que la mano derecha se podrían contar, y tratar de categorizar los resultados en $n$ categorías de manera que cada categoría $k=1,\ldots,n$ $k \binom{n}{k} \binom{n}{n-k}$ de los resultados.

El lado derecho se puede interpretar como el número de maneras de seleccionar una bola azul a ser el "especial de la bola" y, a continuación, recoger $n-1$ otras bolas del resto de las $2n-1$.

${}$

Estos escenarios pueden ser clasificados por la cantidad de bolas de color azul (incluyendo la bola especiales) fueron seleccionados, que los rendimientos de la mano izquierda. Es decir, el número de resultados que ha $k$ bolas de color azul es $k \binom{n}{k} \binom{n}{n-k}$, ya que el número de maneras de seleccionar $k$ bolas de color azul y $n-k$ bolas rojas es $\binom{n}{k} \binom{n}{n-k}$, y $k$ formas de seleccionar el "especial de la bola" de la $k$ bolas de color azul.

Answer 3

Consideremos el conjunto a $\{1,2,\dots,2n\}$ y marca uno de sus incluso los elementos. A continuación, elija $n-1$ más de $2n-1$ otros (no marcada) de los elementos en el conjunto. El número de maneras de hacer esto es el lado derecho de la ecuación. Por tanto, se ha escogido $n$ elementos de $2n$, incluyendo al menos una a incluso elemento.

Alternativamente, usted puede optar $n$ elementos de $\{1,2,\dots,2n\}$ que incluyen al menos uno, incluso elemento de la siguiente manera. Para cada una de las $k\in[1,n]$, elija $k$ incluso los elementos y $n-k$ impar de elementos, a continuación, marque uno de los elegidos, incluso los elementos. El número de hacerlo es el lado izquierdo de la ecuación.

Así, ambas partes recuento de los objetos en el mismo conjunto, de modo que sean iguales.

Answer 4

Primero podemos ver que $$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$$

Podemos ver esto fácilmente si estamos trabajando con factoriales. Para la combinatoria prueba de que el lado izquierdo es simplemente la elección de $k$ objetos de $n$ objetos.

Podemos hacer lo mismo en la rhs por primera fijación de una de las $n$ objetos y, a continuación, recoger el resto de la $k-1$ objetos del resto de las $n-1$ objetos. Esto nos da $\binom{n-1}{k-1}$ $ { }$ $k$-las selecciones que contiene nuestro objeto fijo. Desde allí se $n$ objetos conseguimos un total de $n\binom {n-1}{k-1}$ $ { }$ $k$-las selecciones.

Sin embargo, podemos ver que cada una de las $k$-selección será repetido $k$ veces. Esto es debido a que la fijación de cada elemento de una $k$-selección introduce esta $k$-selección. Dividiendo por $k$ nos da $$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$$

Ahora podemos simplificar la expresión a dar:

\begin{align*}\sum_{k=1}^n k \binom{n}{k}^2 &= \sum_{k=1}^n k \binom{n}{k}\binom{n}{n-k} \\ &= \sum_{k=1}^n n \binom{n-1}{k-1}\binom{n}{n-k} \end{align*}

Al eliminar el factor común $n$ simplemente tenemos que demostrar que

$$ \sum_{k=1}^n \binom{n-1}{k-1}\binom{n}{n-k} = \binom{2n-1}{n-1} $$

Es fácil ver que también podemos seleccionar $n-1$ objetos de $2n-1$ objetos de primera elección de $k-1$ objetos desde un fijo $n-1$ objetos, a continuación, seleccionando $n-k$ objetos del resto de las $n $ objetos. Ver Chu–Vandermonde de identidad .