Partíció (számelmélet)

A számelméletben egy szám partíciójának természetes számok összegére való felbontását nevezzük. Figyelembe vesszük az egy tagból álló összeget is. Két partíció azonos, ha azok csak a tagok sorrendjében térnek el.

Így 5 partíciói: 1+1+1+1+1 = 2+1+1+1 = 3+1+1 = 2+2+1 = 4+1 = 3+2 = 5.

Speciális partíciókra vonatkozó tételek

• Az n szám r-nél nem több tagú partícióinak száma megegyezik n azon partícióinak számával, ahol minden tag legfeljebb r nagyságú.
• Az n szám pontosan m tagú partícióinak száma megegyezik az n-m szám m-nél nem több tagú partícióinak számával.
• Az n különböző tagokra való partícióinak száma megegyezik n páratlan sok tagú partícióinak számával.
• (Ötszögszámok tétele) Ha $n\neq {\frac {3k^{2}\pm k}{2}}$, akkor n páratlan sok tagból álló partícióinak száma megegyezik páros sok tagból álló partícióinak számával.

Adott számú tagra való bontás

Jelölje $p_{k}(n)$ n k tagra való felbontásainak számát. Ekkor

$p_{k}(n)=\sum _{s=1}^{k}p_{s}(n-k).$

Nyilván $p_{1}(n)=1$ és $p_{2}(n)=\lfloor n/2\rfloor$. Generátorfüggvényekkel elegánsan megadhatjuk $p_{3}(n)$ értékét. Jelölje $a_{3}(n)$ n olyan 3 tagra való felbontásainak a számát, ahol 0-t is megengedjük összeadandóként. Nyilván $a_{3}(n)=p_{3}(n+3)$ és

$\sum _{n=0}^{\infty }a_{3}(n)x^{n}={\frac {1}{(1-x)(1-x^{2})(1-x^{3})}}.$

A jobb oldal így bontható parciális törtekre:

${\frac {1}{6(1-x)^{3}}}+{\frac {1}{4(1-x)^{2}}}+{\frac {17}{72(1-x)}}+{\frac {1}{8(1+x)}}+{\frac {1}{9(1-\omega x)}}+{\frac {1}{9(1-\omega ^{2}x)}}$

ahol $\omega =-1/2+{\sqrt {3}}i/2$. A sorok együtthatóit egyenlővé téve

$a_{3}(n)={\frac {(n+3)^{2}}{12}}-{\frac {7}{72}}+{\frac {(-1)^{n}}{8}}+{\frac {2}{9}}\cos \left({\frac {2n}{3}}\pi \right)$

adódik. Mivel a három utolsó tag összege legfeljebb

${\frac {7}{72}}+{\frac {1}{8}}+{\frac {2}{9}}<{\frac {1}{2}},$

azt kapjuk, hogy $p_{3}(n)$ értéke az $n^{2}/12$-höz legközelebb eső egész szám, másképpen $\lfloor (n^{2}+6)/12\rfloor$.

Általában minden k-ra teljesül a

$p_{k}(n)\sim {\frac {n^{k-1}}{k!(k-1)!}}\quad (n\to \infty )$

aszimptotika.

A partíciók száma

Az n szám partícióinak számát p(n)-nel jelöljük. A fentiek szerint p(5)=7. Legyen p(0)=1. Ekkor p(n) generátorfüggvénye

$\sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }(1-x^{k})^{-1}$

Rámánudzsan számos oszthatósági relációt igazolt p(n)-re, például, hogy

$p(5m+4)\equiv 0{\pmod {5}}$

$p(7m+5)\equiv 0{\pmod {7}}$

$p(11m+6)\equiv 0{\pmod {11}}$

p(n)-re aszimptotikát először 1918-ban adott G. H. Hardy és Rámánudzsan. Belátták, hogy

$p(n)\sim {\frac {1}{4n{\sqrt {3}}}}e^{\pi {\sqrt {2n/3}}}.$

Bizonyításuk komplex függvénytant használt. Elemi bizonyítást adtak arra a sokkal gyengébb állításra, hogy $\log p(n)\sim \pi {\sqrt {2n/3}}$. Erdős 1942-ben megmutatta, hogy elemi módszerekkel sokkal tovább lehet jutni: igazolni lehet, hogy

$p(n)\sim {\frac {a}{n}}e^{\pi {\sqrt {2n/3}}}$

valamilyen pozitív $a$-ra. Erdős és Lehmer azt is igazolta, hogy tetszőleges valós x-re azon partíciók száma, amelyek kevesebb, mint

${\frac {1}{\pi }}{\sqrt {3n/2}}\log n+x{\sqrt {n}}$

tagot tartalmaznak, tart

$e^{-{\frac {\sqrt {6}}{\pi }}e^{-\pi {\sqrt {x/6}}}}$

-hoz.

Partíciószám számító algoritmus

Jelölje P2(n,k) n azon partícióinak számát, amelyben minden elem legfeljebb k. Ekkor a következő összefüggések teljesülnek:

• P2(1,k) = 1,P2(n,1) = 1

• P2(n,n) = 1+P2(n,n−1)

• P2(n,k) = P2(n,n) ha n < k

• P2(n,k) = P2(n,k−1)+P2(n−k,k) ha k < n

• A megoldás: P(n) = P2(n,n)

PARTÍCIÓ(n)

Return P2(n,n)

P2(n,k)

If (k=1) Or (n=1) return 1

If k>=n return P2(n,n-1)+1

return P2(n, k-1)+P2(n-k, k)

[1]

Források

• Freud-Gyarmati: Számelmélet