Binomials to polynomial

Using the identity $\,\binom{n}{k+1} = \frac{n-k}{k+1}\,\binom{n}{k}\,$ allows a rewrite reminiscent of Horner's scheme:

$$ \begin{align} P(n) \;=\;\binom{n}{2}+42\binom{n}{3} + 375\binom{n}{4} + 1450\binom{n}{5} + 2940\binom{n}{6} + 3360\binom{n}{7} + 1680\binom{n}{8} \\ = \binom{n}{2} \left(1 + \frac{n-2}{3}\left(42 + \frac{n-3}{4}\left(375+\frac{n-4}{5}\left(1450+ \\ +\frac{n-5}{6}\left(2940+\frac{n-6}{7}\left(3360+\frac{n-7}{8}\,1680\right)\right)\right)\right)\right)\right) \end{align} $$

Working from the innermost parenthesis outwards:

• $3360+\frac{n-7}{8}\,1680 = 210(n+9)$

• $2940+\frac{n-6}{7} \, 210(n+9) = 30 (n^2 + 3 n + 44)$

• $1450+\frac{n-5}{6} \, 30 (n^2 + 3 n + 44) = 5 (n^3 - 2 n^2 + 29 n + 70)$

• $375+\frac{n-4}{5} \, 5 (n^3 - 2 n^2 + 29 n + 70) = n^4 - 6 n^3 + 37 n^2 - 46 n + 95$

• $42 + \frac{n-3}{4} \, \left(n^4 - 6 n^3 + 37 n^2 - 46 n + 95\right) = \frac{1}{4}\left(n^5 - 9 n^4 + 55 n^3 - 157 n^2 + 233 n - 117\right)$

• $1 + \frac{n-2}{3} \, \frac{1}{4}\left(n^5 - 9 n^4 + 55 n^3 - 157 n^2 + 233 n - 117\right) = \frac{1}{12}\left(n^6 - 11 n^5 + 73 n^4 - 267 n^3 + 547 n^2 - 583 n + 246\right)$

The end result matches Alexander's previously posted comment:

$$ P(n) \;=\; \frac{1}{24} n(n-1)\left(n^6 - 11 n^5 + 73 n^4 - 267 n^3 + 547 n^2 - 583 n + 246\right) $$

Here is a proposal to do the calculation in a manageable, not too cumbersome way. Given a polynomial

\begin{align*} \sum_{k=2}^8a_k\binom{n}{k}\tag{1} \end{align*} with $\color{blue}{(a_k)_{2\leq k\leq 8}=(1,42,375,1\,450,2\,940,3\,360,1\,680)}$ we are looking for a representation \begin{align*} \color{blue}{\sum_{k=2}^8a_k\binom{n}{k}=\sum_{j=1}^8 b_j n^j}\tag{2} \end{align*} In (2) we start the right-hand sum with index $j=1$, since $\binom{n}{k}=\frac{1}{k!}n(n-1)\cdots (n-k+1)$ are polynomials which contain a factor $n$ and so the constant term is equal zero.

We recall binomial coefficients can be written using falling factorials \begin{align*} \binom{n}{k}=\frac{n^{\underline{k}}}{k!} \end{align*} and $n^{\underline{k}}$ admits a representation as polynomial in terms of $n^j$ using Stirling numbers of the first kind \begin{align*} n^{\underline{k}}=\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}n^j\tag{3} \end{align*} The identity (3) can be found for instance as formula (6.13) in Concrete Mathematics by Don Knuth et al.

We can write the polynomial (1) using Stirling numbers of the first kind as \begin{align*} \sum_{k=2}^8a_k\binom{n}{k}&=\sum_{k=2}^8\frac{a_k}{k!}n^{\underline{k}}\\ &=\sum_{k=2}^8\frac{a_k}{k!}\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}n^j\\ &=\sum_{j=1}^8\underbrace{\left(\color{blue}{ \sum_{k=j}^{8}\begin{bmatrix}k\\j\end{bmatrix}(-1)^{k-j}\frac{a_k}{k!}}\right)}_{b_j} n^j\tag{4} \end{align*}

We use the representation (4) to determine the coefficients $b_j, 1\leq j\leq 8$.

At first we observe that for each $b_j$ we need the factors $\frac{a_k}{k!}$. It is convenient to calculate them just once beforehand in a table. We obtain \begin{align*} \begin{array}{c|ccccccc} k&2&3&4&5&6&7&8\\ \hline \\ \frac{a_k}{k!}&\frac{1}{2!}&\frac{42}{3!}&\frac{375}{4!}&\frac{1\,450}{5!}&\frac{2\,940}{6!}&\frac{3\,360}{7!}&\frac{1\,680}{8!}\\ \\ \frac{a_k}{k!}&\frac{1}{2}&7&\frac{125}{8}&\frac{145}{12}&\frac{49}{12}&\frac{2}{3}&\frac{1}{24} \end{array} \end{align*} In the last row we have $\frac{a_k}{k!}$ as reduced fraction.

Next we also list the Stirling number of the first kind we need.

The table $\begin{bmatrix}k\\j\end{bmatrix}, 1\leq j\leq k\leq 8$: \begin{align*} \begin{array}{c|rrrrrrrr} k\backslash j&1&2&3&4&5&6&7&8\\ \hline 1&1\\ 2&1&1\\ 3&2&3&1\\ 4&6&11&6&1\\ 5&24&50&35&10&1\\ 6&120&274&225&85&15&1\\ 7&720&1\,764&1\,624&735&175&21&1\\ 8&5\,040&13\,068&13\,132&6\,769&1\,960&322&28&1\\ \end{array} \end{align*}

