Polynomial sequence?

[Nick Hobson]

Hi,

What do people think of this sequence: 1, 7, 58, 601, 7656, 116929,  
2092112, 43006401, 999637120, 25933795801, ... ?

The formula is a(n) = (n+1)^n - n!.  Lest that seem completely artificial,  
I should comment on how I stumbled across the sequence!  Fit a polynomial  
f of degree n-1 to the first n nth powers of positive integers.  Then  
f(n+1) = a(n).

For example, the quadratic that fits (1,1), (2,8), and (3,27) is f(n) =  
6n^2-11n+6.  Then f(4) = a(3) = 58.  Of course, it's not necessary to  
actually determine the polynomial f; a(n) can be found by considering  
differences.

Nick