Heltalspartition

Från Wikipedia
Hoppa till: navigering, sök
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} och antalet ordnade k-partitioner av n är lika med \binom{n-1}{k-1}.

Exempel[redigera | redigera wikitext]

Talet 5 kan partitoneras 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

\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

\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[redigera | redigera wikitext]

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

p(5k+4)\equiv 0 \pmod 5\,

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

  \sum_{k=0}^{\infty} p(5k+4)x^k = 5~ \frac{ (x^5)^5_{\infty} } {(x)^6_{\infty}}

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

(x)_{\infty} = \prod_{m=1}^{\infty}(1-x^m).

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

\begin{align}
 p(7k + 5) &\equiv 0 \pmod 7\\
 p(11k + 6) &\equiv 0 \pmod {11}.
\end{align}

och för p=7 relationen


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

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

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

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

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

Approximationer[redigera | redigera wikitext]

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

p(n) \sim \frac {1} {4n\sqrt3} \exp\left({\pi \sqrt {\frac{2n}{3}}}\right) \mbox { då } n\rightarrow \infty.

G. H. Hardy och 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)=\frac{1}{2 \sqrt{2}} \sum_{k=1}^v \sqrt{k}\, A_k(n)\,
\frac{d}{dn} \exp \left({ \pi\sqrt{\frac23} 
    \frac{\sqrt{n-\frac{1}{24}}}{k} }
    \right)

där

A_k(n) = \sum_{0 \,\le\, m \,<\, k; \; (m,\, k) \,=\, 1}
e^{ \pi i \left[ s(m,\, k) \;-\; \frac{1}{k} 2 nm \right] }.

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

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

Källor[redigera | redigera wikitext]