# Stirling numbers of the first kind

## Introduction.

The Stirling numbers of the first kind, frequently denoted as

$$s(n,k)=\left[\genfrac{}{}{0pt}{}{n}{k}\right],k,n\in \mathbb{N},1\le k\le n,$$ |

are the integer
coefficients of the falling factorial^{} polynomials. To be more precise,
the defining relation for the Stirling numbers of the first kind is:

$${x}^{\underset{\xaf}{n}}=x(x-1)(x-2)\mathrm{\dots}(x-n+1)=\sum _{k=1}^{n}s(n,k){x}^{k}.$$ |

Here is the table of some initial values.

$n\backslash k$ | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|

1 | 1 | ||||

2 | -1 | 1 | |||

3 | 2 | -3 | 1 | ||

4 | -6 | 11 | -6 | 1 | |

5 | 24 | -50 | 35 | -10 | 1 |

## Recurrence Relation.

The evident observation that

$${x}^{\underset{\xaf}{n+1}}=x{x}^{\underset{\xaf}{n}}-n{x}^{\underset{\xaf}{n}}.$$ |

leads to the following equivalent^{} characterization of the $s(n,k)$, in
terms of a 2-place
recurrence formula:

$$ |

subject to the following initial conditions:

$$s(n,0)=0,s(1,1)=1.$$ |

## Generating Function.

There is also a strong connection with the generalized binomial
formula, which furnishes us with the following generating function^{}:

$${(1+t)}^{x}=\sum _{n=0}^{\mathrm{\infty}}\sum _{k=1}^{n}s(n,k){x}^{k}\frac{{t}^{n}}{n!}.$$ |

This generating function implies a number of identities^{}.
Taking the derivative of both sides with respect to $t$ and equating
powers, leads to the recurrence relation described above.
Taking the derivative of both sides with respect to $x$ gives

$$(k+1)s(n,k+1)=\sum _{j=k}^{n}{(-1)}^{n-j}(n-j)!\left(\genfrac{}{}{0pt}{}{n+1}{j}\right)s(j,k)$$ |

This is because the derivative of the left side of the generating funcion equation with respect to $x$ is

$${(1+t)}^{x}\mathrm{ln}(1+t)={(1+t)}^{x}\sum _{k=1}^{\mathrm{\infty}}{(-1)}^{k-1}\frac{{t}^{k}}{k}.$$ |

The relation^{}

$${(1+t)}^{{x}_{1}}{(1+t)}^{{x}_{2}}={(1+t)}^{{x}_{1}+{x}_{2}}$$ |

yields the following family of summation identities. For any given ${k}_{1},{k}_{2},d\ge 1$ we have

$$\left(\genfrac{}{}{0pt}{}{{k}_{1}+{k}_{2}}{{k}_{1}}\right)s(d+{k}_{1}+{k}_{2},{k}_{1}+{k}_{2})=\sum _{{d}_{1}+{d}_{2}=d}\left(\genfrac{}{}{0pt}{}{d+{k}_{1}+{k}_{2}}{{k}_{1}+{d}_{1}}\right)s({d}_{1}+{k}_{1},{k}_{1})s({d}_{2}+{k}_{2},{k}_{2}).$$ |

## Enumerative interpretation.

The absolute value^{} of the Stirling number of the first kind, $s(n,k)$,
counts the number of permutations^{} of $n$ objects with exactly $k$
orbits (equivalently, with exactly $k$ cycles). For example, $s(4,2)=11$, corresponds to the fact that
the symmetric group^{} on 4 objects has $3$ permutations of the form

$$(**)(**)\mathit{\hspace{1em}}\text{\u2014 2 orbits of size 2 each},$$ |

and $8$ permutations of the form

$$(***)\mathit{\hspace{1em}}\text{\u2014 1 orbit of size 3, and 1 orbit of size 1},$$ |

(see the entry on cycle notation for the meaning of the above expressions.)

Let us prove this. First, we can remark that the unsigned Stirling numbers of the first are characterized by the following recurrence relation:

$$ |

To see why the above recurrence relation matches the count of permutations with $k$ cycles, consider forming a permutation of $n+1$ objects from a permutation of $n$ objects by adding a distinguished object. There are exactly two ways in which this can be accomplished. We could do this by forming a singleton cycle, i.e. leaving the extra object alone. This accounts for the $s(n,k-1)$ term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of $n$ object with $k$ cycles, and label the objects ${a}_{1},\mathrm{\dots},{a}_{n}$, so that the permutation is represented by

$$\underset{k\text{cycles}}{\underset{\u23df}{({a}_{1}\mathrm{\dots}{a}_{{j}_{1}})({a}_{{j}_{1}+1}\mathrm{\dots}{a}_{{j}_{2}})\mathrm{\dots}({a}_{{j}_{k-1}+1}\mathrm{\dots}{a}_{n})}}.$$ |

To form a new permutation of $n+1$ objects and $k$ cycles one must insert the new object into this array. There are, evidently $n$ ways to perform this insertion. This explains the $ns(n,k)$ term of the recurrence relation. Q.E.D.

Title | Stirling numbers of the first kind |
---|---|

Canonical name | StirlingNumbersOfTheFirstKind |

Date of creation | 2013-03-22 12:33:44 |

Last modified on | 2013-03-22 12:33:44 |

Owner | rmilson (146) |

Last modified by | rmilson (146) |

Numerical id | 6 |

Author | rmilson (146) |

Entry type | Definition |

Classification | msc 05A15 |

Synonym | Stirling numbers |

Related topic | StirlingNumbersSecondKind |