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

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

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)\;.$$

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