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
|
---|
Képlet alapján | |
---|
Számsorozat alapján | |
---|
Tulajdonság alapján | |
---|
Számrendszerfüggő | |
---|
Mintázatok |
- Iker (p, p + 2)
- Ikerprímlánc (n − 1, n + 1, 2n − 1, 2n + 1, …)
- Prímhármas (p, p + 2 vagy p + 4, p + 6)
- Prímnégyes (p, p + 2, p + 6, p + 8)
- prím n−es
- Unokatestvér (p, p + 4)
- Szexi (p, p + 6)
- Chen
- Sophie Germain (p, 2p + 1)
- Cunningham-lánc (p, 2p ± 1, …)
- Biztonságos (p, (p − 1)/2)
- Számtani sorozatban (p + a·n, n = 0, 1, …)
- Kiegyensúlyozott (egymást követő p − n, p, p + n)
|
---|
Méret alapján | |
---|
Komplex számok | |
---|
Összetett számok | |
---|
Kapcsolódó fogalmak | |
---|
Az első 100 prím | |
---|
|