Partíció (számelmélet)

A jelenlegi kontextusban a Partíció (számelmélet) olyan téma, amely nagyon fontos és sok ember számára érdekes. A Partíció (számelmélet) jelentősége az idő múlásával egyre nyilvánvalóbbá vált, mivel hatása a mindennapi élet különböző aspektusait fedi le. A társadalomra gyakorolt ​​befolyásától a szakmai téren való jelentőségéig a Partíció (számelmélet) számos területen kiemelkedő szerepet játszott. Ezért kulcsfontosságú, hogy mélyebben elmélyedjünk a Partíció (számelmélet) elemzésében, hogy jobban megértsük hatókörét és mai vonatkozásait. Ebben a cikkben a Partíció (számelmélet) különböző perspektíváit vizsgáljuk meg, kitérve annak számos aspektusára és a különböző kontextusokra gyakorolt ​​hatására.

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

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

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)

Források

  • Freud-Gyarmati: Számelmélet