Partíció (számelmélet)

Ez a szócikk a száméleti partícióról szól. Hasonló címmel lásd még: Partíció (egyértelműsítő lap).

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 ${\displaystyle 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 ${\displaystyle p_{k}(n)}$ n k tagra való felbontásainak számát. Ekkor

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

Nyilván ${\displaystyle p_{1}(n)=1}$ és ${\displaystyle p_{2}(n)=\lfloor n/2\rfloor }$. Generátorfüggvényekkel elegánsan megadhatjuk ${\displaystyle p_{3}(n)}$ értékét. Jelölje ${\displaystyle 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 ${\displaystyle a_{3}(n)=p_{3}(n+3)}$ és

${\displaystyle \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:

${\displaystyle {\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 ${\displaystyle \omega =-1/2+{\sqrt {3}}i/2}$. A sorok együtthatóit egyenlővé téve

${\displaystyle 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

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

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

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

${\displaystyle 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

${\displaystyle \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

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

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

${\displaystyle 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

${\displaystyle 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 ${\displaystyle \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

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

valamilyen pozitív ${\displaystyle 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

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

tagot tartalmaznak, tart

${\displaystyle 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