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.

$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... × 10⁶⁴
70	1,19785717... × 10¹⁰⁰
450	1,73368733... × 10^1,000
3249	6,41233768... × 10^10,000
25206	1,205703438... × 10^100,000
1000000	8,263931688... × 10^5565708

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!=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! ≡ 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å 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

Om man definierar fakultet som en funktion som uppfyller villkoret n! = n × (n − 1)! 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:

(n-1)!={\frac {n!}{n}}.

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

{\frac {0!}{0}}.

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 n! = n × (n − 1)! för naturliga tal.

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

\Gamma (z)=\int _{0}^{\infty }x^{z-1}e^{-x}\,dx

Den andra sättet är Hadamards gammafunktion:

H(x)={\frac {1}{\Gamma (1-x)}}\,{\dfrac {d}{dx}}\left\{\ln \left({\frac {\Gamma ({\frac {1}{2}}-{\frac {x}{2}})}{\Gamma (1-{\frac {x}{2}})}}\right)\right\}

där Γ(x) står för Eulers gammafunktion^[1].

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 p₁, p₂ ... p_P ≤ n, där p_k har multipliciteten

\sum _{i=1}^{P}\lfloor n/p_{k}^{i}\rfloor

.

Se även

Källor

^ Thukral, Ashwani K (6 November 2014). ”Factorials of real negative and imaginary numbers - A new perspective”. SpringerPlus (Springer Science and Business Media LLC) 3 (1). doi:10.1186/2193-1801-3-658. ISSN 2193-1801.

Wiktionary har ett uppslag om fakultet.
Ordbok

[1] Thukral, Ashwani K (6 November 2014). ”Factorials of real negative and imaginary numbers - A new perspective”. SpringerPlus (Springer Science and Business Media LLC) 3 (1). doi:10.1186/2193-1801-3-658. ISSN 2193-1801.

[1]