StirlingS1

The signed Stirling number of the first kind, relating falling factorials to powers of n.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaStirling numbers of the first kind↗MathWorldStirlingNumberoftheFirstKind↗WikidataQ2657556↗DLMF26.8.i.p1↗FungrimStirlingS1↗Fungrim entry071a94↗18ec99↗OEISA008275↗Wolfram LanguageStirlingS1✓↗

StirlingS1(n, k)the signed Stirling number of the first kind $s(n, k)$.

CombinatoricaFunction[{n, k}, (-1)^(n - k) StirlingFirst[n, k], Listable][n, k]SageMathstirling_number1(n, k)!↗SymPystirling(n, k, kind=1, signed=True)↗mpmathstirling1(n, k)JuliaCombinatorics.stirlings1(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

• Coefficients relating falling factorials to ordinary powers: $(x)_n = \sum_{k} s(n, k)\, x^k$.
• $|s(n, k)|$ counts the permutations of n elements with exactly k cycles.
• $s(n, n) = 1$ and $s(n, 0) = 0$ for $n > 0$, with the boundary case $s(0, 0) = 1$.
• The unsigned values in each row sum to $n!$: $\sum_k |s(n, k)| = n!$
• $s(n, 1) = (-1)^{n-1}(n-1)!$.
• Threads element-wise over a list of $n$, as Wolfram's Listable heads do.

Plot

Examples

2 more kept as data, checked against the oracles

Basic #

live ↗

In$\mathrm{StirlingS1}(5, 2)$Out$-50$

live ↗

In$\mathrm{StirlingS1}(4, 2)$Out$11$

s(n, n) is always 1

live ↗

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

s(n, 0) is 0 for n > 0

live ↗

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

live ↗

In$\mathrm{StirlingS1}(20, 10)$Out$381\,922\,055\,502\,195$

Scope #

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

live ↗

In$\mathrm{StirlingS1}(\bigl\lbrack2, 4, 6\bigr\rbrack, 2)$Out$\bigl\lbrack1, 11, 274\bigr\rbrack$

Exact for large n

live ↗

In$\mathrm{StirlingS1}(50, 2)$Out$2\,724\,619\,372\,591\,264\,761\,651\,711\,494\,187\,624\,530\,726\,005\,154\,239\,846\,809\,600\,000\,000$

Applications #

The number of permutations of 5 elements with exactly 3 cycles is $|s(5, 3)| = 35$

live ↗

In$\mathrm{StirlingS1}(5, 3)$Out$35$

live ↗

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

Properties #

The unsigned values in a row sum to $n!$

live ↗

In$\sum_{k=0}^4\vert\mathrm{StirlingS1}(4, k)\vert=4!$Out$\mathrm{True}$

The signed row sum vanishes for $n \ge 2$

live ↗

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

$s(n, n-1) = -\binom{n}{2}$

live ↗

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

The generating property: $\sum_k s(n, k)\,x^k = x(x-1)\cdots(x-n+1)$

live ↗

In$\sum_{k=0}^4\mathrm{StirlingS1}(4, k)x^{k}=\mathrm{Expand}(x×(x-1)(x-2)(x-3))$Out$\mathrm{True}$

A 100-digit-scale signed value, evaluated numerically

live ↗

In$N(\mathrm{StirlingS1}(100, 11))$Out$-390\,376\,773\,476\,389\,796\,543\,585\,013\,048\,065\,552\,669\,095\,304\,773\,071\,088\,642\,650\,967\,777\,941\,539\,595\,016\,786\,090\,531\,126\,519\,978\,928\,664\,992\,958\,028\,261\,781\,883\,437\,197\,859\,800\,964\,094\,681\,415\,680\,000\,000\,000$

No ways to arrange nothing into one cycle

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

Zero cycles can't hold an element

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

A single fixed point

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

More cycles than elements: $0$

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

Zero cycles can't hold any element, for $n\ge1$

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

Signed: one 2-cycle counts as $-1$

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

Two fixed points, sign $+$

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

Too many cycles

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

No arrangement into zero cycles

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

Two 3-cycles, positive sign since $3-1$ is even

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

Three permutations with one transposition, signed $-$

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

$k>n$ gives $0$

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

Zero for any $n\ge1$

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

$(-1)^{n-1}(n-1)!$ at $k=1$, here $-3!$

live ↗

In$\mathrm{StirlingS1}(4, 1)$Out$-6$

Known value · Wolfram MathematicalFunctionData, StirlingS1

Six transpositions in $S_4$, with sign $-$

live ↗

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

Known value · Wolfram MathematicalFunctionData, StirlingS1

Possible issues #

The empty case $s(0, 0) = 1$ by convention, distinct from $s(n, 0) = 0$ for $n > 0$

live ↗

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

$k > n$ is 0

live ↗

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

Neat examples #

$s(n, 1) = (-1)^{n-1}(n-1)!$, so $s(10, 1) = -9!$

live ↗

In$\mathrm{StirlingS1}(10, 1)$Out$-362\,880$

About

Examples	34
Checked against	Wolfram Language 34 agreeCombinatorica 32 agree2 differSageMath 21 agree8 differ1 unevaluated3 errorSymPy 29 agree1 unevaluated2 errormpmath 29 agree1 errormathlib4 19 agree7 differ4 errorJulia 20 agree7 differ1 unevaluated2 error
Crosswalk	WikipediaMathWorldWikidataDLMFFungrimFungrim entry ×2OEISWolfram LanguageCombinatoricaSageMathSymPympmathJulia

Implementation

mappedwolframpackages/oracle/src/mappings.ts

Signed in Wolfram and compute-engine; Sage's stirling_number1, Combinatorics.jl's stirlings1 and Mathlib's Nat.stirlingFirst are UNSIGNED, so a sign difference here is expected, not a bug. Combinatorics.jl's stirlings1 also needs n as a BigInt past its Int64 lookup table (n > 20).

mappedsagepackages/oracle/src/mappings.ts

Signed in Wolfram and compute-engine; Sage's stirling_number1, Combinatorics.jl's stirlings1 and Mathlib's Nat.stirlingFirst are UNSIGNED, so a sign difference there is expected, not a bug. Combinatorics.jl's stirlings1 also needs n as a BigInt past its Int64 lookup table (n > 20).

mappedjuliapackages/oracle/src/mappings.ts

Signed in Wolfram and compute-engine; Sage's stirling_number1, Combinatorics.jl's stirlings1 and Mathlib's Nat.stirlingFirst are UNSIGNED, so a sign difference here is expected, not a bug. Combinatorics.jl's stirlings1 also needs n as a BigInt past its Int64 lookup table (n > 20).

mappedmathlib4packages/oracle/src/mappings.ts

Signed in Wolfram and compute-engine; Sage's stirling_number1, Combinatorics.jl's stirlings1 and Mathlib's Nat.stirlingFirst are UNSIGNED, so a sign difference here is expected, not a bug. Combinatorics.jl's stirlings1 also needs n as a BigInt past its Int64 lookup table (n > 20).

mappedcombinatoricapackages/oracle/src/mappings.ts

Signed in Wolfram and compute-engine; Combinatorica's StirlingFirst, like Sage's stirling_number1, is UNSIGNED, so the template carries the sign (-1)^(n-k). Combinatorics.jl's stirlings1 and Mathlib's Nat.stirlingFirst are UNSIGNED too, so a sign difference there is expected, not a bug. Combinatorics.jl's stirlings1 also needs n as a BigInt past its Int64 lookup table (n > 20).

mappedsympypackages/oracle/src/mappings.ts

SymPy's stirling defaults to the second kind and unsigned; kind=1, signed=True is the signed first kind, as ours and Wolfram's.

mappedmpmathpackages/oracle/src/mappings.ts

Signed, as ours.

See also: Binomial, Stirling