Partitie (getaltheorie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
een Ferrersdiagram dat de partities toont 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).

Voorbeelden[bewerken]

De partities van 4:

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

De partities van 8:

  1. 8
  2. 7 + 1
  3. 6 + 2
  4. 6 + 1 + 1
  5. 5 + 3
  6. 5 + 2 + 1
  7. 5 + 1 + 1 + 1
  8. 4 + 4
  9. 4 + 3 + 1
  10. 4 + 2 + 2
  11. 4 + 2 + 1 + 1
  12. 4 + 1 + 1 + 1 + 1
  13. 3 + 3 + 2
  14. 3 + 3 + 1 + 1
  15. 3 + 2 + 2 + 1
  16. 3 + 2 + 1 + 1 + 1
  17. 3 + 1 + 1 + 1 + 1 + 1
  18. 2 + 2 + 2 + 2
  19. 2 + 2 + 2 + 1 + 1
  20. 2 + 2 + 1 + 1 + 1 + 1
  21. 2 + 1 + 1 + 1 + 1 + 1 + 1
  22. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Partitiefunctie[bewerken]

De partitiefunctie p(n) is gelijk aan het aantal mogelijke partities van een getal n. Bijvoorbeeld p(4)=5. Door conventie is 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

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 die partities zijn met enkel 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 die enkel gebruik maakt van 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. [1]

Externe links[bewerken]

Bronnen, noten en/of referenties
  1. Andrews, George E. Number Theory. W. B. Saunders Company, Philadelphia, 1971. Dover edition, page 149–150.