Subfactorial

From Wikipedia, the free encyclopedia

You have new messages (last change).

The subfactorial function, written as !n, is used to calculate the number of permutations of a set of n objects in which none of the elements occur in their natural place. These are also known as derangements. (The factorial function itself calculates the total number of permutations of the set.)

In practical terms, subfactorial is the number of ways of putting n letters into n envelopes (one in each envelope) with none in its correct envelope.

It can 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 ]

where [x] denotes the nearest integer function.

!n = !(n-1)\;n + (-1)^n
!n = (n-1)\;(!(n-1)+!(n-2))
!n = (n-1)\; a_{n-2} with \;a_0 = a_1 = 1 and a_n = n\;a_{n-1} + (n-1)\;a_{n-2} (sequence A000255 in OEIS)

The first few values of the function are:

!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

The number 148,349 has the surprising property that it 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.

Retrieved from "http://en.wikipedia.org../../../s/u/b/Subfactorial.html"
In other languages