Prueba combinatoria con factoriales

Question

Mostrar que %#% $ #%

Traté de pensar en lo que el sumando del lado izquierdo podría ser (permutación, combinación), pero no puedo subir con nada; ni yo era capaz de idear una prueba combinatoria.

Answer 1

Permite considerar una bolsa de bolas de $n+1$de % que $m$ blanco y $n-m+1$ negro.

Que $X$ sea una variable aleatoria que cuenta el no. de bolas para sacar la caja con el fin de terminar con una bola negra.

Clarly X toma valor en el conjunto de $1,2,....,m+1 $.

$P(X=1)=\frac{n-m+1}{n+1}$

$P(X=2)=\frac{m}{n+1}\times \frac{n-m+1}{n}$

$P(X=3)=\frac{m}{n+1} \times \frac{m-1}{n}\times \frac{n-m+1}{n-1}$

De esta manera $P(X=k)=\frac{m}{n+1}\times \frac{m-1}{n}.... \times \frac{m-k+2}{n-k+3}\times \frac{n-m+1}{n-k+2}=\frac{n-m+1}{n+1}\times \frac{m!(n-(k-1))!}{n!(m-(k-1))!}$

Como todas las probabilidades deben agregar hasta que $1$

Tenemos $\displaystyle\sum_{k=1}^{m+1}P(X=k)=1$

$\Rightarrow\displaystyle\sum_{k=1}^{m+1}\frac{n-m+1}{n+1}\times \frac{m!(n-(k-1))!}{n!(m-(k-1))!}=1$

$\Rightarrow\displaystyle\sum_{l=0}^{m}\frac{n-m+1}{n+1}\times \frac{m!(n-l)!}{n!(m-l)!}=1$

$\Rightarrow\displaystyle\sum_{l=0}^{m}\frac{m!(n-l)!}{n!(m-l)!}=\frac{n+1}{n-m+1}$

Hemos terminado.

Answer 2

Primero reorganizar la identidad:

$$\sum_{k=0}^m\frac{(n-k)!}{(m-k)!}=\frac{(n+1)!}{m!(n+1-m)}=\binom{n+1}m(n-m)!\;.$$

A continuación, tenga en cuenta que

$$\frac{(n-k)!}{(m-k)!}=(n-k)^{\underline{n-m}}\;,$$

donde $x^{\underline n}$ es la caída de factorial, por lo que la identidad puede ser escrito

$$\sum_{k=0}^m(n-k)^{\underline{n-m}}=\binom{n+1}m(n-m)!\;.\tag{1}$$

El plazo $(n-k)^{\underline{n-m}}$ es el número de formas de elegir y permutar $n-m$ elementos de $[n-k]$ donde $0\le k\le m$. Alternativamente, es el número de maneras de elegir un conjunto de $n-m+1$ elementos de $[n+1]$ cuyo elemento más grande es $n-k+1$ y permutar las otras $n-m$ elementos del conjunto. Por lo tanto, el lado izquierdo de $(1)$ cuenta las formas de elegir los $n-m+1$ elementos de $[n+1]$ y permutar las $n-m$ más pequeño de los elementos elegidos.

Por otro lado, hay $\dbinom{n+1}{n-m+1}=\dbinom{n+1}m$ formas de elegir los $n-m+1$ elementos de $[n+1]$, y, a continuación, $(n-m)!$ formas de permutar las $m-n$ más pequeño de los elementos elegidos, de modo que la parte derecha de $(1)$ cuenta la misma cosa, y la identidad se establece.