Problem - 4772
Derive the permutation formula $P_n^n=n\times (n-1)\times\cdots\times 2\times 1$ using the recursion method.
Let $P(n)$ be the number of permutations of lining up $n$ people. To line up $n$ people, we perform the next two steps:
- Line up the first $(n-1)$ people. There are $P(n-1)$ ways
- For the $n^{th}$ person, he has $n$ place to choose from: before / after the line and all the intervals in between.
Hence, by the multiplication principle, we have $P(n) = n P(n-1)$. Clearly, we have $P(1)=1$. Therefore, solving this recursion gives $P(n)=n!$.