The sum of premutations
 p(n,0)+p(n,1)+p(n,2)...........p(n,n-1)+p(n,n)


= a(n) = n* a(n-1) + 1

can you solve this recurence relation

---

Request for Question Clarification by livioflores-ga on 12 Aug 2004 19:18 PDT

Do you want a proof if this recurrence relation? or do you want a
solution (in that case what means solution in this context)?

Thank you.

a(n)=e Gamma(n+1,1) with the incomplete Gamma function

equivalently

a(n)= int( exp(-t) (1+t)^n, t=0..infinity)

The proof that this satsifies the recursion follows
from integration by parts (if you need a proof)

Going back to the sum: it may be written  n!*(1/0! + 1/1! + 1/2! + ...
+ 1/n!) if you write the sum in reverse order. As n increases, the sum
in the parentheses approaches a well-known constant. Call it C.

Next, make table with a column for n, for C*n!, and for the sum of
permutations, and fill it in for several values of n>0. Compare the
columns
for C*n! and the permutation sum.

p(n,r) is defined for all values of n and r such that n and r are
non-negative integers and r is less than or equal to n.

Since n is non-negative, a(0)= 0*a(-1)+1 = 1.

The recurring relation is: 

a(n) = n*a(n-1) + 1
     = n(n-1)*a(n-2) + n + 1	
     = n(n-1)(n-2)*a(n-3) + n(n-1) + n + 1
     = n(n-1)(n-2)(n-3)*a(n-4) + n(n-1)(n-2) + n(n-1) + n + 1

.. continuing expansion in the same manner, we reach:

     = [n(n-1)(n-2)(n-3)...*2*1*a(0) + n(n-1)(n-2)(n-3)...*2*1 +
n(n-1)(n-2)(n-3)...*2 + n(n-1)(n-2)(n-3)...3 + ... + n + 1]

Since a(0) = 1, as calculated before, we get:

     = [n(n-1)(n-2)(n-3)...*2*1 + n(n-1)(n-2)(n-3)...*2*1 +
n(n-1)(n-2)(n-3)...*2 + n(n-1)(n-2)(n-3)...3 + ... + n + 1]
     
     = p(n,n) + p(n,n-1) + p(n,n-2) + ... + p(n,n)

Q.E.D.

sorry, the last line should read:
     = p(n,n) + p(n,n-1) + p(n,n-2) + ... + p(n,0)
instead of:
     = p(n,n) + p(n,n-1) + p(n,n-2) + ... + p(n,n)