Subfactorial

The number of derangements of n objects: permutations that leave no element in its original position.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaDerangement↗Subfactorial↗MathWorldSubfactorial↗WikidataQ2361661↗OEISA000166↗Wolfram LanguageSubfactorial✓↗

Subfactorial(n)the number of derangements $D_n$ of n objects.

SageMathsubfactorial(n)SymPysubfactorial(n)Juliaenumeratio_subfactorial(n)

Typed signatures

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

Domain: Combinatorics

Details

• Closed form $D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$, so $D_n$ is n! divided by e and rounded to the nearest integer.
• Recurrence: $D_n = n\,D_{n-1} + (-1)^n$, with $D_0 = 1$.
• Also satisfies the two-term recurrence $D_{n+1} = n\,(D_n + D_{n-1})$.
• The classic hat-check problem: $D_n$ counts the ways n people can have their hats returned so nobody gets their own.
• compute-engine leaves negative arguments unevaluated rather than extending Subfactorial analytically.
• A real, non-integer n continues as $D_n = \Gamma(n+1, -1)/e$, complex-valued; N(x, d) past a double's digits sums $\Gamma(a) - e^{i\pi a}\sum_{k\ge 0} 1/(k!\,(a+k))$ with $a = n+1$ (DLMF 8.7.1).

Examples

Basic #

live ↗

In$\mathrm{Subfactorial}(0)$Out$1$

A single object can't be deranged

live ↗

In$\mathrm{Subfactorial}(1)$Out$0$

live ↗

In$\mathrm{Subfactorial}(4)$Out$9$

live ↗

In$\mathrm{Subfactorial}(5)$Out$44$

live ↗

In$\mathrm{Subfactorial}(20)$Out$895\,014\,631\,192\,902\,121$

live ↗

In$\mathrm{FullSimplify}(\operatorname{Normal}(\operatorname{Series}(\mathrm{Subfactorial}(x), x, 0, 2)))$Out$\frac{1}{2}\mathrm{Subfactorial}^{\prime\prime}(0)x^2+x\mathrm{Subfactorial}^{\prime}(0)+1$

live ↗

In$\mathrm{FullSimplify}(\operatorname{Normal}(\operatorname{Series}(\mathrm{Subfactorial}(x), x, ∞, 2)))$Out$\operatorname{Series}(\mathrm{Subfactorial}(x), x, ∞, 2)$

Scope #

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

live ↗

In$\mathrm{Subfactorial}(\bigl\lbrack1, 2, 3, 4\bigr\rbrack)$Out$\bigl\lbrack0, 1, 2, 9\bigr\rbrack$

Exact for large n

live ↗

In$\mathrm{Subfactorial}(48)$Out$4\,566\,824\,330\,931\,624\,695\,767\,452\,273\,778\,667\,071\,025\,042\,534\,230\,906\,772\,538\,913$

Real arguments evaluate as $\frac{\Gamma(n+1, -1)}{e}$ (complex off the integers)

live ↗

In$\mathrm{Subfactorial}(4.5)$Out$19.255\,831\,840\,742\,534+0.157\,179\,122\,964\,615\,25i$

Complex arguments evaluate as $\frac{\Gamma(n+1, -1)}{e}$ too

live ↗

In$\mathrm{Subfactorial}(1.6+i)$Out$0.296\,830\,458\,177\,711\,8+0.284\,208\,547\,251\,969\,9i$

Threads over a matrix element-wise

live ↗

