# $n^s=(n)_s+f(s)$, what is $f(s)$?

In the following equation, $$n^s=(n)_s+f(s)$$ What is general form for $f(s)$? Understand that, $$(n)_s=n(n-1)(n-2)\cdots(n-[s-1])=\text{ The Falling Factorial }$$

I have experimented with this equation for $s=\{1,2,3,4\}$. Unless my calculations are horribly mangled, the following table arises: $$\begin{array}{c|c} s & f(s)\\ \hline 1 & 0\\ 2 & n\\ 3 & 3n^2-2n\\ 4 & 6n^3-11n^2+6n \end{array}$$

I cannot see any reasonable pattern to these values. There isn't an obvious (to me) reccurence relationship, so that method of solving this seems useless. I would appreciate any help on this; it is a personal curiosity of mine. I'm a freshman in highschool. So, I would appreciate elaboration on any complex or complicated methods.

To be more specific, I would like $f(s)$ defined in the form of a polynomial. This is the particular form I was considering: $$f(s)=c_{s-1}n^{s-1}+c_{s-2}n^{s-2}+\dots+c_{1}n$$

-
Where did $q$ come from? – Thomas Andrews Apr 11 '12 at 18:25
@ThomasAndrews Ah, drat. I checked the Wikipedia definition of the falling factorial and unwittingly wrote $q$ rather than $s$. – 000 Apr 11 '12 at 18:26
@ThomasAndrews, $c_{s-1}\neq 3 \text{ when } s=3$. Also, $c_1=-2 \text{ when } s=3$. – 000 Apr 11 '12 at 18:33
Whoops, got them reversed, $c_{s-1}=\frac{s(s-1)}2$ and $c_2=(s-1)!$. – Thomas Andrews Apr 11 '12 at 18:34
@ThomasAndrews I think you have your indexing backwards - it's $c_1$ that's $(s-1)!$ and $c_{s-1}$ that's $s-1\choose 2$. – Steven Stadnicki Apr 11 '12 at 18:35

What you want are known as the Stirling numbers of the first kind; the unsigned version is generally denoted as $\displaystyle{s\brack i}$, and the cofefficients of your polynomial are given by $\displaystyle{f_s(n) = \sum_{i=0}^{s-1} (-1)^{s-i+1}{s\brack i}}n^i$. Note that I'm writing this as $f_s(n)$ rather than $f(s)$, since the latter suggests that it's a function of $s$ where it's more properly thought of as a sequence of functions indexed by $s$. There are recurrence formulas for the coefficients, but there's no explicit representation of them. For more details, I'd suggest checking out the Wikipedia page as a starting point; both of the book references in that article (Knuth's The Art Of Computer Programming and Knuth, Graham and Patashnik's Concrete Mathematics) are excellent sources for learning more about them.