Prueba combinatoria que involucran suma de factoriales

Question

Necesito ayuda con esta prueba combinatoria: $1\cdot1!+2\cdot2!+\cdots+n\cdot n!=(n+1)!-1$ hasta el momento se me ocurrió esto: S que ser un conjunto de números $1, 2, \ldots, n+1$ tan LHS podría ser: cuántas permutaciones de longitud $k$ hay en conjunto $S$ tal que número $1$ es no la primera permutación. $k$ puede ser $2, 3,\ldots, n+1$. Pero el lado derecho me da problemas... Gracias. (Lo siento por la pobre formateo, no soy bueno con HTML)

Answer 1

$n\cdot n!$ cuenta el número de maneras de orden ${1,2,3,\ldots,n+1}$ sin $n+1$ ser el primero.

$(n-1)\cdot (n-1)!$ cuenta el número de maneras de orden ${1,2,3,\ldots,n+1}$ $n+1$ ser primero y $n$ no segundo.

$(n-2)\cdot (n-2)!$ cuenta el número de maneras para segundo ${1,2,3,\ldots,n+1}$ $n+1$ ser el primero y $n$ y $n-1$ no tercero.

Etcetera...

El lado derecho es todas las formas de orden ${1,2,3,\ldots,n+1}$ sin todos los elementos en la descendente la orden.

Answer 2

Queremos mostrar que las permutaciones de $n+1$ elementos, salvo uno de ellos, están en bijective correspondencia con los pares $(j,\tau)$ donde $\tau$ es una permutación de $k\le n$ elementos y $1\le j\le k$, para algunas de las $k$.

He aquí una correspondencia. Empezamos con una permutación $\sigma$$\{1,2,3,\ldots,n+1\}$, por ejemplo

 i        1 2 3 4 5 6 7 8 9 10
sigma(i)  1 6 3 2 7 5 4 8 9 10

Si la permutación es la identidad, entonces no mapa en cualquier lugar! De lo contrario vamos a $k+1$ ser el mayor índice tal que $\sigma(k+1)\ne k+1$. En el ejemplo,$k+1=7$. Tenemos $k\ge 1$ debido a que el índice de $1$ no puede ser la última diferencia entre el$i$$\sigma(i)$.

Deje que la primera salida de $j$ ser el número tal que $\sigma(k+1-j)=k+1$. En otras palabras, $j$ es el número de elementos a la derecha de la $k+1$ en la línea inferior de la permutación, antes de la final de la secuencia de posiciones que no han cambiado. En el ejemplo anterior tenemos $j=2$ debido a que los dos elementos 5 4 entre 7 y la final 8 9 10.

La segunda salida de $\tau$ se define ahora por $\tau(i) = \begin{cases} \sigma(i) & i < j \\ \sigma(i+1) & i \ge j \end{cases}$

 i      1 2 3 4 5 6
tau(i)  1 6 3 2 5 4

Esta correspondencia es bijective-podemos hacerlo a la inversa, comenzando con $(j,\tau)$. Primero anote $\tau$, a continuación, introduzca el número de $k+1$ antes de la $j$th-a-último elemento, y por último añadir los numers $k+2, k+3, \ldots, n+1$ al final de la permutación.

Answer 3

Prueba por inducción obras aquí. Esto no es una prueba combinatoria (¡lo siento!).

$n=1$, La instrucción $1\cdot 1!=2!-1$ es verdad; ambos lados igualan $1$.

Asumir la instrucción $n=k$ es cierto: $$1\cdot 1!+2\cdot 2!+\cdots+k \cdot k!=(k+1)!-1$ $

$n=k+1$, Tenemos\begin{align} 1\cdot 1!+2\cdot 2!+\cdots+(k+1) \cdot (k+1)!&=1\cdot 1!+2\cdot 2!+\cdots+k\cdot k!+(k+1) \cdot (k+1)! \ &=(k+1)!-1+(k+1)\cdot(k+1)! \ &=(k+1)!(1+(k+1))-1 \ &=(k+1)!(k+2)-1 \ &=(k+2)!-1 \end {Alinee el}

Answer 4

sugerencia :$n\cdot n! = (n+1)!-n!$. Puedes continuar?