Explicit formulas for Stirling numbers of the first kind?

I am solving this problem:

What are the coefficients of particular powers of $$x$$ in polynomial $$x*(x-1)*(x-2)*...*(x-k+1)$$?

I know, how to start, how to get a recurrence relation, but I do not know how to get an explicit formula using just $$n$$ (means power) and $$k$$ (means $$k$$-th falling power).

• This is a question in combinatorics. The algebraic combinatorics topic is different; read its definition. I know this is confusing, because the solution requires a lot of algebra in the "work with equations" sense, but not in the sense that modern math uses the word "algebra." – Mark Fischler Aug 20 at 15:59

The answer, valid for $$k \geq 0$$, will be

$$x^{\underline{k}} = \sum_n\left[\matrix{k\\n}\right](-1)^{k-n}x^n$$

The easiest proof I find starts from the following lemmas about rising powers, both proven by induction: $$\mbox{Lemma 1 : }\forall k \in \Bbb N : x^{\overline{k}} = \sum_n \left[\matrix{k\\n}\right]x^n$$

$$\mbox{Lemma 2 : }\forall k \in \Bbb N : x^{\underline{k}} = (-1)^k (-x)x^{\overline{k}}$$

If we start with Lemma 1 and replace $$x$$ with $$(-x)$$ it becomes $$(-x)^{\overline{k}} = \sum_n \left[\matrix{k\\n}\right](-x)^n \\ (-x)(-x+1)(-x+2)\cdots(-x+k-1) = \sum_n \left[\matrix{k\\n}\right](-1)^n x^n \\ (-1)^k (x)(x-1)(x-2)\cdots(x-k+1) = \sum_n \left[\matrix{k\\n}\right](-1)^n x^n \\ (x)(x-1)(x-2)\cdots(x-k+1) = \sum_n \left[\matrix{k\\n}\right](-1)^{n-k} x^n$$

$$x^{\underline{k}} = \sum_n\left[\matrix{k\\n}\right](-1)^{k-n}x^n$$

I lied, we don't need lemma 2.

To prove lemma 1, note that it is true for $$k=1$$ because $$x^1 = x = \left[ \matrix{1\\1}\right] x^1 = 1\cdot x$$. Then assuming it is true for all $$j < k$$, $$x^{\overline{k-1}} = \sum_n \left[\matrix{k-1\\n}\right]x^n \\ (x+k-1) x^{\overline{k-1}} = (x+k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n \\ x^{\overline{k}} = (k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n + (x)\sum_n \left[\matrix{k-1\\n}\right]x^n \\ x^{\overline{k}} = (k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n + \sum_n \left[\matrix{k-1\\n}\right]x^{n+1} \\ x^{\overline{k}} = (k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n + \sum_m \left[\matrix{k-1\\m-1}\right]x^{m} \\ x^{\overline{k}} = (k-1) \sum_n \left[\matrix{k-1\\n}\right]x^n + \sum_n \left[\matrix{k-1\\n-1}\right]x^{n} \\ x^{\overline{k}} = \sum_n \left((k-1)\left[ \matrix{k-1\\n}\right] + \left[\matrix{k-1\\n-1}\right]\right)x^{n}$$ and since $$\left[\matrix{k\\n}\right] =(k-1) \left[ \matrix{k-1\\n}\right] + \left[\matrix{k-1\\n-1}\right]$$

$$x^{\overline{k}} = \sum_n \left[\matrix{k\\n}\right]x^{n}$$

which establishes induction and proves lemma 1, thus proving the result stated at the start of this answer.

• But I still don't get how to express [k n] (imagine k is written over n) explicitly, not recursively as you used it in your proof. – Barbra Aug 20 at 17:25
• There is no closed form expression for $\left[ \matrix{k\\n}\right]$ analogous to expressing the binomial coefficients as fractions involving three factorials. That should not bother you too much; strictly speaking, you could say there is no closed form expression for $n!$ and it is "only" defined recursively, but the notation $n!$ bothers nobody. – Mark Fischler Aug 20 at 21:40