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

-
"there's no explicit representation of them" Really? That's depressing. Is there any explanation for this? (I have Concrete Mathematics, but I have not read through it entirely.) – 000 Apr 11 '12 at 18:36
Also, this confirms your validity: en.wikipedia.org/wiki/… As such, I am accepting this answer. Thank you. – 000 Apr 11 '12 at 18:39
@user22144 I should be more careful in my phrasing; there are formulas for finding the numbers. In general, the lack of an explicit formula for this thing is to be expected - it's having an explicit formula that's usually the pleasant surprise! – Steven Stadnicki Apr 11 '12 at 18:40
Ah, I understood what your phrasing meant. I was depressed because of the fact that it's usually elegant and beautiful to find the explicit formula. However, I suppose explicit formulae are much less common than I presumed. (And, for an explicit formula, this is quite terrifying: en.wikipedia.org/wiki/… ) – 000 Apr 11 '12 at 18:43
In this case, I wouldn't be surprised if the lack of explicit formulas of certain kinds is actually related to some rather deep mathematics involving the factorial (and its generalization, the Gamma function), specifically Hölder's theorem that the Gamma function doesn't solve any algebraic differential equation. – Steven Stadnicki Apr 11 '12 at 18:43