prove that $a_n=\sum_{k=1}^{n}\binom{n-1}{k-1}(k-1)!a_{n-k}\rightarrow a_n=n!$

Question

I try to prove that: Given $a_n=\sum_{k=1}^{n}\binom{n-1}{k-1}(k-1)!a_{n-k},a_0 = a_1 = 1$. Prove that $a_n=n!$ for any natural $n$, by finding a combinatorics problem that fits both. any solution (combinatorial proofs)?

Answer 1

We'll show by induction that $a_n$ is the number of permutations of $n$ elements, and it'll follow from this that $a_n = n!$.

Base: $a_0 = a_1 = 1$ is indeed the number of permutations of 0 and 1 elements respectively.

Assume $a_t$ is the number of permutations of $t$ elements for all $t < l$. Then we'll prove that $a_l$ is the number of permutations of $l$ elements.

Assume we're permuting the numbers from 1 to $n$. First, we can choose any position for the number $1$. If 1 is in position $k$, we need choose the $k-1$ from the remaining $n-1$ numbers to come before it, and we have $(k-1)!$ ways to order them. We're left with $n-k$ numbers that we ween to place after the 1, and we can do that in $(n-k)! = a_{n-k}$ ways (by induction hypothesis). Thus, we have a total of $$\sum_{k=1}^n {n - 1 \choose k - 1}(k-1)!a_{n-k}$$ ways to permute $n$ numbers. By definition, this is $a_n$.