# Partitie (getaltheorie)

In de getaltheorie is een partitie van een positief natuurlijk getal een manier om dat getal te schrijven als een som van positieve natuurlijke getallen, waarbij dezelfde termen in een andere volgorde niet als andere som geldt. Het aantal partities van $n$ wordt gegeven door de partitiefunctie $p(n).$
Een Ferrersdiagram is de grafische voorstelling van een partitie van een getal.

## Voorbeelden
### Partities van het getal 4

* $\quad$ 4
* $\quad$ 3 + 1
* $\quad$ 2 + 2
* $\quad$ 2 + 1 + 1
* $\quad$ 1 + 1 + 1 + 1

### Groepentheorie

Het is in de groepentheorie gegeven dat iedere conjugatieklasse in de symmetrische groep door het cykeltype van de elementen binnen die conjugatieklasse is bepaald. Het aantal conjugatieklassen in de symmetrische groep $S(n)$ is dus gelijk aan het aantal partities van het getal $n.$
    partities van 7 cykeltypeaantal 11 1 1 1 1 1 11 22 1 1 1 1 121 33 1 1 1 170 42 2 1 1 1105 54 1 1 1210 63 2 1 1420 75 1 1504 82 2 2 1105 94 2 1630 103 3 1280 116 1840 123 2 2210 135 2504 144 3420 157720 5040

## Partitiefunctie

De partitiefunctie $p(n)$ is gelijk aan het aantal mogelijke partities van het getal $n.$ Bijvoorbeeld is $p(4)=5.$ Per definitie is $p(0)=1$. Voor het gemak definieert men ook $p(n)=0$ voor negatieve gehele getallen $n.$

### Waarden

* p(1) = 1
* p(2) = 2
* p(3) = 3
* p(4) = 5
* p(5) = 7
* p(6) = 11
* p(7) = 15
* p(8) = 22
* p(9) = 30
* p(10) = 42
* p(100) = 190.569.292
* p(200) = 3.972.999.029.388
* p(1000) = 24.061.467.864.032.622.473.692.149.727.991 ≈ 2,4 × 10$^{31}$
Srinivasa Aaiyangar Ramanujan heeft in de partitiefunctie een aantal congruenties ontdekt. Voor elke gehele $k$ geldt
    $p(5k+4)\equiv 0{\pmod {5}}$
    $p(7k+5)\equiv 0{\pmod {7}}$
    $p(11k+6)\equiv 0{\pmod {11}}$

### Voortbrengende functie

De voortbrengende functie voor $p(n)$ is, zoals bewezen door Euler:
    $\sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{k}}}\right).$
Elke factor in dit product kan worden beschouwd als de som van een meetkundige rij, zodat men het kan uitwerken als:
    $(1+x+x^{2}+x^{3}+\ldots )(1+x^{2}+x^{4}+x^{6}+\ldots )(1+x^{3}+x^{6}+x^{9}+\ldots )\ldots =$
    $=1+x+2x^{2}+3x^{3}+5x^{4}+7x^{5}+\ldots$

## Intermediaire partitiefunctie

De intermediaire partitiefunctie $p(k,n)$ is het aantal partities die alleen maar getallen gebruikt die groter of gelijk zijn aan $k.$ Hier enkele voorbeelden:
* p(1, 4) = 5
* p(2, 8) = 7
* p(3, 12) = 9
* p(4, 16) = 11
* p(5, 20) = 13
* p(6, 24) = 16
De originele partitiefunctie $p(n)$ is dus $p(1,n).$
Hier volgt een tabel met waarden van $p(k,n)$:
    k 1 2 3 4 5 6 7 8 9 10 n 1 1000000000 2 2100000000 3 3110000000 4 5211000000 5 7211100000 6 11421110000 7 15421111000 8 22732111100 9 30842111110 10 421253211111

## Partities met voorwaarden

Van de 22 partities voor het getal 8 zijn er 6 partities met alleen oneven getallen:
* 7 + 1
* 5 + 3
* 5 + 1 + 1 + 1
* 3 + 3 + 1 + 1
* 3 + 1 + 1 + 1 + 1 + 1
* 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Het aantal partities van 8 met alleen verschillende getallen is eveneens gelijk aan 6:
* 8
* 7 + 1
* 6 + 2
* 5 + 3
* 5 + 2 + 1
* 4 + 3 + 1
Leonhard Euler toonde in 1748 aan dat voor alle natuurlijke getallen het aantal partities met oneven getallen altijd gelijk is aan het aantal partities met verschillende getallen.

## Externe link

* H Hofstede Uit Hoeveel sommen komt 20? over de berekening van het aantal partities van een getal