20
$\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$
25
$\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$
  • $\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$ – Michael Le Barbier Grünewald Nov 7 '18 at 22:41

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.