Fakultet (matematik)
Från Rilpedia
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! utläses tre-fakultet) och allmänt för alla heltal n > 0
Man gör dessutom definitionen
På så sätt är fakultetsfunktionen definierad för alla naturliga tal.
Rekursivitet
Fakultetsfunktionen kan uttryckas rekursivt eftersom det gäller att
.
Rekursionen avbryts då n = 0 och 
.
Till exempel är 
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
Här blir definitionen 0! = 1 ganska naturlig. Antalet sätt att kombinera noll element blir alltså
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
för alla 
.
Datorberäkning
Då 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 ... pP ≤ n, där pk har multipliciteten
.
