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

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)?

• $a_n=\sum_{k=1}^{n}\binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1\rightarrow a_n=n!$ really doesn't make sense. Moreover, induction proof should work ! – Surb Feb 1 at 12:59
• what doesn't make any sense? this identity is right. you can check it. – proven Feb 1 at 13:03
• Maybe it make sense for you, but not for me ! What does mean $a_n=\sum_{k=1}^{n}\binom{n-1}{k-1}(k-1)!a_{n-k},a_1=1,a_0=1\rightarrow a_n=n!$ ? is it a limit ? – Surb Feb 1 at 13:11
• if n is 0, then a_n is 1. if n is 1, then a_n is 1. if n is natural and greater than 1, it is the formula with the sum. The identity claims, that the general formula of a_n is exactly n! – proven Feb 1 at 13:12
• make sense now? – proven Feb 1 at 13:12

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