Now we are well prepared to calculate the $b_j, 1\leq j\leq 8$.

We do the easy parts first and calculate $b_j$ starting with $j=8$. We obtain \begin{align*} \color{blue}{b_8}&=\begin{bmatrix}8\\8\end{bmatrix}\,\frac{a_8}{8!}=1\cdot\frac{1}{24}\color{blue}{=\frac{1}{24}}\\ \color{blue}{b_7}&=\begin{bmatrix}7\\7\end{bmatrix}\,\frac{a_7}{7!}-\begin{bmatrix}8\\7\end{bmatrix}\,\frac{a_8}{8!} =1\cdot\frac{2}{3}-28\cdot\frac{1}{24}\color{blue}{=-\frac{1}{2}}\\ \color{blue}{b_6}&=\begin{bmatrix}6\\6\end{bmatrix}\,\frac{a_6}{6!} -\begin{bmatrix}7\\6\end{bmatrix}\,\frac{a_7}{7!} +\begin{bmatrix}8\\6\end{bmatrix}\,\frac{a_8}{8!}\\ &=1\cdot\frac{49}{12}-21\cdot\frac{2}{3}+322\cdot\frac{1}{24}\color{blue}{=\frac{7}{2}} \end{align*}

We note it becomes somewhat more lengthy each step we perform. We can reduce the writing effort by using a more compact notation. We will use the dot-product notation $\langle (x_j)_{1\leq j\leq n},(y_j)_{1\leq j\leq n}\rangle=\sum_{j=1}^n x_jy_j$.

We obtain \begin{align*} \color{blue}{b_5}&=\left\langle\left(\begin{bmatrix}5+j\\5\end{bmatrix}\right)_{0\leq j\leq 3}, \left((-1)^j\frac{a_{5+j}}{(5+j)!}\right)_{0\leq j\leq 3}\right\rangle\\ &=\left\langle\left(1,15,175,1\,960\right),\left(\frac{145}{12},-\frac{49}{12},\frac{2}{3},-\frac{1}{24}\right)\right\rangle \,\,\color{blue}{=-\frac{85}{6}}\\ \color{blue}{b_4}&=\left\langle\left(\begin{bmatrix}4+j\\4\end{bmatrix}\right)_{0\leq j\leq 4}, \left((-1)^j\frac{a_{4+j}}{(4+j)!}\right)_{0\leq j\leq 4}\right\rangle\\ &=\left\langle\left(1,10,85,735,6\,769\right),\left(\frac{125}{8},-\frac{145}{12},\frac{49}{12},-\frac{2}{3},\frac{1}{24}\right)\right\rangle \,\,\color{blue}{=\frac{407}{12}}\\ \color{blue}{b_3}&=\left\langle\left(\begin{bmatrix}3+j\\3\end{bmatrix}\right)_{0\leq j\leq 5}, \left((-1)^j\frac{a_{3+j}}{(3+j)!}\right)_{0\leq j\leq 5}\right\rangle\\ &=\Bigg\langle\left(1,6,35,225,1\,624,13\,132\right),\\ &\qquad\left(7,-\frac{125}{8},\frac{145}{12},-\frac{49}{12},\frac{2}{3},-\frac{1}{24}\right)\Bigg\rangle \,\,\color{blue}{=-\frac{565}{12}}\\ \color{blue}{b_2}&=\left\langle\left(\begin{bmatrix}2+j\\2\end{bmatrix}\right)_{0\leq j\leq 6}, \left((-1)^j\frac{a_{2+j}}{(2+j)!}\right)_{0\leq j\leq 6}\right\rangle\\ &=\Bigg\langle\left(1,3,11,50,274,1\,764,13\,068\right),\\ &\qquad\left(\frac{1}{2},-7,\frac{125}{8},-\frac{145}{12},\frac{49}{12},-\frac{2}{3},\frac{1}{24}\right)\Bigg\rangle \,\,\color{blue}{=\frac{829}{24}}\\ \color{blue}{b_1}&=\left\langle\left(\begin{bmatrix}1+j\\1\end{bmatrix}\right)_{0\leq j\leq 7}, \left((-1)^j\frac{a_{2+j}}{(2+j)!}\right)_{0\leq j\leq 7}\right\rangle\\ &=\Bigg\langle\left(1,1,2,6,24,120,720,5\,040\right),\\ &\qquad\left(0,-\frac{1}{2},7,-\frac{125}{8},\frac{145}{12},-\frac{49}{12},\frac{2}{3},-\frac{1}{24}\right)\Bigg\rangle \,\,\color{blue}{=-\frac{41}{4}}\\ \end{align*}

Result: Putting all together we can write the polynomial (1) as \begin{align*} \sum_{k=2}^8 a_k\binom{8}{k}& \color{blue}{=\frac{1}{24}n^8-\frac{1}{2}n^7+\frac{7}{2}n^6-\frac{85}{6}n^5+\frac{407}{12}n^4}\\ &\qquad\color{blue}{-\frac{565}{12}n^3+\frac{829}{24}n^2-\frac{41}{4}n} \end{align*}