title: Partitie (getaltheorie)
text: 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  wordt gegeven door de partitiefunctie 
  
  Een Ferrersdiagram is de grafische voorstelling van een partitie van een getal.
  
  Voorbeelden
  
  Partities van het getal 4 
    4
    3 + 1
    2 + 2
    2 + 1 + 1
    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  is dus gelijk aan het aantal partities van het getal 
  
  {| class="wikitable"
  !colspan=3| partities van 7
  |-
  ! !! cykeltype !! aantal
  |-
  | align="right" | 1 || 1 1 1 1 1 1 1 || align="right" | 1
  |-
  | align="right" | 2 || 2 1 1 1 1 1 || align="right" | 21
  |-
  | align="right" | 3 || 3 1 1 1 1 || align="right" | 70
  |-
  | align="right" | 4 || 2 2 1 1 1 || align="right" | 105
  |-
  | align="right" | 5 || 4 1 1 1 || align="right" | 210
  |-
  | align="right" | 6 || 3 2 1 1 || align="right" | 420
  |-
  | align="right" | 7 || 5 1 1 || align="right" | 504
  |-
  | align="right" | 8 || 2 2 2 1 || align="right" | 105
  |-
  | align="right" | 9 || 4 2 1 || align="right" | 630
  |-
  | align="right" | 10 || 3 3 1 || align="right" | 280
  |-
  | align="right" | 11 || 6 1 || align="right" | 840
  |-
  | align="right" | 12 || 3 2 2 || align="right" | 210
  |-
  | align="right" | 13 || 5 2 || align="right" | 504
  |-
  | align="right" | 14 || 4 3 || align="right" | 420
  |-
  | align="right" | 15 || 7 || align="right" | 720
  |-
  | || || align="right" | 5040
  |}
  
  Partitiefunctie 
  De partitiefunctie  is gelijk aan het aantal mogelijke partities van het getal  Bijvoorbeeld is  Per definitie is . Voor het gemak definieert men ook  voor negatieve gehele getallen
  
  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 × 1031
  
  Srinivasa Aaiyangar Ramanujan heeft in de partitiefunctie een aantal congruenties ontdekt. Voor elke gehele  geldt
  
  Voortbrengende functie 
  De voortbrengende functie voor  is, zoals bewezen door Euler:
  
  Elke factor in dit product kan worden beschouwd als de som van een meetkundige rij, zodat men het kan uitwerken als:
  
  Intermediaire partitiefunctie 
  De intermediaire partitiefunctie  is het aantal partities die alleen maar getallen gebruikt die groter of gelijk zijn aan  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  is dus 
  
  Hier volgt een tabel met waarden van :
  
  {| class="wikitable"
  !colspan=2 rowspan=2| ||colspan=10 align=center | k
  |-align=right
  ! width="22" | 1
  ! width="22" | 2
  ! width="22" | 3
  ! width="22" | 4
  ! width="22" | 5
  ! width="22" | 6
  ! width="22" | 7
  ! width="22" | 8
  ! width="22" | 9
  ! width="22" | 10
  |-align=right
  ! rowspan=10 width="22" | n
  ! width="22" | 1
  |1||0||0||0||0||0||0||0||0||0
  |-align=right
  !2
  |2||1||0||0||0||0||0||0||0||0
  |-align=right
  !3
  |3||1||1||0||0||0||0||0||0||0
  |-align=right
  !4
  |5||2||1||1||0||0||0||0||0||0
  |-align=right
  !5
  |7||2||1||1||1||0||0||0||0||0
  |-align=right
  !6
  |11||4||2||1||1||1||0||0||0||0
  |-align=right
  !7
  |15||4||2||1||1||1||1||0||0||0
  |-align=right
  !8
  |22||7||3||2||1||1||1||1||0||0
  |-align=right
  !9
  |30||8||4||2||1||1||1||1||1||0
  |-align=right
  !10
  |42||12||5||3||2||1||1||1||1||1
  |}
  
  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
    Uit Hoeveel sommen komt 20? over de berekening van het aantal partities van een getal
  
  Referenties
  
  Combinatoriek
  Getaltheorie
  Rij van gehele getallen