Subfactorial

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
n !n
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

En matemáticas, el subfactorial de un número natural n, a veces escrito como !n, es el número de posibles desarreglos (permutación donde ninguno de sus elementos aparece en la posición original) de un conjunto con n elementos. En términos concretos, el subfactorial cuenta el número de formas diferentes en que n personas podrían cambiar por ejemplo: regalos, donde cada persona da un regalo a otra persona, y cada uno recibe exactamente otro regalo. El subfactorial es una función del conjunto de números naturales que devuelve un valor también natural.

La función subfactorial define la secuencia A000166 en OEIS.

El nombre “subfactorial” viene de la función factorial (usualmente escrita n!), la cual cuenta el número 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 \,\le\, n!

Computando los valores de la función Subfactorial[editar]

Los subfactoriales pueden ser calculados usando el principio de inclusión-exclusion.

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

También pueden ser calculados de las siguientes formas:

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

donde \Gamma denota la función gamma incompleta, y e es la constante de Euler; o

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

donde [x] denota la función parte entera más cercana.

!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,

donde la secuencia(an)n está dada por \;a_0 = a_1 = 1 y a_n = n\;a_{n-1} + (n-1)\;a_{n-2}; esta es la secuencia OEIS:A000255

Los subfactoriales también pueden ser calculados recursivamente:

!n = n! - \sum_{k=1}^{n} {n \choose k}(!(n-k))

La intuición aquí es la siguiente: Primero, hay n! permutaciones en total. Nosotros vamos a contar sistemáticamente los que mantienen precisamente k número de objetos fijos. Escogiendo k objetos para que mantengan fijos. Hay {n \choose k} manera de hacer esto. Ahora, los objetos n-k faltantes necesitan ser permutados, con alguno que mantega fijo. El número de formas de hacer esto es: !(n-k).

Una forma recursiva de calcularlo, es, partiendo de que !1 = 0 y !2 = 1,

!n = (n - 1) (!(n-1) + !(n-2)).\,

Miscelanea[editar]

La notación !n no es universalmente aceptada. Da ambigüedad a la notación de la función factorial si hay algún valor que procede el subfactorial, lo cual hace que usualmente se necesite un inusual ordenamiento de los factores (véase por ejemplo las fórmulas arriba), o parentesis rodeando el subfactorial.

El número 148,349 es el único número en que es igual a la suma de los subfactoriales de sus dígitos:

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

El uso de subfactoriales a veces es permitido en el juego matemático llamado Cuatro cuatros, donde el hecho que !4 sea 9 es útil.

Referencias[editar]

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