22
$\begingroup$

Are the numbers appearing as coefficients in the following sequence of polynomials known? Is there a known recurrence relation to compute them?

\begin{align*} (x+y) &= x+y \\ (x+y)(x+2y) &= x^2+3yx+2y^2 \\ (x+y)(x+2y)(x+3y) &= x^3+6yx^2+11y^2x+6y^3 \\ (x+y)(x+2y)(x+3y)(x+4y) &= x^4+10yx^3+35y^2x^2+50y^3x+24y^4 \\ &\text{etc.} \end{align*}

$\endgroup$
4

1 Answer 1

30
$\begingroup$

The On-Line Encyclopedia of Integer Sequences® is a searchable database of many integer sequences, and (as @Kevin also said in a comment) can be a valuable tool to identify a particular sequence. Searching for $$ 1, 1, 1, 3, 2, 1, 6, 11, 6, 1, 10, 35, 50, 24 $$ returns as the top result

A094638 Triangle read by rows: T(n,k) = |s(n,n+1-k)|, where s(n,k) are the signed Stirling numbers of the first kind (1 <= k <= n; in other words, the unsigned Stirling numbers of the first kind in reverse order).

So your numbers are Unsigned Stirling numbers of the first kind ${ n \brack k }$, which can be defined as the coefficients in the expansion $$ \tag{*} x(x+1)(x+2) \cdots (x+n-1) = \sum_{k=0}^n { n \brack k } x^k $$

They satisfy various recurrence relations, such as $$ {n+1 \brack k} = n { n \brack k } + { n \brack k-1 } $$ for $k > 0$, with the initial conditions $$ { 0 \brack 0 } = 1 \, , \quad { n \brack 0 } = { 0 \brack n } = 0 $$ for $n > 0$. For more resources about the Stirling numbers and their relations, see @Michael's comment below.


The precise connection with your polynomial expansion is $$ (x+y)(x+2y) \cdots (x+ny) = \sum_{k=0}^n { n+1 \brack k+1 } x^k y^{n-k} $$ This follows from $(*)$ with $n+1$ instead of $n$ and $\frac xy$ instead of $x$.

$\endgroup$
1
  • $\begingroup$ “The Art of Computer Programming” (vol. 1) by Knuth is a commonly available ressource with a lot of other relations involving these numbers. The classical “Problems and Theorems in Analysis I” by Polya and Szegö contains much less details about these but also could be consulted. $\endgroup$ Commented Nov 7, 2018 at 22:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .