Fakultet (matematik)

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.

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 0! ≡ 1.

Till exempel är 4! = 4 ⋅ 3 ⋅ 2 ⋅ 1 = 4 ⋅ 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å  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å  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 

Om man definierar fakultet som en funktion som uppfyller villkoret   så går det att hitta funktioner som även fungerar på mer än de naturliga talen.

Förhållandet gör att man kan beräkna fakulteten för ett heltal med hjälp av ett mindre heltal. Relationen kan inverteras så att man kan beräkna fakulteten med hjälp av ett större heltal:

Men använder man denna formel för att beräkna (−1)! så innebär det en division med noll:

 

Det finns två sätt att hantera detta, antingen konstruera en funktion som inte är definierad för de negativa heltalen, eller konstruera en funktion som bara uppfyller villkoret  för naturliga tal.

Det första sättet är den vanligaste och används i Eulers gammafunktion:

Den andra sättet är Hadamards gammafunktion:

där  står för Eulers gammafunktion.

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

.

Se även 
 Semifakultet
 Primorial

Källor

Operatorer