In$\mathrm{Subfactorial}(\bigl\lbrack\bigl\lbrack2, 0\bigr\rbrack, \bigl\lbrack0, 2\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack1, 1\bigr\rbrack, \bigl\lbrack1, 1\bigr\rbrack\bigr\rbrack$

Threads over a list; exact derangement counts up to $20$

live ↗

In$\mathrm{Subfactorial}(\bigl\lbrack5, 10, 20\bigr\rbrack)$Out$\bigl\lbrack44, 1\,334\,961, 895\,014\,631\,192\,902\,121\bigr\rbrack$

On a scalar matrix $2I$ the matrix function gives $!2\cdot I$

live ↗

In$\mathrm{MatrixFunction}(\operatorname{\_1}↦\mathrm{Subfactorial}(\operatorname{\_1}), \bigl\lbrack\bigl\lbrack2, 0\bigr\rbrack, \bigl\lbrack0, 2\bigr\rbrack\bigr\rbrack)$Out$\bigl\lbrack\bigl\lbrack1, 0\bigr\rbrack, \bigl\lbrack0, 1\bigr\rbrack\bigr\rbrack$

live ↗

In$N(\mathrm{Subfactorial}(\frac{1}{3}), 50)$Out$0.581\,679\,279\,998\,131\,546\,308\,233\,168\,239\,509\,695\,786\,964\,644\,882\,07+0.438\,504\,127\,935\,786\,850\,035\,306\,159\,942\,752\,654\,110\,750\,012\,538\,63i$

live ↗

In$\mathrm{FullSimplify}(\operatorname{Normal}(\operatorname{Series}(\mathrm{Subfactorial}(x), x, ∞, 1)))$Out$\operatorname{Series}(\mathrm{Subfactorial}(x), x, ∞, 1)$

live ↗

In$\mathrm{FullSimplify}(\operatorname{Normal}(\operatorname{Series}(\mathrm{Subfactorial}(x), x, \mathrm{x0}, 2)))$Out$\frac{1}{2}\mathrm{Subfactorial}^{\prime\prime}(\mathrm{x0})(x-\mathrm{x0})^2+(x-\mathrm{x0})\mathrm{Subfactorial}^{\prime}(\mathrm{x0})+\mathrm{Subfactorial}(\mathrm{x0})$

Applications #

The hat-check problem: the number of ways 6 people can have their hats returned so nobody gets their own

live ↗

In$\mathrm{Subfactorial}(6)$Out$265$

Properties #

Recurrence: $D_n = n D_{n-1} + (-1)^n$

live ↗

In$\mathrm{Subfactorial}(4)=4\mathrm{Subfactorial}(3)+(-1)^4$Out$\mathrm{True}$

$D_n$ is $\frac{n!}{e}$ rounded to the nearest integer

live ↗

In$\mathrm{Subfactorial}(10)=\mathrm{round}(\frac{10!}{e})$Out$\mathrm{True}$

Two-term recurrence: $D_{n+1} = n\,(D_n + D_{n-1})$

live ↗

In$\mathrm{Subfactorial}(6)=5(\mathrm{Subfactorial}(5)+\mathrm{Subfactorial}(4))$Out$\mathrm{True}$

Exponential generating function $\frac{e^{-x}}{1-x}$

live ↗

In$\mathrm{ExponentialGeneratingFunction}(\mathrm{Subfactorial}(n), n, x)$Out$\frac{e^{-x}}{1-x}$

Only the swap is a derangement of two items

live ↗

In$\mathrm{Subfactorial}(2)$Out$1$

Known value · Wolfram MathematicalFunctionData, Subfactorial

Two 3-cycles are the derangements

live ↗

In$\mathrm{Subfactorial}(3)$Out$2$

Known value · Wolfram MathematicalFunctionData, Subfactorial

Possible issues #

A negative argument is left unevaluated

live ↗

In$\mathrm{Subfactorial}(-1)$Out$\mathrm{Subfactorial}(-1)$

Neat examples #

Digit-wise derangement sums spell out the number

live ↗

In$148\,349=\sum\mathrm{Subfactorial}(\bigl\lbrack1, 4, 8, 3, 4, 9\bigr\rbrack)$Out$\mathrm{True}$

About

Examples	26
Checked against	Wolfram Language 24 agree2 unevaluatedSageMath 15 agree2 unevaluated6 errorSymPy 18 agree4 differ2 unevaluatedmpmath 18 agree1 differmathlib4 9 agree7 errorJulia 18 agree1 error
Crosswalk	Wikipedia ×2MathWorldWikidataOEISWolfram LanguageSageMathSymPyJulia

Implementation

mappedsympypackages/oracle/src/mappings.ts

subfactorial(n) is the number of derangements, !n.

mappedmpmathpackages/oracle/src/mappings.ts

Γ(n + 1, −1)/e, Wolfram's closed form.

mappedsagepackages/oracle/src/mappings.ts

mappedjuliapackages/oracle/src/mappings.ts

mappedmathlib4packages/oracle/src/mappings.ts

Derangements.numDerangements, the same a(0) = 1, a(1) = 0 recurrence; natural numbers only, so a negative or non-integer n fails to typecheck rather than taking Wolfram's Gamma closed form.

See also: Factorial