4
$\begingroup$

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 \}$?

Thanks.

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!

  • 0
    @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.2012-01-06

1 Answers 1

3

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.