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ételekSzerkeszté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ásSzerkeszté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ámaSzerkeszté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ó algoritmusSzerkeszté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ásokSzerkesztés

  • Freud-Gyarmati: Számelmélet