Stirling

The Stirling number of the second kind $S(n, k)$: the number of ways to partition an n-set into k non-empty blocks

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaStirling numbers of the second kind↗MathWorldStirlingNumberoftheSecondKind↗WikidataQ2601117↗DLMF26.8.i.p3↗Fungrim entry9fbe4f↗OEISA008277↗Wolfram LanguageStirlingS2✓↗

Stirling(n, k)the number of partitions of an $n$-set into $k$ blocks

SageMathstirling_number2(n, k)✓↗SymPystirling(n, k)↗mpmathstirling2(n, k)JuliaCombinatorics.stirlings2(big(n), k)

Typed signatures

Type	Package	Applies
(integer, integer) -> integer	compute-engine	always
(integer, integer) -> integer	number-theoryreplaces compute-engine	always

Domain: Combinatorics

Details

• compute-engine spells the second-kind number $\left\{{n\atop k}\right\}$ as $\mathrm{Stirling}$.
• It satisfies the recurrence $S(n, k) = k\,S(n-1, k) + S(n-1, k-1)$
• Summing over $k$ gives the Bell number: $\sum_k S(n, k) = B_n$ (see BellNumber)
• The signed first-kind numbers are StirlingS1

Plot

Examples

3 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{Stirling}(5, 2)$Out$15$

live ↗

In$\mathrm{Stirling}(6, 3)$Out$90$

live ↗

In$\mathrm{Stirling}(20, 10)$Out$5\,917\,584\,964\,655$

Scope #

Exact for large n

live ↗

In$\mathrm{Stirling}(50, 2)$Out$562\,949\,953\,421\,311$

Threads element-wise over a list, as Wolfram's Listable heads do

live ↗

In$\mathrm{Stirling}(\bigl\lbrack2, 4, 6\bigr\rbrack, 2)$Out$\bigl\lbrack1, 7, 31\bigr\rbrack$

Applications #

The ways to split 10 distinct items among 3 identical non-empty boxes

live ↗

In$\mathrm{Stirling}(10, 3)$Out$9\,330$

live ↗

In$\mathrm{Stirling}(n, 1..n)$Out$\mathrm{Map}(\operatorname{\_1}↦\mathrm{Stirling}(n, \operatorname{\_1}), 1..n)$

live ↗

In$\sum_{k=1}^6\mathrm{Stirling}(6, k)f^{\prime}(e^{z})e^{kz}$Out$15f^{(5)}(e^{z})e^{5z}+31f^{\prime\prime}(e^{z})e^{2z}+65f^{(4)}(e^{z})e^{4z}+90f^{\prime\prime\prime}(e^{z})e^{3z}+f^{\prime}(e^{z})e^{z}+f^{(6)}(e^{z})e^{6z}$

Properties #

One block means one partition: $S(n, 1) = 1$

live ↗

In$\mathrm{Stirling}(5, 1)$Out$1$

Singletons only: $S(n, n) = 1$

live ↗

In$\mathrm{Stirling}(5, 5)$Out$1$

Row sums give the Bell numbers

live ↗

In$\sum_{k=0}^4\mathrm{Stirling}(4, k)=\mathrm{BellNumber}(4)$Out$\mathrm{True}$

Two blocks: $S(n, 2) = 2^{n-1} - 1$

live ↗

In$\mathrm{Stirling}(10, 2)=2^9-1$Out$\mathrm{True}$

$S(n, n-1) = \binom{n}{2}$: one block is a pair

live ↗

In$\mathrm{Stirling}(6, 5)=\binom{6}{2}$Out$\mathrm{True}$

Explicit formula $S(n, k) = \frac{1}{k!}\sum_j (-1)^{k-j}\binom{k}{j} j^n$

live ↗

In$\mathrm{Stirling}(6, 3)=\frac{1}{3!}(\sum_{j=0}^3(-1)^{3-j}\binom{3}{j}j^6)$Out$\mathrm{True}$

Orthogonality with StirlingS1: $\sum_k s(n, k)\,S(k, m) = \delta_{nm}$

live ↗

In$\sum_{k=0}^4\mathrm{StirlingS1}(4, k)\mathrm{Stirling}(k, 2)$Out$0$

Enormous Stirling number evaluated numerically

live ↗

In$N(\mathrm{Stirling}(120, 10))$Out$275\,564\,293\,332\,645\,612\,796\,076\,533\,812\,387\,578\,132\,055\,070\,471\,681\,207\,862\,920\,555\,299\,757\,965\,212\,186\,923\,458\,011\,526\,847\,229\,561\,561\,721\,294\,169\,780$

Partitions of 10 elements into 4 blocks

live ↗

In$\mathrm{Stirling}(10, 4)$Out$34\,105$

Nothing to partition into zero blocks, for $n>0$

live ↗

In$\mathrm{Stirling}(1, 0)$Out$0$

