Subfactorial

En matemàtiques, el subfactorial d'un número natural n, a voltes escrit com !n, és el número de possibles desarreglos (permutació a on cap dels seus elements apareix en la posició original) d'un conjunt en n elements. En térmens concrets, el subfactorial conta el número de formes diferents en que n persones podrien canviar per eixemple: regals, a on cada persona dona un regal a una atra persona, i cada u rep exactament un atre regal. El subfactorial és una funció del conjunt d'número natural que torna un valor també natural.

La funció subfactorial definix la seqüència A000166 en OEIS.

El nom «subfactorial» ve de la funció factorial (usualment escrita n!), la qual conta el número total de permutació d'un element n d'un conjunt. El valor del subfactorial és sempre menor o igual que el factorial corresponent a mateix n:

! n \leq n!

Computant els valors de la funció Subfactorial

$n$	$! n$
0	1
1	0
2	1
3	2
4	9
5	44
6	265
7	1854
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
22	413 496 759 611 120 779 881
23	9 510 425 471 055 777 937 262

Els subfactoriales poden ser calculats usant el principi d'inclusió-exclusió.

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

També poden ser calculats de les següents formes:

! n = \int_{0}^{\infty} (x - 1)^{n} e^{- x} d x = \frac{Γ (n + 1, - 1)}{e}

a on $Γ$ denota la funció gamma incompleta, i i és la constant de Euler; o

! n = [\frac{n!}{e}] para n \geq 1

a on $x$ denota la funció partix sancera més propenca.

! n =! (n - 1) n + (- 1)^{n} para n \geq 1

! n = (n - 1) (! (n - 1) +! (n - 2)) para n \geq 2

! n = (n - 1) a_{n - 2} para n \geq 2,

a on la seqüència $(a_{n})_{n}$ està donada per $a_{0} = a_{1} = 1$ i $a_{n} = n a_{n - 1} + (n - 1) a_{n - 2}$ ; esta és la seqüència OEIS:A000255

Els subfactoriales també poden ser calculats recursivamente:

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

Intuitivament, l'expressió anterior pot deduir-se a partir de les següents observacions:

Per a $n$ objectes existixen un total de $n!$ permutació (primer terme de la dreta).
Dels $n$ objectes triem un número $k$ objectes que mantindrem fixos (sumatorio en $k$ ).
Existixen un total de $(\binom{n}{k})$ formes possibles de fixar $k$ objectes d'una mostra de $n$ .
Aixina mateix, els $(n - k)$ objectes no fixats poden permutar-se de $! (n - k)$ formes diferents (terme dins del sumatorio).

Recursivament, el factorial d'un número pot calcular-se partint de que $! 1 = 0$ i $! 2 = 1$ com $! n = (n - 1) (! (n - 1) +! (n - 2)) .$

Miscelànea

La notació !n no és universalment acceptada. Dona ambigüitat a la notació de la funció factorial si hi ha algun valor que precedix al subfactorial, la qual cosa fa que usualment es necessite un inusual ordenament dels factors (vore per eixemple les fòrmules dalt), o paréntesis rodejant el subfactorial. No obstant, existixen atres notacions que carixen d'esta ambigüitat, com a D_n, d_n, o n¡ (que usa el signe d'exclamació invertit).^[1]

El número 148 349 és l'únic número que és igual a la suma dels subfactoriales dels seus dígits:

148349 =! 1 +! 4 +! 8 +! 3 +! 4 +! 9

L'us de subfactoriales a voltes és permés en el joc matemàtic cridat Quatre cuatros, a on el fet que !4 siga 9 és útil.

Referències

↑ Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics (1994), Addison–Wesley, Reading MA. ISBN 0-201-55802-5

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

fr:Analogues de la factorielle#Sous-factorielle

Referències

Este artícul conté una traducció derivada de «Subfactorial» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics (1994), Addison–Wesley, Reading MA. ISBN 0-201-55802-5

[1]