Subfactorial

En matematicas, el subfactorial de un numero natural n, a veces escrito como !n, es el numero de posibles desarreglos(permutacion donde ninguno de sus elementos aparece en la posicion original) de un conjunto con n elementos. En terminos concretos, el subfactorial cuenta el numero de formas diferentes en que n personas podrian cambiar por ejemplo: regalos, donde cada persona da un regalo a otra persona, y cada uno recibe exactamente otro regalo. El subfactorial es una funcion del conjunto de numeros naturales que devuelve un valor tambien natural. Los primeros valores son:

$!0\,=\,1,\quad !1\,=\,0,\quad !2\,=\,1,\quad !3\,=\,2,\quad !4\,=\,9,\quad !5\,=\,44.$

La funcion subfactoriak define la secuencia A000166 en OEIS.

El nombre “subfactorial” viene de la funcion factorial (usualmente escritan!), la cual cuenta el numero total de permutaciones de un elemento n de un conjunto. El valor del subfactorial es siempre menor o igual que el factorial correspondiente a mismo n:

$!n\,\leq \,n!$

Computando los valores de la funcion Subfactorial

Los subfactoriales pueden ser calculados usando el principio de inclusion-exclusion.

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

Tambien pueden ser calculados de las siguientes formas:

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

donde $\Gamma$ denota la funcion gama incompleta, y e es la constante de euler; o

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

donde [x] denota la funcion entera mas cercana.

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

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

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

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

Los subfactoriales tambien pueden ser carlculados recursivamente:

$!n=n!-\sum _{k=1}^{n}{n \choose k}(!(n-k))$

The intuition here is the following: first, there are $n!$ total permutations. We are going to systematically account for those which keep precisely $k$ objects fixed. Choose $k$ objects to remain fixed. There are ${n \choose k}$ ways to do this. Now, the remaining $n-k$ objects need to be permuted, with none remaining fixed. The number of ways to do this is $!(n-k)$.

Valores explicitos

Los primeros valores de la funcion son:

!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

Miscelanea

La notacion !n no es universalmente aceptada. 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), or brackets round the subfactorial.

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.

References

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