Stirling Numbers of the First Kind

We prove (B) directly by a combinatorial recurrence, then derive (A) from (B) via generating-function bookkeeping, and finally verify uniqueness and the sign pattern. The technique is combinatorial recurrence with a bijective insertion argument, followed by an induction on $n$ to match the algebraic recursion for $x^{\underline n}$.

Step 1: A recurrence for $c(n,k)$. Define $c(n,k)$ for $n\ge 1$, $1\le k\le n$ as the number of permutations of $[n]:=\{1,\dots,n\}$ with exactly $k$ cycles, and set $c(0,0)=1$, $c(n,0)=0$ for $n\ge1$, $c(n,k)=0$ if $k>n$ or $k<0$. We claim that for $n \ge 2$ and $1\le k\le n$,

Proof of $(\ast)$. Consider a permutation $\pi$ of $[n]$ with exactly $k$ cycles, and look at where element $n$ sits.

• Case 1: $n$ is a fixed point, i.e. $\pi$ contains the $1$-cycle $(n)$. Deleting $n$ leaves a permutation of $[n-1]$ with exactly $k-1$ cycles (we removed exactly one cycle, the singleton). This correspondence is a bijection between permutations of $[n]$ with exactly $k$ cycles fixing $n$, and permutations of $[n-1]$ with exactly $k-1$ cycles: given any permutation of $[n-1]$ with $k-1$ cycles, adjoin the fixed point $n$ to get a permutation of $[n]$ with $k$ cycles fixing $n$, and these two maps are mutually inverse. Hence there are exactly $c(n-1,k-1)$ such permutations.

• Case 2: $n$ is not a fixed point. Then in the cycle containing $n$, say $n$ appears as $(\dots\, a \, n \, b \,\dots)$ for some $a$ (the element that maps to $n$) — equivalently, $n$ occupies one of the "slots" immediately following some element $a \in [n-1]$ in the cyclic order. Deleting $n$ from its cycle (and reconnecting $a$ directly to $b$, i.e. replacing $a\to n \to b$ by $a \to b$) yields a permutation $\pi'$ of $[n-1]$ with the same number of cycles $k$, since we only shortened one cycle without splitting or merging it (if the cycle containing $n$ had length $\ge 2$, removing $n$ leaves a cycle of length $\ge 1$, not zero, because $n$ is not the only element of its cycle in this case). Conversely, given any permutation $\pi'$ of $[n-1]$ with $k$ cycles, we may insert $n$ immediately after any of the $n-1$ elements $a \in [n-1]$ (in the cyclic reading of $\pi'$'s cycle structure), producing a permutation of $[n]$ with $k$ cycles in which $n$ is not a fixed point. These two constructions (deletion of $n$; insertion of $n$ after a chosen element) are mutually inverse bijections between {permutations of $[n]$, $k$ cycles, $n$ not fixed} and {permutations of $[n-1]$ with $k$ cycles} $\times$ {choice of $a \in [n-1]$}. Hence there are exactly $(n-1)\, c(n-1,k)$ such permutations.

Since Case 1 and Case 2 partition all permutations of $[n]$ with $k$ cycles, adding gives $(\ast)$. $\blacksquare$ (Step 1)

Step 2: The falling factorial satisfies the same recurrence, via its coefficients. Write $p_n(x) := x^{\underline n}$. Then $p_n(x) = p_{n-1}(x)\,(x-n+1)$ for $n\ge 1$, with $p_0(x)=1$. Suppose inductively that

for some integers $a(n-1,k)$ (with $a(n-1,k)=0$ outside $0\le k\le n-1$). Then

Re-indexing the first sum ($k \to k-1$) and combining coefficients of $x^k$ gives

This is a well-defined recursion determining all $a(n,k)$ from $a(0,0)=1$ (since $p_0(x)=1=x^0$), by induction on $n$; it uniquely determines the integers $a(n,k) = s(n,k)$ appearing in the statement, because the monomials $x^k$ are linearly independent, so the coefficients of any polynomial in the power basis are unique. This proves uniqueness of $s(n,k)$ in (A), and gives an explicit recursive algorithm computing them.

Step 3: Matching signs, $c(n,k) := (-1)^{n-k} s(n,k)$ satisfies $(\ast)$. Substitute $s(n,k) = (-1)^{n-k} c(n,k)$ into $(\ast\ast)$:

Now $(-1)^{(n-1)-(k-1)} = (-1)^{n-k}$ and $(-1)^{(n-1)-k} = -(-1)^{n-k}$. Substituting:

Dividing both sides by $(-1)^{n-k}$ (nonzero) gives exactly

