Stirling Numbers Calculator

Welcome to the Stirling Numbers Calculator, a comprehensive combinatorics tool for computing Stirling numbers of the First Kind (unsigned — permutations into cycles) and the Second Kind (set partitions into non-empty subsets). Featuring interactive triangle visualizations, step-by-step recurrence derivations, bar chart distributions, and deep combinatorial interpretations, this calculator is designed for students, educators, researchers, and competitive programmers who need fast, accurate results with educational context.

What Are Stirling Numbers?

Stirling numbers are two families of numbers that arise naturally in combinatorics, algebra, and analysis. Named after the Scottish mathematician James Stirling (1692–1770), they bridge the gap between factorials, binomial coefficients, and polynomial identities. While they are less well-known than Pascal's triangle, they are equally fundamental and appear throughout discrete mathematics.

Stirling Numbers of the First Kind

The unsigned Stirling numbers of the First Kind, denoted \(|s(n,k)|\) or \(\left[{n \atop k}\right]\), count the number of permutations of \(n\) elements that decompose into exactly \(k\) disjoint cycles.

Intuition: Consider where element \(n\) goes. Either it is inserted into one of the existing cycles (there are \(n-1\) positions to insert it, one before each of the \(n-1\) other elements) — contributing the \((n-1)\cdot|s(n-1,k)|\) term — or it forms its own new 1-cycle, contributing \(|s(n-1,k-1)|\).

Key facts:

• \(|s(n,1)| = (n-1)!\) — circular permutations (one big cycle)
• \(|s(n,n)| = 1\) — the identity permutation (all fixed points)
• \(|s(n,n-1)| = \binom{n}{2}\) — one transposition
• \(\sum_{k=0}^{n} |s(n,k)| = n!\) — total number of permutations

Stirling Numbers of the Second Kind

The Stirling numbers of the Second Kind, denoted \(S(n,k)\) or \(\left\{{n \atop k}\right\}\), count the number of ways to partition a set of \(n\) elements into exactly \(k\) non-empty subsets.

Intuition: Consider where element \(n\) goes. Either it joins one of the \(k\) existing subsets (\(k\) choices) — contributing the \(k \cdot S(n-1,k)\) term — or it forms its own new singleton subset, contributing \(S(n-1,k-1)\).

Key facts:

• \(S(n,1) = 1\) — only one way: all elements in one set
• \(S(n,n) = 1\) — only one way: every element is a singleton
• \(S(n,2) = 2^{n-1} - 1\) — ways to split into two non-empty subsets
• \(S(n,n-1) = \binom{n}{2}\) — choose which pair shares a subset
• \(\sum_{k=0}^{n} S(n,k) = B(n)\) — the \(n\)-th Bell number

Explicit Formula (Second Kind)

How to Use This Calculator

1. Enter n: The total number of elements (0 to 200).
2. Enter k: The number of cycles (First Kind) or subsets (Second Kind), with 0 ≤ k ≤ n.
3. Select the kind: Choose First Kind, Second Kind, or both for a side-by-side comparison.
4. Calculate: Click "Calculate Stirling Numbers" to see results with step-by-step derivation, triangle visualization, and distribution chart.

Comparison: First Kind vs Second Kind

Applications of Stirling Numbers

Polynomial Conversion

Stirling numbers connect different polynomial bases:

• Rising factorial: \(x^{(n)} = \sum_{k} |s(n,k)|\, x^k\)
• Ordinary power: \(x^n = \sum_{k} S(n,k)\, x^{\underline{k}}\) (falling factorial)

Probability and Statistics

Stirling numbers appear in computing moments of probability distributions, particularly when converting between ordinary and factorial moments. They are essential in the analysis of random permutations and occupancy problems.

Computer Science

In algorithm analysis, Stirling numbers appear in counting the number of ways to distribute objects into containers, hash table analysis, and the study of random permutations. The Second Kind relates directly to surjective function counting: the number of onto functions from an n-set to a k-set is \(k!\, S(n,k)\).

Number Theory

Stirling numbers connect to Bernoulli numbers, harmonic numbers, and various summation identities. They appear in finite difference calculus and in the Euler-Maclaurin formula.

Frequently Asked Questions

What are Stirling numbers of the First Kind?

Unsigned Stirling numbers of the First Kind, denoted |s(n,k)|, count the number of permutations of n elements that decompose into exactly k disjoint cycles. They satisfy the recurrence |s(n,k)| = (n−1)·|s(n−1,k)| + |s(n−1,k−1)| with |s(0,0)| = 1. The row sums give n! since every permutation has some number of cycles.

What are Stirling numbers of the Second Kind?

Stirling numbers of the Second Kind, denoted S(n,k), count the number of ways to partition a set of n elements into exactly k non-empty subsets. They satisfy the recurrence S(n,k) = k·S(n−1,k) + S(n−1,k−1) with S(0,0) = 1. The row sums give Bell numbers B(n).

What is the difference between First Kind and Second Kind Stirling numbers?

First Kind (unsigned) counts permutations with k cycles — order within each cycle matters. Second Kind counts set partitions into k subsets — order within subsets does not matter. They are related through matrix inversion: the triangle of signed First Kind numbers is the inverse of the Second Kind triangle.

How are Stirling numbers used in mathematics?

Stirling numbers appear in polynomial conversion between falling/rising factorials and ordinary powers, in computing moments of probability distributions, in combinatorial identities, in number theory, and in the analysis of algorithms.

What is the relationship between Stirling numbers and Bell numbers?

The n-th Bell number B(n) equals the sum of all Stirling numbers of the Second Kind in row n: B(n) = Σ S(n,k) for k = 0 to n. Bell numbers count the total number of partitions of a set of n elements into any number of non-empty subsets.

Is there an explicit formula for Stirling numbers?

Yes, the Second Kind has an explicit formula via inclusion-exclusion: S(n,k) = (1/k!) Σ (−1)^(k−j) C(k,j) j^n for j = 0 to k. The First Kind can be computed via the recurrence or through the connection with rising factorials.

Additional Resources

• Stirling Numbers of the First Kind - Wikipedia
• Stirling Numbers of the Second Kind - Wikipedia