Heltalspartition

För andra betydelser, se Partition.

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 2 n − 1 {\displaystyle 2^{n-1}} och antalet ordnade k-partitioner av n är lika med ( n − 1 k − 1 ) {\displaystyle {\binom {n-1}{k-1}}} .

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, ... (talföljd A000041 i OEIS)

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

p(10000) = 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144.

Genererande funktion

Partitionsfunktionens genererande funktion ges av

∑ n = 0 ∞ p ( n ) x n = ∏ k = 1 ∞ ( 1 1 − x k ) . {\displaystyle \sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{k}}}\right).}

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

∑ n = 0 ∞ q ( n ) x n = ∏ k = 1 ∞ ( 1 + x k ) = ∏ k = 1 ∞ ( 1 1 − x 2 k − 1 ) . {\displaystyle \sum _{n=0}^{\infty }q(n)x^{n}=\prod _{k=1}^{\infty }(1+x^{k})=\prod _{k=1}^{\infty }\left({\frac {1}{1-x^{2k-1}}}\right).}

Kongruenser

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

p ( 5 k + 4 ) ≡ 0 ( mod 5 ) {\displaystyle p(5k+4)\equiv 0{\pmod {5}}\,}

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

∑ k = 0 ∞ p ( 5 k + 4 ) x k = 5   ( x 5 ) ∞ 5 ( x ) ∞ 6 {\displaystyle \sum _{k=0}^{\infty }p(5k+4)x^{k}=5~{\frac {(x^{5})_{\infty }^{5}}{(x)_{\infty }^{6}}}}

där ( x ) ∞ {\displaystyle (x)_{\infty }} är q-Pochhammersymbolen, definierad som

( x ) ∞ = ∏ m = 1 ∞ ( 1 − x m ) . {\displaystyle (x)_{\infty }=\prod _{m=1}^{\infty }(1-x^{m}).}

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

p ( 7 k + 5 ) ≡ 0 ( mod 7 ) p ( 11 k + 6 ) ≡ 0 ( mod 11 ) . {\displaystyle {\begin{aligned}p(7k+5)&\equiv 0{\pmod {7}}\\p(11k+6)&\equiv 0{\pmod {11}}.\end{aligned}}}

och för p=7 relationen

∑ k = 0 ∞ p ( 7 k + 5 ) x k = 7   ( x 7 ) ∞ 3 ( x ) ∞ 4 + 49   ( x 7 ) ∞ 7 ( x ) ∞ 8 {\displaystyle \sum _{k=0}^{\infty }p(7k+5)x^{k}=7~{\frac {(x^{7})_{\infty }^{3}}{(x)_{\infty }^{4}}}+49~{\frac {(x^{7})_{\infty }^{7}}{(x)_{\infty }^{8}}}}

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

p ( 11 3 ⋅ 13 ⋅ k + 237 ) ≡ 0 ( mod 13 ) . {\displaystyle p(11^{3}\cdot 13\cdot k+237)\equiv 0{\pmod {13}}.}

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

p ( 28995244292486005245947069 k + 28995221336976431135321047 ) ≡ 0 ( mod 29 ) . {\displaystyle p(28995244292486005245947069k+28995221336976431135321047)\equiv 0{\pmod {29}}.}

Approximationer

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

p ( n ) ∼ 1 4 n 3 exp ⁡ ( π 2 n 3 )  då  n → ∞ . {\displaystyle p(n)\sim {\frac {1}{4n{\sqrt {3}}}}\exp \left({\pi {\sqrt {\frac {2n}{3}}}}\right){\mbox{ då }}n\rightarrow \infty .}

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

p ( n ) = 1 2 2 ∑ k = 1 v k A k ( n ) d d n exp ⁡ ( π 2 3 n − 1 24 k ) {\displaystyle p(n)={\frac {1}{2{\sqrt {2}}}}\sum _{k=1}^{v}{\sqrt {k}}\,A_{k}(n)\,{\frac {d}{dn}}\exp \left({\pi {\sqrt {\frac {2}{3}}}{\frac {\sqrt {n-{\frac {1}{24}}}}{k}}}\right)}

där

A k ( n ) = ∑ 0 ≤ m < k ; ( m , k ) = 1 e π i [ s ( m , k ) − 1 k 2 n m ] . {\displaystyle A_{k}(n)=\sum _{0\,\leq \,m\,<\,k;\;(m,\,k)\,=\,1}e^{\pi i\left[s(m,\,k)\;-\;{\frac {1}{k}}2nm\right]}.}

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

p ( n ) = 1 π 2 ∑ k = 1 ∞ k A k ( n ) d d n ( 1 n − 1 24 sinh ⁡ [ π k 2 3 ( n − 1 24 ) ] ) . {\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }{\sqrt {k}}\,A_{k}(n)\,{\frac {d}{dn}}\left({{\frac {1}{\sqrt {n-{\frac {1}{24}}}}}\sinh \left[{{\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}}\right]}\right).}

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):

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

Källor

  • George E. Andrews, The Theory of Partitions (1976), Cambridge University Press. ISBN 0-521-63766-X .
  • Apostol, Tom M. (1990) [1976]. Modular functions and Dirichlet series in number theory. Graduate Texts in Mathematics. "41" (2nd). New York etc.: Springer-Verlag. ISBN 0-387-97127-0  (See chapter 5 for a modern pedagogical intro to Rademacher's formula).
  • Mall:Hardy and Wright
  • Lehmer, D. H. (1939). ”On the remainder and convergence of the series for the partition function”. Trans. Amer. Math. Soc. 46: sid. 362–373. doi:10.1090/S0002-9947-1939-0000410-9.  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.)
  • Macdonald, Ian G. (1979). Symmetric functions and Hall polynomials. Oxford Mathematical Monographs. Oxford University Press. ISBN 0-19-853530-9  (See section I.1)
  • Nathanson, M.B. (2000). Elementary Methods in Number Theory. Graduate Texts in Mathematics. "195". Springer-Verlag. ISBN 0-387-98912-9 
  • 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 ISBN 0-521-56069-1
  • Whiteman, A. L. (1956). A sum connected with the series for the partition function. "6". sid. 159–176. http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1103044252. Läst 9 december 2013  (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.
  • Miklós Bóna (2002). A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory. World Scientific Publishing. ISBN 981-02-4900-4  (qn elementary introduction to the topic of integer partition, including a discussion of Ferrers graphs)
  • George E. Andrews, Kimmo Eriksson (2004). Integer Partitions. Cambridge University Press. ISBN 0-521-60090-1 
  • 'A Disappearing Number', devised piece by Complicite, mention Ramanujan's work on the Partition Function, 2007