Let $f(t) = \sum_{i = 0}^{n} c_i \ t^i$ be a degree $n$ polynomial. In the binomial basis, we can write $f(t) = \sum_{k = 0}^{n} h_k \ \binom{t + n - k}{n}$. Using the calculus of finite differences, I can prove that the coefficient $c_i$ can be computed from $\{ h_0, \dots, h_n \}$ by the equation $$c_i = \frac{1}{n!} \sum_{k = 0}^{n} \left( \sum_{\ell = i}^{n} s(n,\ell) \binom{\ell}{i} (n-k)^{\ell - i} \right) h_k, $$ where $s(n,\ell)$ is the (signed) Stirling Number of the first kind. I'd like to have the inverse formula. That is, how does one compute $h_k$ as a function of $\{ c_0, \dots, c_n \}$?


Update: Thanks to the suggestions below, I can prove \begin{eqnarray} f(t) = \sum_{i = 0}^{n} \sum_{k = 0}^{i} \sum_{j = k}^{i} c_{i} k! \binom{i}{j} r^{i-j} S(j,k) \binom{t - r}{k} \end{eqnarray} for any positive integer $r$. I'm not sure how to convert this into an expansion in the basis $\left \{ \binom{t + n - k}{k} \right\}$ or $\left\{ \binom{t + n -k}{n} \right\}$, since I believe that $r$ cannot depend on $k$. Any ideas are certainly appreciated!

  • 1
    $\begingroup$ Take backward differences and let t = 0. It's essentially the same as computing Taylor series coefficients. $\endgroup$ – Qiaochu Yuan Feb 18 '11 at 16:39
  • $\begingroup$ I haven't had the time to think through this all the way through myself, but I was going to try choosing a different $r$ for each value of $i$ in $\sum_{i=0}^n c_i t^i$. You would need $r$ to range from $0$ to $-n$ to cover all possible values of $t+n-k$. Then maybe you could combine these and reindex to get the basis change you want. $\endgroup$ – Mike Spivey Feb 20 '11 at 14:49
  • $\begingroup$ @Srivatsan, it is great that you tidy up posts and tags, but remember to do this a couple of posts at a time only, as otherwise you get the front page covered with old questions and force the new ones to be bumped off. (Also, while I also cringe a bit when I see things like x_{n}, there is really no point in editing that into x_n—in particular, both forms are correct! $\endgroup$ – Mariano Suárez-Álvarez Jan 6 '12 at 6:32
  • $\begingroup$ @Mariano Oops, sorry about flooding the main page. I got carried away; I'll stop for now. // The reason for the edit was not really x_{n} vs. x_n (that was just a bonus) but to remove the [algebra] tag and replace it by something else. $\endgroup$ – Srivatsan Jan 6 '12 at 6:35

Since $\binom{t+n-k}{k} = \frac{(t+n-k)!}{k! (t+n-2k)!} = \frac{(t+n-k)^{\underline{k}}}{k!}$, your problem reduces to how to find the coefficients $s_0, s_1, \ldots, s_n$ such that $$t^n = \sum_{k=0}^n s_k (t+n-k)^{\underline{k}}.$$

If you had $n-k = 0$, this would involve the Stirling numbers of the second kind $S(n,k)$ via the formula $$t^n = \sum_{k=0}^n S(n,k) t^{\underline{k}}.$$

Instead, what you want are called the non-central Stirling numbers of the second kind. Unfortunately, I can't seem to find a good web reference. Charalambides's Enumerative Combinatorics, pp. 314-319, has a decent discussion, but not all of it appears on Google books.

The relevant formulas are

$$t^n = \sum_{k=0}^n S(n,k;r) (t-r)^{\underline{k}},$$ and $$S(n,k;r) = \sum_{j=k}^n \binom{n}{j} r^{n-j} S(j,k),$$ where $S(j,k)$ is (again) a Stirling number of the second kind. Note that the second equation is dual (as it should be!) to the expression inside the parentheses in your question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.