# What are the coefficients in the expansion of $(x+y)(x+2y) \cdots (x+ny)$?

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*}

• Looks like en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind, see also oeis.org/A094638. Commented Nov 7, 2018 at 14:58
• Pro tip: You can search for any sequence of integers in the On-Line Encyclopedia of Integer Sequences to see if it has a name. Commented Nov 7, 2018 at 16:43
• @Kevin I hadn't realised that OEIS supports such searches! Consider adding your comment as an answer for higher visibility, as it is a good answer to the question in the title. Commented Nov 7, 2018 at 16:52
• Actually that is how I found the answer:) Commented Nov 7, 2018 at 18:21

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$$.

• “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. Commented Nov 7, 2018 at 22:41