Subfaktoriaal

$n$	Subfaktoriaal ${!}n$	Faktoriaal $n!$
0	1	1
1	0	1
2	1	2
3	2	6
4	9	24
5	44	120
6	265	720
7	1854	5040
8	14 833	40 320
9	133 496	362 880
10	1 334 961	3 628 800

Subfaktoriaal ehk de Montmorti arv ehk korratuste arv (tähis ${!}n$ ) on peamiselt kombinatoorikas kasutatav funktsioon, mis seab igale naturaalarvule $n$ vastavusse $n$ -elemendilise hulga korratuste ehk püsipunktita permutatsioonide hulga.

!n näitab näiteks, mitmel viisil saab n inimest vahetada kingitusi nii, et igaüks annab ühe kingituse kellelegi teisele ja saab täpselt ühe kingituse kelleltki teiselt.

Subfaktoriaal on tihedalt seotud faktoriaaliga $n!$ , mis annab $n$ -elemendilise hulga permutatsioonide koguarvu, ning on faktoriaali järgi ka nime saanud. Subfaktoriaal ei ületa kunagi faktoriaali:

!n\,\leq \,n!

.

Subfaktoriaal on ligikaudu võrdne faktoriaali ja arvu e jagatisega.

Definitsioon

Naturaalarvu $n\geq 0$ subfaktoriaal defineeritakse faktoriaali kaudu valemiga

{!}n=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}=n!\cdot \left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-{\frac {1}{3!}}+\cdots +(-1)^{n}{\frac {1}{n!}}\right)

.

Subfaktoriaal ${!}n$ vastab $n$ -elemendilise hulga püsipunktita permutatsioonide (korratuste) arvule, faktoriaal $n!$ aga kõigi võimalike permutatsioonide arvule.

Näide

Oletame, et meil on kuus eri värvi kuulikest ja iga kuulikese jaoks kast, mis on sellega ühte värvi. Tuleb leida, mitu võimalust on jagada kuulikesed kastidesse nii, et igas kastis on täpselt üks kuulike, aga ükski kuulike ei ole kastis, mis on sellega ühte värvi. Neid võimalusi on täpselt

{!}6=6!\cdot \left(1-{\frac {1}{1!}}+{\frac {1}{2!}}-{\frac {1}{3!}}+{\frac {1}{4!}}-{\frac {1}{5!}}+{\frac {1}{6!}}\right)=265

.

Teised esitused

Ümardusesitused

Subfaktoriaali lähenduste võrdlus
$n$	${\frac {n!}{e}}$	$\left[{\frac {n!}{e}}\right]$	${\frac {n!\!+\!1}{e}}$	$\left\lfloor {\frac {n!\!+\!1}{e}}\right\rfloor$
1	0,37	0	0,74	0
2	0,74	1	1,10	1
3	2,21	2	2,58	2
4	8,83	9	9,20	9
5	44,15	44	44,51	44
6	264,87	265	265,24	265
7	1854,11	1854	1854,48	1854
8	14832,90	14833	14833,27	14833
9	133496,09	133496	133496,46	133496

Kehtib valem

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

,

kus $e$ on arv e ja $\Gamma$ on mittetäielik gammafunktsioon.

Väga hea lähendus on

{!}n\approx {\frac {n!}{e}}

.

Ümardamise abil saab $n\geq 1$ kohta anda isegi täpse valemi

{!}n=\left[{\frac {n!}{e}}\right]

,

kus $\left[x\right]$ tähistab arvule $x$ lähimat täisarvu.

Kui viimasesse valemisse lisada enne jagamist veel ühe liitmine, siis ei ole enam tarvis vahet teha, kas ümardatakse alla- või ülespoole. Selle asemel kasutatakse lihtsalt täisosa, nii et ${!}n$ : avaldub nii:

{!}n=\left\lfloor {\frac {n!+1}{e}}\right\rfloor

,

kus $\left\lfloor x\right\rfloor$ tähistab arvu $x$ täisosa^[1].

Rekursiivsed esitused

Subfaktoriaali rekurrentne esitus
$n$	${!}(n-1)$	$n\cdot {!}(n-1)$	$(-1)^{n}$	${!}n$
1	1	1	−1	0
2	0	0	+1	1
3	1	3	−1	2
4	2	8	+1	9
5	9	45	−1	44
6	44	264	+1	265
7	265	1855	−1	1854
8	1854	14832	+1	14833
9	14833	133497	−1	133496

