Combinatoria prueba para dos identidades

Question

• Existe una combinatoria de prueba para los siguientes dos identidades ?

  • $\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$

  • $\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$

Sé cómo derivar la identites de $(1+x)^n$ , pero estoy en busca de una combinatoria de la prueba ?

Answer 1

Para la identidad de la primera:

$\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$

El lado izquierdo es el número de secuencias de azul y amarillo bolas se puede hacer de tal manera que no son exactamente $x$ bolas de color azul y en la mayoría de las $n$ bolas amarillas.

El lado derecho se crea la misma secuencias mediante la enumeración de todas las secuencias con $x+1$ bolas de color azul y $n$ bolas amarillas y, a continuación, siempre quitando el extremo derecho de la bola azul y todas las bolas amarillas a la derecha de ella.

Answer 2

La segunda identidad, se cuenta el número de conjuntos no vacíos con un distinguido representante; es decir, todos los pares de $(x,S)$ tal que $S \subseteq [n]$$x \in S$.

1. Usted puede elegir un conjunto que consta de $k$ elementos (en $\binom n k$ formas) y escoger el representante en $k$ formas para cada una de las opciones del conjunto.
2. Usted puede elegir el representante de $x \in [n]$ primero y, a continuación, elija los otros miembros del conjunto en $2^{n-1}$ maneras.

Igualando estas dos cuentas, hemos terminado.

Answer 3

Usted está eligiendo $n$ de las personas de $x+n+1$ de las personas que están alineados en una fila. El lado derecho cuenta el número de opciones.

El lado izquierdo cuenta las opciones de otra manera. Para cualquier $k$$0$$n$, seleccione todos los de la primera $n-k$ de las personas (desde la izquierda), entonces no la siguiente, a continuación, elija $k$ de las personas del resto de las $x+n+1-(n-k+1)$, que es del resto de las $x+k$. Hay $\binom{x+k}{k}$ maneras de hacer esto. La suma de los $\binom{x+k}{k}$, con lo que los recuentos de las opciones de $n$ de las personas de la $x+n+1$.