Fakultet (matematik)

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

Fakultet är en funktion inom matematiken. För ett heltal större än noll är fakulteten lika med produkten av alla heltal från 1 upp till och med talet självt.

Innehåll

n n!
0 1
1 1
2 2
3 6
4 24
5 120
6 720
7 5040
8 40320
9 362 880
10 3 628 800
20 2 432 902 008 176 640 000
50 3,04140932... × 1064
70 1,19785717... × 10100
450 1,73368733... × 101,000
3249 6,41233768... × 1010,000
25206 1,205703438... × 10100,000

Beteckning

Fakultet betecknas med ett utropstecken (!), fakultetstecken. Alltså är till exempel

 3! = 1 \cdot 2 \cdot 3 = 6

(3! utläses tre-fakultet) och allmänt för alla heltal n > 0

 n! = \prod_{k=1}^{n} k = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n

Man gör dessutom definitionen

 0! = 1 \

På så sätt är fakultetsfunktionen definierad för alla naturliga tal.

Rekursivitet

Fakultetsfunktionen kan uttryckas rekursivt eftersom det gäller att

 n!=n \cdot (n-1)! .

Rekursionen avbryts då n = 0 och 0! \equiv 1.

Till exempel är  4! = 4 \cdot 3 \cdot 2 \cdot 1 = 4 \cdot 3!

Användning inom kombinatoriken

Fakulteter förekommer mycket ofta inom kombinatoriken, bland annat när det gäller att beräkna antalet möjliga sammansättningar av ett visst antal element.

Antag till exempel att man har fyra kulor (blå, grön, gul, röd). Dessa fyra kulor kan läggas i en rad på precis 4! = 24 olika sätt (permutationer).

Detta kan förklaras såhär: När man väljer den första kulan i raden har man 4 möjliga val. När man väljer den andra kulan i raden har man 3 möjliga val (en kula är ju redan upptagen). En rad med två kulor kan alltså väljas på 4 · 3 = 12 olika sätt. Den tredje kulan kan väljas på 2 olika sätt och den fjärde på precis ett sätt. Antalet möjliga rader med fyra kulor är alltså 4 · 3 · 2 · 1 = 4! stycken.

Vidare kan man visa att antalet möjliga kombinationer av k element ur en mängd med n element är

 \frac {n!} {k! (n-k)!}

Här blir definitionen 0! = 1 ganska naturlig. Antalet sätt att kombinera noll element blir alltså

 \frac {n!} {0! \cdot (n-0)!} = \frac {n!} {1 \cdot n!} = 1

Se vidare binomialkoefficient.

Generalisering

Gammafunktionen är en generalisering av fakultetsfunktionen till reella och övriga komplexa tal (förutom de ickepositiva heltalen). Speciellt gäller att

z! = \Gamma(z+1) \  för alla z \in \Z^+ .

Datorberäkning

n är litet beräknas n! enklast genom upprepad multiplikation. Eftersom n! växer snabbt blir den här metoden dock ofta opraktisk för stora n, och i numeriska tillämpningar används i regel Stirlings formel eller liknande approximationer för att beräkna fakulteten (eller gammafunktionen) med flyttalsprecision.

Även exakta fakulteter av mycket stora heltal har många tillämpningar, exempelvis inom beräkningar som rör kombinatorik och talteori. Sådana fakulteter kan i princip beräknas genom att multiplicera alla talen 1, 2, ... n i sekvens, men detta är ineffektivt eftersom många stora delprodukter uppstår. Ett bättre angreppssätt är att rekursivt dela upp sekvensen så att delprodukterna blir mindre. Optimal prestanda uppnås genom att först bestämma alla exponenter i primtalsfaktoriseringen av n! och sedan beräkna potenserna genom upprepad kvadrering. På så sätt kan även stora binomialkoefficienter beräknas effektivt, genom att primtalsfaktorisera fakulteterna i nämnaren och täljaren och sedan subtrahera exponenter.

Faktoriseringen av n! utgörs av alla primtalen p1, p2 ... pPn, där pk har multipliciteten

\sum_{i=1}^P \lfloor n/p_k^i \rfloor.

Se även

Personliga verktyg