Combinatorial proof to $n! = (n-1)[(n-1)! + (n-2)!]$

Question

It is for sure true that $n! = (n-1)[(n-1)! + (n-2)!]$

Since:

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

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

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

Today my friend told me that there is a brilliant combinatorial proof for this equation. ($n! = (n-1)[(n-1)! + (n-2)!]$) For a few hours I have been thinking about it. However I could not find a way. Could you please show me how it is proven combinatorially?

Regards

Answer 1

$n!$ is equal to the number of n lettered words(by a word I mean the series of distinct $A_i$ put side by side) that can be formed of the alphabets from the set $S=\{A_1,A_2,A_3,\dots,A_n\}$.

Now take the set $S_1=\{A_3,A_4,A_5,\dots,A_n\}$. No. of words that can be formed with $A_i\in S_1$ is $(n-2)!$.

Now take any word(say $\lambda$) consisting of the letters from $S_1$ . This can be converted into a n letterd word consisting of letters from $S$ by inserting $A_1,A_2$ in between the letters(as well as before the word or after the word) of the word $\lambda $. As there are $(n-2)$ letters so there are $(n-3)$ places within the word and there are two places namely before the word and after the word where the two letters can be inserted .

Case 1: $A_1,A_2$ are side by side with $A_1$ appearing before $A_2$.

In this case the as $A_1,A_2$ will ocuur side by side with the order remaining same so finding the number of possible word from a given word $\lambda$ amounts to finding the no. of places where $A_1A_2$ can be placed. Aand as the no. of places is $(n-1)$. So this implies that $(n-1)$ n lettered word can be obtained from each $\lambda$ . Now we have $(n-2)!$ $\lambda$ s .This implies that we will have $(n-1)(n-2)!$ n lettered words where $A_1,A_2$ are side by side with $A_1$ appearing before $A_2$

case 2:Either $A_1,A_2$ is side by side with $A_2$ occuring before $A_1$ or they are not side by side .

In this case we will first put $A_2$ in any one of the $n-1$ places. Then we will put $A_1$ again in any one of the $n-1$ places . When we will put $A_1$ in the place where $A_2$ is alredy sitting we will put it after $A_2$ so as to not violate the condition. Thus in this case for each $\lambda $ we have $(n-1)^2$ new words. Implying that we will have $(n-1)^2(n-2)!$ words in this case.

Case 1,case 2 exhausts all the possible cases of formation of $n$ lettered word and the cases are disjoint

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

Answer 2

The following isn’t especially nice, but it is a combinatorial proof of the identity. Of course $n!$ counts the permutations of $[n]=\{1,\dots,n\}$. Let $\pi$ be such a permutation. If $n$ is not the last element of $\pi$, let $k$ be the number immediately after $n$ in $\pi$, and if $n$ is the last element of $\pi$, let $k$ be the number immediately before $n$. In each case there are $n-1$ possible values of $k$. In the first case $\pi$ has been obtained by inserting $n$ into a permutation of $[n-1]$, placing it just before $k$, and there are $(n-1)!$ such permutations. In the second case $\pi$ has been obtained by appending $kn$ to any permutation of $[n-1]\setminus\{k\}$, and there are $(n-2)!$ such permutations. Thus, $$n!=(n-1)\Big((n-1)!+(n-2)!\Big)\;.$$

Answer 3

Imagine you have two types of lists $L_1,L_2$ where $L_1$ is a permutation of $\{1,2,..,n-2\}$ and $L_2$ is a permutation of $\{1,2,...,n-1\}.$ These are disjoint sets of lists, and we wish to map their union into the set of permutations of $\{1,2,...,n\}$ in a $1$ to $n-1$ fashion.

Now for a list of type $L_1$ we convert to a permutation of $L=\{1,2,...,n\}$ by placing $n$ first, and then placing $n-1$ in one of the $n-1$ spaces between terms of $L_1.$ And for a list of type $L_2$ we convert to a permutation of the same $L$ by placing $n$ in any of the $n-1$ spaces of $L_2$ which are not the leftmost open space. This gives the correspondence, since lists of type $L_1$ are sent to permutations in $L$ which start with $n$, while lists of type $L_2$ are sent to permutations in $L$ which do not start with $n$.

Answer 4

Using this fact :

$ 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$

Multiply the expression by $(n-1)!$

You get the required expression:

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

You can say that in this way:

Number ways of selecting $1$ or $0$ out of $(n-1)$ objects is equal to selecting $1$ from $n$ objects.