Stirling Numbers of the Second Kind S(n,k) Calculator

Stirling Numbers of the Second Kind S(n,k) Calculator

Growing AI Skill PRO

Enter Calculation

Formula

S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)nS\!\left(\text{n},\,\text{k}\right) = \frac{1}{\text{k}!}\sum_{j=0}^{\text{k}} (-1)^{j}\binom{\text{k}}{j}\left(\text{k}-j\right)^{\text{n}}
Usage stats

Advertisement

Results

Stirling Number of the Second Kind S(5, 2)
15
ways to partition labeled elements into non-empty subsets (Elements: 5 · Subsets: 2)
n (set size) 5
k (subsets) 2
Notation S(n, k)

Report an error on this page

What is the Stirling Number of the Second Kind?

The Stirling number of the second kind, written \(S(n,k)\), counts the number of ways to partition a set of n distinct (labeled) elements into exactly k non-empty, unlabeled subsets. It is a fundamental quantity in combinatorics and appears in problems involving set partitions, surjections, and the Bell numbers. This is a pure-mathematics tool that works the same way everywhere.

Four labeled balls grouped into two unlabeled bins showing one set partition
S(n,k) counts the ways to split n labeled items into k non-empty unlabeled groups.

How to Use This Calculator

Enter the set size n and the number of subsets k. Both must be non-negative integers. Press calculate to get \(S(n,k)\), the exact count of partitions. If k is greater than n, the result is 0, because you cannot fill more non-empty subsets than there are elements.

The Formula Explained

The explicit form is $$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}\, j^{n}$$ where \(\binom{k}{j}\) is the binomial coefficient. An equivalent and numerically safer way is the recurrence $$S(n,k) = k\, S(n-1,k) + S(n-1,k-1)$$ with base cases \(S(0,0)=1\), \(S(n,0)=0\) for \(n>0\), and \(S(0,k)=0\) for \(k>0\). This calculator uses the recurrence to avoid floating-point cancellation. Useful special cases: \(S(n,1)=1\), \(S(n,n)=1\), and \(S(n,2)=2^{n-1}-1\).

Advertisement

Worked Example

For \(n=5\) and \(k=2\): using the special case $$S(5,2)=2^{5-1}-1=16-1=15$$ The recurrence confirms this: $$S(5,2)=2\cdot S(4,2)+S(4,1)=2\cdot 7+1=15$$ So there are 15 ways to split a 5-element set into two non-empty groups.

Triangular grid of small Stirling number values arranged like Pascal's triangle
A triangle of S(n,k) values, each built from the two entries above it.

Table of Stirling Numbers of the Second Kind S(n,k) for n = 0 to 10

Each entry is the number of ways to partition a set of n labeled elements into exactly k non-empty, unlabeled blocks. The table is built from the recurrence \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\), with \(S(0,0)=1\) and \(S(n,0)=S(0,n)=0\) for \(n\ge 1\). Blank cells are \(k>n\), where S(n,k)=0. The last column is the row sum, which is the Bell number B(n). For example, S(10,4) = 34105.

n \ k 0 1 2 3 4 5 6 7 8 9 10 Row sum B(n)
0 1 1
1 0 1 1
2 0 1 1 2
3 0 1 3 1 5
4 0 1 7 6 1 15
5 0 1 15 25 10 1 52
6 0 1 31 90 65 15 1 203
7 0 1 63 301 350 140 21 1 877
8 0 1 127 966 1701 1050 266 28 1 4140
9 0 1 255 3025 7770 6951 2646 462 36 1 21147
10 0 1 511 9330 34105 42525 22827 5880 750 45 1 115975

Check of one entry with the recurrence: \(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\). Always \(S(n,1)=1\), \(S(n,2)=2^{n-1}-1\), \(S(n,n-1)=\binom{n}{2}\) and \(S(n,n)=1\).

Advertisement

Key Terms and Notation

Set partition
A way of splitting a set into non-empty, pairwise disjoint subsets (blocks) whose union is the whole set. Order of blocks and order within a block do not matter.
Labeled vs. unlabeled
The n elements are labeled (distinguishable, e.g. 1, 2, …, n). The k subsets are unlabeled: swapping two blocks gives the same partition. If the blocks were labeled, the count would be k!·S(n,k) instead.
Non-empty block
Every one of the k subsets must contain at least one element. This is why S(n,0)=0 for n ≥ 1 and S(n,k)=0 when k > n.
Notation S(n,k)
The Stirling number of the second kind, also written \(\left\{ n \atop k \right\}\). It is computed by \(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\).
Bell number B(n)
The total number of partitions of an n-element set into any number of blocks: \(B(n)=\sum_{k=0}^{n}S(n,k)\). The first values are 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975.
Binomial coefficient
\(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\), the number of ways to choose j items from k. It appears in the inclusion–exclusion formula above.
Surjection
A function from an n-set onto a k-set in which every element of the k-set is hit at least once. The number of such functions is \(k!\cdot S(n,k)\): partition the domain into k blocks, then assign the blocks to the k targets in k! ways.

Second kind vs. first kind. Stirling numbers of the second kind count partitions of a set into k blocks. Stirling numbers of the first kind, written \(c(n,k)\) or \(\left[ n \atop k \right]\) (unsigned), count permutations of n elements with exactly k cycles. They obey a different recurrence, \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\), and are related to the second kind by being inverse matrices of each other (with signs).

FAQ

Why is \(S(0,0)=1\)? By convention, the empty set has exactly one partition into zero parts: the empty partition.

What happens when \(k > n\)? The result is 0, since every subset must be non-empty and you have too few elements.

How does this relate to Bell numbers? Summing \(S(n,k)\) over all k from 0 to n gives the Bell number \(B(n)\), the total number of partitions of an n-element set.

Last updated:

Most popular in Math and Statistics

View all Math and Statistics calculators