Hoppa till innehållet

Heltalspartition

Från Wikipedia

Partition av ett tal är, inom talteori, ett sätt att skriva ett positivt heltal n som en summa av positiva heltal utan hänsyn till termernas inbördes ordning. Ibland även kallad oordnad partition. Partitionsfunktionen p(n) ger antalet möjliga partitioner av talet n. Något enkelt sätt att beräkna p(n) finns inte.

Om hänsyn till termernas ordning tas, talar man om ordnade partitioner av n. Med uttrycket k-partition av talet n menas en partition av n som består av k termer. Det totala antalet ordnade partitioner av n är lika med och antalet ordnade k-partitioner av n är lika med .

Talet 5 kan partitioneras på 7 olika sätt:

  • 5
  • 4 + 1
  • 3 + 2
  • 3 + 1 + 1
  • 2 + 2 + 1
  • 2 + 1 + 1 + 1
  • 1 + 1 + 1 + 1 + 1

Antalet 3-partitioner av talet 5 är lika med 2, antalet ordnade 3-partitioner av talet 5 är lika med 6 och det totala antalet ordnade partitioner av 5 är lika med 16.

Partitionsfunktionen

[redigera | redigera wikitext]

Partitionsfunktionen p(n) är en funktion, som ger antalet möjliga partitioner av n. Defininitionsmässigt är p(0) = 1.

De första värdena av partitionsfunktionen p(n) är: p(1), p(2)... =

1, 2, 3, 5, 7, 11, 15, 22, 30, 42, ... (talföljd A000041 i OEIS)

Vidare är p(100) = 190569292, p(1000) = 24061467864032622473692149727991 och

p(10000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144.

Genererande funktion

[redigera | redigera wikitext]

Partitionsfunktionens genererande funktion ges av

Genererande funktionen för q(n), antalet partitioner av n till olika delar, ges av

Srinivasa Ramanujan upptäckte några kongruenser för partitionsfunktionen:

Det här följer av en identitet av Ramanujan,

där är q-Pochhammersymbolen, definierad som

Han upptäckte även kongruenser relaterade till 7 och 11:

och för p=7 relationen

A. O. L. Atkin har bevisat några andra kongruenser, såsom

En något mer komplicerad kongruens av F. Johansson (2012) är

Approximationer

[redigera | redigera wikitext]

En asymptotisk formel för p(n) är

G. H. Hardy och Srinivasa Aiyangar Ramanujan bevisade formeln 1918 och senare upptäcktes den oberoende av J. V. Uspensky 1920.

Hardy and Ramanujan förbättrade senare formeln till

där

Här betyder (mn) = 1 att summan går över alla värden på m relativt prima till n. Funktionen s(mk) är en Dedekindsumma.

1937 förbättrade Hans Rademacher Hardys och Ramanujans resultat genom att bevisa en konvergerande serie för p(n). Serien är

En metod att beräkna partitionsfunktionen

[redigera | redigera wikitext]

Låt P(n,k) beteckna antalet partitioner av heltalet n som består av k termer och skriv dem i en tabell med en rad för varje n och varje k i en kolonn, enligt nedan (översta raden motsvarar n=0):

1
1
1 1
1 1 1
1 2 1 1
1 2 2 1 1
1 3 3 2 1 1
1 3 4 3 2 1 1
1 4 5 5 3 2 1 1
1 4 7 6 5 3 2 1 1

Självklart är summan av talen i varje rad lika med antalet partitioner av n.

Den här tabellen skapas genom att man för varje k i rad n bildar P(n,k) genom att lägga ihop de k talen längst till vänster i rad n-k (om k>n-k, "fyller man på" raden med nollor så långt det behövs åt höger).

Exempel
I den nedersta raden (n=9) är den första ettan lika med ettan längst till vänster i raden ovanför (P(9,1)=P(8,1)=1). Nästa tal, 4, är summan av de två första talen två rader ovanför (P(9,2)=P(7,1)+P(7,2)=1+3=4). Tredje talet, 7, är summan av de tre första talen tre rader ovanför (P(9,3)=P(6,1)+P(6,2)+P(6,3)=1+3+3=7). P(9,4)=P(5,1)+P(5,2)+P(5,3)+P(5,4)=1+2+2+1=6. P(9,5)=P(4,1)+P(4,2)+P(4,3)+P(4,4)+"P(4,5)"=1+2+1+1+0=5. Etcetera...

Att man verkligen får värdena på P(n,k) på detta sätt inses om man beaktar att man måste ha exakt k termer som alla är större än noll. När vi tilldelat dessa k termer det minimala värdet ett återstår n-k att fördela på dessa k termer. Detta kan göras på det antal sätt som är lika med summan av P(n-k,1) till P(n-k,k) (vi kan fördela resten, n-k, på en av termerna på ett sätt, på två av termerna på P(n-k,2) sätt, etcetera, och när vi antingen når n-k finns inte mer "rest" kvar att fördela eller när vi når k finns det inte fler termer att fördela "resten" på).