Partitie (getaltheorie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Ferrersdiagram met de partities van de getallen 1 tot 8

In de getaltheorie is de partitie van een positief natuurlijk getal n een manier om dat getal te schrijven als een som van positieve natuurlijke getallen. Het aantal partities van n is gegeven door de partitiefunctie p(n).

Een Ferrersdiagram is de grafische voorstelling van een partitie van een getal.

Voorbeelden[bewerken]

Partities van 4[bewerken]

  1. 4
  2. 3 + 1
  3. 2 + 2
  4. 2 + 1 + 1
  5. 1 + 1 + 1 + 1

Groepentheorie[bewerken]

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 Sn is dus gelijk aan het aantal partities van het getal n.

partities van 7
cykeltype aantal[1]
1 1 1 1 1 1 1 1 1
2 2 1 1 1 1 1 21
3 3 1 1 1 1 70
4 2 2 1 1 1 105
5 4 1 1 1 210
6 3 2 1 1 420
7 5 1 1 504
8 2 2 2 1 105
9 4 2 1 630
10 3 3 1 280
11 6 1 840
12 3 2 2 210
13 5 2 504
14 4 3 420
15 7 720
5040

Partitiefunctie[bewerken]

De partitiefunctie p(n) is gelijk aan het aantal mogelijke partities van een getal n. Bijvoorbeeld p(4)=5. Het is gedefinieerd dat p(0) = 1 en p(n) = 0 voor n een negatief geheel getal.

Waarden[bewerken]

  • 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 k geldt

.

Voortbrengende functie[bewerken]

De voortbrengende functie voor p(n) 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:

(1 + x + x2 + x3 + ...)(1 + x2 + x4 + x6 + ...)(1 + x3 + x6 + x9 + ...) ... = 1 + x + 2 x2 + 3 x3 + 5 x4 + 7 x5 + ...

Intermediaire partitiefunctie[bewerken]

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 1 0 0 0 0 0 0 0 0 0
2 2 1 0 0 0 0 0 0 0 0
3 3 1 1 0 0 0 0 0 0 0
4 5 2 1 1 0 0 0 0 0 0
5 7 2 1 1 1 0 0 0 0 0
6 11 4 2 1 1 1 0 0 0 0
7 15 4 2 1 1 1 1 0 0 0
8 22 7 3 2 1 1 1 1 0 0
9 30 8 4 2 1 1 1 1 1 0
10 42 12 5 3 2 1 1 1 1 1

Partities met voorwaarden[bewerken]

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. [2]


  1. Het aantal conjugatieklassen in de symmetrische groep S7 met het gegeven cykeltype
  2. (en) GE Andrews Number Theory, 1971. blz 149–150.