which is $(\ast)$. Since the two sequences $\big(c(n,k)\big)_{\text{combinatorial}}$ from Step 1 and $\big(c(n,k)\big)_{\text{algebraic}} := (-1)^{n-k}s(n,k)$ from Step 2–3 satisfy the same recurrence $(\ast)$ and the same boundary conditions ($c(0,0)=1$; $c(n,0)=0, n\ge1$; $c(n,k)=0$ for $k<0$ or $k>n$ — the algebraic side's boundary conditions follow since $p_0(x)=x^0$ forces $s(0,0)=1$ and $p_n(x)$ has degree exactly $n$ with no constant-in-$x^0$... more precisely $s(n,0)$ is the value of $p_n$ at $x=0$ up to the constant term, and $p_n(0)=0$ for $n\ge1$ since one factor of $x^{\underline n}$ is $x$ itself, forcing $s(n,0)=0$), induction on $n$ shows they agree for all $n,k$. This proves (B), and simultaneously confirms the sign claim $\operatorname{sign}(s(n,k))=(-1)^{n-k}$ in (A) whenever $c(n,k) = |s(n,k)| \neq 0$, since $c(n,k) \ge 0$ always (it's a cardinality) and $s(n,k) = (-1)^{n-k}c(n,k)$.

Step 4: Conclusion. Combining Steps 1–3: the unique integer coefficients $s(n,k)$ of $x^{\underline n}$ in the monomial basis satisfy $s(n,k) = (-1)^{n-k}c(n,k)$ where $c(n,k)$ is exactly the number of permutations of $[n]$ with $k$ cycles. This establishes both (A) and (B), and their equivalence. $\blacksquare$

By Theorem (B), $c(n,k)$ counts permutations of $[n]$ with exactly $k$ cycles. Every permutation has a well-defined number of cycles between $1$ and $n$ (a permutation of a nonempty finite set always decomposes into at least one and at most $n$ disjoint cycles, since the cycle decomposition partitions $[n]$ into nonempty blocks each of which is a single cycle). Summing the count over all possible values of $k$ therefore counts every permutation of $[n]$ exactly once, giving $\sum_k c(n,k) = |S_n| = n!$. Equivalently, algebraically, setting $x=1$ in $x^{\underline n} = \sum_k s(n,k)x^k$ and using $s(n,k)=(-1)^{n-k}c(n,k)$ gives $1^{\underline n} = 1\cdot 0 \cdot(-1)\cdots$ which is $0$ for $n \ge 2$ — so instead evaluate the unsigned version at $x=1$: from the rising factorial identity $x^{\overline n} = \sum_k c(n,k) x^k$ (proved in the theorem below), setting $x=1$ gives $1^{\overline n} = n! = \sum_k c(n,k)$, matching the combinatorial count. $\blacksquare$

Part 1: Rising factorial identity (C). Note $x^{\overline n} = (-1)^n (-x)^{\underline n}$, because

By the main theorem applied with $x \mapsto -x$,

Hence

using $(-1)^n(-1)^k = (-1)^{n+k}=(-1)^{n-k}$ and $s(n,k)=(-1)^{n-k}c(n,k) \Rightarrow (-1)^{n-k}s(n,k) = c(n,k)$. This proves (C).

Part 2: Inversion. We use the standard defining property of Stirling numbers of the second kind (established independently, as a prerequisite result): for all $n\ge0$,

This is the analogous expansion of ordinary powers in the falling-factorial basis, proved (elsewhere, as background) by the combinatorial fact that $S(n,k)\cdot k!$ counts surjections from an $n$-set onto a labeled $k$-set, matching the standard basis-change identity — we take (D) as given, since it defines $S(n,k)$ and is not part of what we are proving here. Now substitute the falling factorial expansion from the main theorem, $x^{\underline{k}} = \sum_{j} s(k,j) x^j$, into (D):

Since $\{x^j\}_{j=0}^n$ are linearly independent polynomials, comparing coefficients of $x^j$ on both sides (the left side is $x^n$, i.e. coefficient $1$ at $j=n$ and $0$ elsewhere) yields

In matrix terms, with $B=[S(n,k)]$ and $A=[s(n,k)]$ (both indexed $n,k = 0,\dots,N$, entries $0$ outside $0\le k\le n\le N$), this says exactly $(BA)_{n,j} = \delta_{nj}$, i.e. $BA = I$. Conversely substitute (C) into the falling factorial expansion. From (C) with $x \mapsto -x$ we recovered $x^{\underline n} = \sum_k s(n,k) x^k$ (that is just the definition); instead substitute the defining expansion of $x^{\underline n}$ into (D) the other way: start from

and substitute $x^k = \sum_{j=0}^k S(k,j) x^{\underline j}$ (this is (D) with $n$ renamed to $k$):

The falling factorials $x^{\underline 0}, \dots, x^{\underline n}$ are also linearly independent as polynomials (each has a distinct degree $0,1,\dots,n$, and a nonzero leading coefficient $1$, so any linear dependence among finitely many of them with distinct degrees forces all coefficients to vanish by comparing leading terms degree by degree — a standard fact about polynomial bases graded by degree). Comparing coefficients of $x^{\underline j}$ against the left side $x^{\underline n}$ (coefficient $1$ at $j=n$, else $0$) gives

i.e. $(AB)_{n,j} = \delta_{nj}$, so $AB=I$. Both $AB=I$ and $BA=I$ hold for the truncated $(N+1)\times(N+1)$ triangular matrices, for every $N$; hence $A$ and $B$ are inverse matrices. $\blacksquare$