Subfactorial

From Wikipedia, the free encyclopedia

In mathematics, the subfactorial function is a function from the set of natural numbers to itself, whose value at n gives the number of permutations of a sequence of n distinct values in which none of the elements occur in their original place; such permutations are also known as derangements. In the group-theoretic sense of "permutation", it counts permutations without fixed point of an n-element set. This number of permutations is often written as !n. By contrast the factorial function of n, written as n!, gives the total number of permutations of a sequence of n distinct values.

In practical terms, subfactorial is the number of ways in which n persons can each give one present to one other person so that everyone receives a present.

Ths subfactorial function defines sequence A000166 in OEIS.

1 Computing values of the subfactorial function
2 Explicit values
3 Miscellanea
4 References

[edit] Computing values of the subfactorial function

Subfactorials be calculated using the inclusion-exclusion principle.

$!n = n! \sum_{k=0}^n \frac {(-1)^k}{k!}$

Subfactorials can also be calculated in the following ways:

$!n = \frac{\Gamma (n+1, -1)}{e}$

where $Γ$ denotes the incomplete gamma function, and e is the mathematical constant; or

$!n = \left [ \frac {n!}{e} \right ]\qquad\mbox{for }n\geq1$

where [x] denotes the nearest integer function.

$!n = !(n-1)\;n + (-1)^n\qquad\mbox{for }n\geq1$

$!n = (n-1)\;(!(n-1)+!(n-2))\qquad\mbox{for }n\geq2$

$!n = (n-1)\; a_{n-2}\qquad\mbox{for }n\geq2,$

where the sequence (a_n)_n is given by $\;a_0 = a_1 = 1$ and $a_n = n\;a_{n-1} + (n-1)\;a_{n-2}$ ; this is sequence OEIS:A000255

[edit] Explicit values

The first few values of the function are:

!0 = 1

!1 = 0

!2 = 1

!3 = 2

!4 = 9

!5 = 44

!6 = 265

!7 = 1,854

!8 = 14,833

!9 = 133,496

!10 = 1,334,961

!11 = 14,684,570

!12 = 176,214,841

!13 = 2,290,792,932

!14 = 32,071,101,049

!15 = 481,066,515,734

!16 = 7,697,064,251,745

!17 = 130,850,092,279,664

!18 = 2,355,301,661,033,953

!19 = 44,750,731,559,645,106

!20 = 895,014,631,192,902,121

!21 = 18,795,307,255,050,944,540

[edit] Miscellanea

The notation !n is not universally accepted. It gives ambiguity with the notation for the factorial function if there is a factor that precedes the subfactorial, which sometimes necessitates an unusual ordering of factors (see for instance in the formulas above).

The number 148,349 is the only number that is equal to the sum of the subfactorials of its digits:

148,349 = !1 + !4 + !8 + !3 + !4 + !9

Subfactorial is sometimes permitted in the Four fours mathematical game where !4 being 9 is helpful.

[edit] References

David Wells, The Penguin Dictionary of Curious and Interesting Numbers (2nd ed 1997) ISBN 0 14 026149 4, p.104

Categories: Permutations | Factorial and binomial topics

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Subfactorial

From Wikipedia, the free encyclopedia

Contents

[edit] Computing values of the subfactorial function

[edit] Explicit values

[edit] Miscellanea

[edit] References

Views

Navigation

Interaction

Search

Languages