Finding Stirling Numbers of the second kind with Synthetic Division

Horner's method of synthetic division provides an efficient means of performing polynomial division. It is especially simple when dividing by a linear term of the form $x-k$.

A Stirling number of the second kind (or a Stirling partition number), denoted $S(n,k)$, is the number of ways to partition a set of $n$ objects into $k$ non-empty subsets. Here we compute Stirling numbers of the second kind by sucessively dividing a power of $x$ by linear polynomials $x-1$, $x-2$, etc. This division is done via Horner's method.

Why does this work? Stirling numbers of the second kind are known to obey the following formula: $$x^{n-1} = S(n,1) + S(n,2)(x-1) + S(n,3)(x-1)(x-2) + \cdots + S(n,n)(x-1)(x-2)\cdots (x-n+1)$$ When we divide $x^{n-1}$ by $x-1$ we get $x^{n-1} = q_1(x)(x-1)+r_1$ where the remainder $r_1$ is a constant and, given the above formula, $r_1=S(1,n)$. Notice that $x^{n-1} = S(n,1) + (x-1)\left(S(n,2)+S(n,3)(x-2)+\cdots+S(n,n)(x-2)\cdots(x-n+1)\right)$. So $$q_1(x)=S(n,2)+S(n,3)(x-2)+S(n,4)(x-2)(x-3)+\cdots+S(n,n)(x-2)\cdots(x-n+1)$$ If we divide $q_1(x)$ by $x-2$, we get $q_1(x) = q_2(x)(x-2)+r_2$ where the remainder $r_2$ is a constant and, again considering our above formulas, $r_2=S(n,2)$. Continuing in this fashion will give us all of the desired Stirling numbers.

How is the table created?

• List the coefficients of $x^{n-1}$ along the top row (i.e., $1,0,\dots,0$). We call this row 0-B.
• Draw a vertical line to the left of the list of coefficients.
• We now create rows two at a time. I will refer to these as rows $k$-A and $k$-B (and I will refer to the previously completed row as row $(k-1)$-B). (So we start by creating rows 1-A and 1-B.)
• In row $k$-A to the left of the vertical line write $k$ since we are dividing by $x-k$. Then to the right of the vertical line draw an arrow pointing down.
• To the right of the vertical line, in row $k$-B, write a 1 (i.e., $(x^{n-1})$'s leading coefficient).
• Multiply the last completed entry in row $k$-B by $k$ and place this entry in row $k$-A (this is will be up and to the right of the entry we just multiplied).
• Sum the latest entry in row $k$-A with the entry in row $(k-1)$-B just above it. Place the result below these entries in row $k$-B.
• We repeat this process across the entire row.
• Draw a line between rows $k$-A and $k$-B. In row $k$-B color all but the last entry red (these are the coefficients of our current quotient polynomial). Color the last entry blue (this is our Stirling number).
• Repeat this process creating two rows at a time, but only compute up to the last red entry. So each time we create a new pair of rows, they shrink in length by one entry.

The computation above is powered by SageMath. The Sage code is embedded in this webpage's html file. To view the code instruct your browser to show you this page's source. For example, in Chrome, right-click and choose "View page source".

• Wikipedia entry for Horner's method.
• Stirling Numbers of the second kind