Subfaktoriaali saab arvutada ka rekurrentselt valemite

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

(

n\geq 1

)

ja

{!}n=(n-1)\cdot ({!}(n-1)+{!}(n-2))

(

n\geq 2

)

järgi. Avaldis ${!}(n-1)+{!}(n-2)$ vastab $n$ -elemendilise hulga püsipunktita permutatsioonide arvule ühe fikseeritud elemendi korral (jada A0002555 saidil OEIS).

Veel üks rekurrentne valem binoomkordajate kaudu on järgmine:

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

Selle saame järgmistel kaalutlustel. Permutatsioone on kokku $n!$ . $k$ püsipunkti saab valida ${n \choose k}$ viisil. Püsipunktita permutatsioone ülejäänud $n-k$ elemendiga on $!(n-k)$ .

Integraalesitus

Järgnev integraalesitus päratu integraali kaudu üldistab subfaktoriaali naturaalarvudelt kompleksarvudele, mille reaalosa on suurem kui math>-1</math>:

{!}z=\int _{0}^{\infty }\mathrm {e} ^{-t}(t-1)^{z}dt

.

Maatriksesitus

!n on sellise n-nda astme ruutmaatriksi permanent, mille peadiagonaalil on nullid ja mille ülejäänud elemendid on ühed.

Umbraalarvutus

Umbraalarvutuses kehtivad formaalsed samasused

Q^{n}=(P-1)^{n}

ja

P^{n}=(Q+1)^{n}

,

kus $P^{k}$ tähistab $k!$ ja $Q^{k}$ tähistab $!k$ .

Väärtuste tabel

!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

Meelelahutusmatemaatika

Ainus subfaktorioon, st ainus arv, mis võrdub oma kümnendesituse numbrite subfaktoriaalide summaga, on^[2]

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

.

Mängus "Neli nelja" mõne variandi puhul on kasulik teada, et !4 = 9.

Tähis

!n on kõige levinum tähis, kuid see on ebamugav, sest faktoriaali tähisega segiajamise vältimiseks tuleb kasutada sulgi. Muud tähised on M(n) (pärineb Pierre Rémond de Montmortilt), h(n, 0) (pärineb Donald Knuthilt), M_n ja n¡ .

Ajalugu

Korratuste arvuga tegelesid esimestena Leonhard Euler ja Nikolaus II Bernoulli.

Viited

↑ Mehdi Hassani. Derangements and Applications. – Journal of Integer Sequences, 2003, kd 6, artikkel 03.1.2.
↑ Joseph S. Madachy. Madachy's Mathematical Recreations, |New York: Dover 1979, lk 167.

Kirjandus

David Wells. The Penguin Dictionary of Curious and Interesting Numbers, 2. trükk. 1997, 1997, ISBN 0140261494, lk 104.
Joseph S. Madachy. Madachy's Mathematical Recreations, New York: Dover 1979, lk 167.

Välislingid

Eric W. Weisstein. Subfactorial, MathWorld.
Jada A000166, OEIS

[1] Mehdi Hassani. Derangements and Applications. – Journal of Integer Sequences, 2003, kd 6, artikkel 03.1.2.

[2] Joseph S. Madachy. Madachy's Mathematical Recreations, |New York: Dover 1979, lk 167.

[1]

[2]

KoduKe

Värsked postitused

Most Used Categories

Eelnõu kohustaks mobiilsete liikluskaamerate ette panema hoiatusmärgi

Startup Estonia viib iduettevõtted Euroopa mainekaimale süvatehnoloogia messile

Anekdoot: mees mängib arvutis päevad läbi sõda

ERGO aasta ennetajaks valiti veepäästekoerad

Anekdoot: kas Tallinn on veel kaugel?

VIDEO: Hiinas said töötajad krabada laua pealt raha nii palju kui suutsid

Tesla Cybertruckid paisatakse suure allahindlusega müüki: keegi ei osta

HOIATUS ⟩ Saabuv sula võib kaasa tuua ootamatuid üleujutusi

Põhja-Korea on valmis tuumariigiks tunnustamisel USA-ga läbi saama

Martin Helme hoiatas meelepaha tänavatele valgumise eest