Stirling Numbers

Stirling Numbers

This concept comes from leetcode 3317.

Stirling numbers are mathematical concepts that come in two types: Stirling numbers of the first kind and Stirling numbers of the second kind. Both are related to combinatorics and partitioning sets.

Stirling numbers of the first kind

S(n,k): These count the number of ways to arrange 𝑛 n objects into 𝑘 k non-empty cycles. They are denoted by

c(n,k)

or

S1(n,k)

A cycle is a permutation where each element is part of a single loop, and all elements are connected.

For example:

S(4,2)=11

meaning there are 11 ways to arrange 4 objects into 2 non-empty cycles.

Stirling numbers of the second kind

S(n,k): These count the number of ways to partition a set of n elements into k non-empty, unlabeled subsets. They are denoted by

S2(n,k)

or

S(n,k)

For example:

S(4,2)=7

meaning there are 7 ways to divide a set of 4 objects into 2 non-empty subsets.

Formula for Stirling numbers of the second kind:

S(n,k) = S(n − 1, k − 1) + k⋅S(n − 1, k)

This recurrence relation shows how you can compute Stirling numbers step by step.

Both types of Stirling numbers are useful in combinatorics, number theory, and algebra, especially in problems involving permutations, partitions, and cycles.