Heltalspartition

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 .

Exempel 
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
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, ...  
Vidare är p(100) = 190569292, p(1000) = 24061467864032622473692149727991 och p(10000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144.

Genererande funktion
Partitionsfunktionens genererande funktion ges av

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

Kongruenser

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
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 (m, n) = 1 att summan går över alla värden på m relativt prima till n. Funktionen s(m, k) ä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
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):

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å).

 Källor 
 George E. Andrews, The Theory of Partitions (1976), Cambridge University Press.   .
   (See chapter 5 for a modern pedagogical intro to Rademacher's formula).
 
  Provides the main formula (no derivatives), remainder, and older form for Ak(n).)
 Gupta, Gwyther, Miller, Roy. Soc. Math. Tables, vol 4, Tables of partitions, (1962) (Has text, nearly complete bibliography, but they (and Abramowitz) missed the Selberg formula for Ak(n), which is in Whiteman.)
  (See section I.1)
 
 Ken Ono, Distribution of the partition function modulo m, Annals of Mathematics 151 (2000) pp 293–307. (This paper proves congruences modulo every prime greater than 3)
 Sautoy, Marcus Du. The Music of the Primes. New York: Perennial-HarperCollins, 2003.
 Richard P. Stanley, Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press, 1999 
  (Provides the Selberg formula. The older form is the finite Fourier expansion of Selberg.)
 Hans Rademacher, Collected Papers of Hans Rademacher, (1974) MIT Press; v II, p 100–107, 108–122, 460–475.
  (qn elementary introduction to the topic of integer partition, including a discussion of Ferrers graphs)
 
 'A Disappearing Number', devised piece by Complicite, mention Ramanujan's work on the Partition Function, 2007

Kombinatorik
Aritmetiska funktioner
Heltalsmängder