Partíció (számelmélet)

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

  • 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 megyezik 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[szerkesztés | forrásszöveg szerkesztése]

Jelölje p_k(n) n k tagra való felbontásainak számát. Ekkor

p_k(n)=\sum^k_{s=1}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^\infty_{n=0}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^2x)}

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[szerkesztés | forrásszöveg szerkesztése]

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^\infty_{n=0}p(n)x^n=\prod^\infty_{k=1}(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[szerkesztés | forrásszöveg szerkesztése]

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) //valóban ez van a jegyzetben, de szerintem egyszerűbb P2(0,k)=0

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

• P2(n,k) = P2(n,k−1)+P2(n−k,k) ha k < n //ha a 2. sort módosítjuk, akkor itt k<=n áll

• 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ás[szerkesztés | forrásszöveg szerkesztése]

Freud-Gyarmati: Számelmélet