---
tag: 0C5BFX94J9
kind: statement
role: theorem
name: Recurrence for Stirling numbers of the first kind
msc: [11B73]
uses: [0Z22VQH17V]
sources:
  - url: https://en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind
    locator: Recurrence relation
---

## Statement

Let $n$ and $k$ be natural numbers, and let $c(n, k)$ be the unsigned [[Stirling numbers of the first kind|0Z22VQH17V]].
Then
$$c(n + 1, k + 1) = n\, c(n, k + 1) + c(n, k).$$

## Remarks

Proof idea: look at the element $n + 1$ in a permutation of $n + 1$ elements. Either it is a fixed point, and the rest has $k$ cycles. Or it sits right after one of the $n$ other elements in its cycle.
Example: $c(4, 2) = 3\, c(3, 2) + c(3, 1) = 3 \cdot 3 + 2 = 11$.

## Explanations

### L1 human

Insert a new element into a permutation written as cycles.
It forms a new cycle of length $1$, or it goes into an existing cycle right after one of the $n$ old elements.