Known value · Wolfram MathematicalFunctionData, StirlingS2

One element in one block

live ↗

In$\mathrm{Stirling}(1, 1)$Out$1$

Known value · Wolfram MathematicalFunctionData, StirlingS2

More blocks than elements gives $0$

live ↗

In$\mathrm{Stirling}(1, 2)$Out$0$

Known value · Wolfram MathematicalFunctionData, StirlingS2

Nonempty set cannot fill zero blocks

live ↗

In$\mathrm{Stirling}(2, 0)$Out$0$

Known value · Wolfram MathematicalFunctionData, StirlingS2

One block holding both

live ↗

In$\mathrm{Stirling}(2, 1)$Out$1$

Known value · Wolfram MathematicalFunctionData, StirlingS2

Each element on its own

live ↗

In$\mathrm{Stirling}(2, 2)$Out$1$

Known value · Wolfram MathematicalFunctionData, StirlingS2

Too many blocks

live ↗

In$\mathrm{Stirling}(2, 3)$Out$0$

Known value · Wolfram MathematicalFunctionData, StirlingS2

Zero blocks only fit the empty set

live ↗

In$\mathrm{Stirling}(3, 0)$Out$0$

Known value · Wolfram MathematicalFunctionData, StirlingS2

A single block

live ↗

In$\mathrm{Stirling}(3, 1)$Out$1$

Known value · Wolfram MathematicalFunctionData, StirlingS2

Three ways to pick the lone element

live ↗

In$\mathrm{Stirling}(3, 2)$Out$3$

Known value · Wolfram MathematicalFunctionData, StirlingS2

All singletons

live ↗

In$\mathrm{Stirling}(3, 3)$Out$1$

Known value · Wolfram MathematicalFunctionData, StirlingS2

$k>n$ gives $0$

live ↗

In$\mathrm{Stirling}(3, 4)$Out$0$

Known value · Wolfram MathematicalFunctionData, StirlingS2

Zero for $n\ge1$

live ↗

In$\mathrm{Stirling}(4, 0)$Out$0$

Known value · Wolfram MathematicalFunctionData, StirlingS2

Always $1$ when $k=1$

live ↗

In$\mathrm{Stirling}(4, 1)$Out$1$

Known value · Wolfram MathematicalFunctionData, StirlingS2

$S(n,2)=2^{n-1}-1$

live ↗

In$\mathrm{Stirling}(4, 2)$Out$7$

Known value · Wolfram MathematicalFunctionData, StirlingS2

$S(4,3)=\binom42$, choosing the pair that shares a block

live ↗

In$\mathrm{Stirling}(4, 3)$Out$6$

Known value · Wolfram MathematicalFunctionData, StirlingS2

Possible issues #

The empty set has one partition (into no blocks)

live ↗

In$\mathrm{Stirling}(0, 0)$Out$1$

No blocks for a non-empty set: $S(n, 0) = 0$ for $n > 0$

live ↗

In$\mathrm{Stirling}(5, 0)$Out$0$

$k > n$ is 0

live ↗

In$\mathrm{Stirling}(3, 5)$Out$0$

About

Examples	39
Checked against	Wolfram Language 39 agreeSageMath 33 agree4 errorSymPy 33 agree1 differ3 errormpmath 32 agree1 errormathlib4 31 agree1 differ2 errorJulia 31 agree1 unevaluated1 errorCombinatorica 1 agree
Crosswalk	WikipediaMathWorldWikidataDLMFFungrim entryOEISWolfram LanguageSageMathSymPympmathJulia

Implementation

mappedwolframpackages/oracle/src/mappings.ts

compute-engine's Stirling is the SECOND kind (Wolfram's StirlingS2). Combinatorics.jl's stirlings2 needs n as a BigInt past its Int64 lookup table (n > 20).

mappedsympypackages/oracle/src/mappings.ts

compute-engine's Stirling is the SECOND kind (Wolfram's StirlingS2). Combinatorics.jl's stirlings2 needs n as a BigInt past its Int64 lookup table (n > 20).

mappedsagepackages/oracle/src/mappings.ts

compute-engine's Stirling is the SECOND kind (Wolfram's StirlingS2). Combinatorics.jl's stirlings2 needs n as a BigInt past its Int64 lookup table (n > 20).

mappedjuliapackages/oracle/src/mappings.ts

compute-engine's Stirling is the SECOND kind (Wolfram's StirlingS2). Combinatorics.jl's stirlings2 needs n as a BigInt past its Int64 lookup table (n > 20).

mappedmathlib4packages/oracle/src/mappings.ts

compute-engine's Stirling is the SECOND kind (Wolfram's StirlingS2). Combinatorics.jl's stirlings2 needs n as a BigInt past its Int64 lookup table (n > 20).

mappedmpmathpackages/oracle/src/mappings.ts

The second kind.

See also: StirlingS1, BellNumber, SetPartitions