Combinatoria prueba a $n! = (n-1)[(n-1)! + (n-2)!]$

Question

Es seguro, cierto que $n! = (n-1)[(n-1)! + (n-2)!]$

Desde:

$(n-1)(n-1)! + (n-1)(n-2)! = $

$(n-1)(n-1)! + (n-1)! =$

$ (n-1)!(n-1+1) = (n-1)!n = n! $

Hoy mi amigo me dijo que hay un brillante combinatoria prueba para esta ecuación. ($n! = (n-1)[(n-1)! + (n-2)!]$) Para un par de horas que he estado pensando en ello. Sin embargo, no pude encontrar una manera. Podría usted por favor, muéstrame cómo está demostrado combinatoria?

Saludos

Answer 1

$n!$ es igual a la cantidad de n palabras con letras(por una palabra me refiero a la serie de distintas $A_i$ poner de lado a lado), que pueden estar formados de los alfabetos del conjunto $S=\{A_1,A_2,A_3,\dots,A_n\}$.

Ahora tome el conjunto $S_1=\{A_3,A_4,A_5,\dots,A_n\}$. No. de las palabras que pueden formarse con $A_i\in S_1$$(n-2)!$.

Ahora tomar cualquier palabra(decir $\lambda$) que consta de las cartas de $S_1$ . Este se puede convertir en un n letterd palabra compuesta de las letras de $S$ mediante la inserción de $A_1,A_2$ entre las letras(así como antes de la palabra o después de la palabra) de la palabra $\lambda $. Como hay $(n-2)$ letras así que hay $(n-3)$ lugares dentro de la palabra y hay dos lugares, es decir, antes de la palabra y después de la palabra donde las dos cartas puede ser insertado .

Caso 1: $A_1,A_2$ están en el lado de $A_1$ aparece antes de $A_2$.

En este caso el as $A_1,A_2$ ocuur de lado a lado con el fin restante de la misma a fin de encontrar el número de palabras posible, a partir de una palabra dada $\lambda$ equivale a encontrar el no. de los lugares donde $A_1A_2$ puede ser colocado. Ay como no. de los lugares es $(n-1)$. Por lo que esto implica que $(n-1)$ n de letras de la palabra puede ser obtenido a partir de cada una de las $\lambda$ . Ahora tenemos $(n-2)!$ $\lambda$ s .Esto implica que vamos a tener $(n-1)(n-2)!$ n palabras con letras donde $A_1,A_2$ están en el lado de $A_1$ aparece antes de $A_2$

caso 2: $A_1,A_2$ es de lado a lado con $A_2$ ocurren antes de $A_1$ o que no son de lado a lado .

En este caso vamos a colocar en primer lugar $A_2$ en cualquiera de las $n-1$ lugares. A continuación, vamos a poner a $A_1$ nuevo en cualquiera de las $n-1$ lugares . Cuando vamos a poner $A_1$ el lugar donde: $A_2$ es todavia sentado vamos a poner después de $A_2$ a fin de no violar la condición. Por lo tanto, en este caso, para cada una de las $\lambda $ tenemos $(n-1)^2$ nuevas palabras. Lo que implica que tendremos $(n-1)^2(n-2)!$ palabras en este caso.

El caso 1,caso 2 agota todos los casos posibles de formación de $n$ letras de la palabra y de los casos son distintos

$\Rightarrow (n-1)^2(n-2)!+(n-1)(n-2)!=(n-1)[(n-1)!+(n-2)!]=n!$

Answer 2

La siguiente no es especialmente bonita, pero es una combinatoria de la prueba de la identidad. De curso $n!$ cuenta las permutaciones de $[n]=\{1,\dots,n\}$. Deje $\pi$ ser una permutación. Si $n$ no es el último elemento de $\pi$, vamos a $k$ ser el número inmediatamente después de$n$$\pi$, y si $n$ es el último elemento de $\pi$, vamos a $k$ ser el número inmediatamente antes de $n$. En cada caso hay $n-1$ posibles valores de $k$. En el primer caso $\pi$ ha sido obtenida mediante la inserción de $n$ en una permutación de $[n-1]$, colocándolo justo antes de $k$, y $(n-1)!$ tales permutaciones. En el segundo caso $\pi$ se ha obtenido añadiendo $kn$ a cualquier permutación de $[n-1]\setminus\{k\}$, y $(n-2)!$ tales permutaciones. Por lo tanto, $$n!=(n-1)\Big((n-1)!+(n-2)!\Big)\;.$$

Answer 3

Imagina que tienes dos tipos de listas de $L_1,L_2$ donde $L_1$ es una permutación de $\{1,2,..,n-2\}$ $L_2$ es una permutación de $\{1,2,...,n-1\}.$ Estos son distintos conjuntos de listas, y queremos mapa de su unión en el conjunto de las permutaciones de $\{1,2,...,n\}$ $1$ $n-1$la moda.

Ahora para obtener una lista de tipo $L_1$ convertimos a una permutación de $L=\{1,2,...,n\}$ mediante la colocación de $n$ primero, y luego la colocación de $n-1$ en una de las $n-1$ espacios entre los términos de $L_1.$, Y para una lista de tipo $L_2$ convertimos a una permutación de la misma $L$ mediante la colocación de $n$ en cualquiera de las $n-1$ espacios de $L_2$ que son no más a la izquierda del espacio abierto. Esto le da a la correspondencia, ya que las listas de tipo $L_1$ son enviados a las permutaciones en $L$ que comienzan con $n$, mientras que las listas de tipo $L_2$ son enviados a las permutaciones en $L$ que no comienzan con $n$.

Answer 4

El uso de este hecho :

$ n-k \choose k$+ $ n-k \choose k-1$=$ n \choose k$

$ n-1 \choose 0$+$ n-1 \choose 1$=$ n \choose 1$

$1 +$ $\dfrac{(n-1)!}{(n-2)!}=n$

Multiplicar la expresión por $(n-1)!$

Usted obtiene la necesaria expresión:

$n! = (n-1)\big[(n-1)! + (n-2)!\big]$

Se puede decir que en esta forma:

Número de maneras de seleccionar los $1$ o $0$ $(n-1)$ objetos es igual a la selección de $1$ $n$ objetos.