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]

  • 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 , 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]

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

Nyilván és . Generátorfüggvényekkel elegánsan megadhatjuk értékét. Jelölje n olyan 3 tagra való felbontásainak a számát, ahol 0-t is megengedjük összeadandóként. Nyilván és

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

ahol . A sorok együtthatóit egyenlővé téve

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

azt kapjuk, hogy értéke az -höz legközelebb eső egész szám, másképpen .

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

aszimptotika.

A partíciók száma[szerkesztés]

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

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

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

Bizonyításuk komplex függvénytant használt. Elemi bizonyítást adtak arra a sokkal gyengébb állításra, hogy . Erdős 1942-ben megmutatta, hogy elemi módszerekkel sokkal tovább lehet jutni: igazolni lehet, hogy

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

tagot tartalmaznak, tart

-hoz.

Partíciószám számító algoritmus[szerkesztés]

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ás[szerkesztés]

Freud-Gyarmati: Számelmélet