Next: A nem felírható számok
Up: A nem felírható számok
Previous: Partíciók és nem felírható
Tartalomjegyzék
A lehetséges iskolai vonatkozások szempontjából kiválasztottunk
egy olyan könnyebben kezelhető részt, amely bepillantást enged a
generátorfüggvény használatának módszereibe.
Ebben a szakaszban végig csak az esetre szorítkozunk.
Legyenek és relatív prím pozitív egészek és jelölje
NR
azoknak a nemnegatív egészeknek a halmazát, amelyek nem fejezhetők ki
alakban, ahol és nemnegatív egészek. Legyen
ezeknek a nemnegatív egészeknek az összege:
NR
-t és -t is ismerjük (ld. pl. 2. fejezet 3. feladat
és 8. feladat):
Természetes felső becslést kaphatunk azonnal a nem felírható számok összegére, ha
-ig a legnagyobb
darab
egész számot, és egy alsó becslést, ha a legkisebb
pozitív egész számot vesszük:
T. C. BROWN és P. J. SHIUE [2] pontosan
meghatározták -t:
TÉTEL 5.2.1
Legyenek és relatív prím pozitív egészek. Ekkor
BIZONYÍTÁS: Jelentse az pozitív egész szám azon
alakú előállításainak számát, ahol és nemnegatív
egészek. Köny-nyen beláthatjuk, hogy ha
, akkor
vagy . Ellenkező esetben ugyanis az -et legalább kétféleképpen
előállíthatnánk, azaz
ahol az általánosság
meg-szorítása nélkül feltehetjük, hogy
Átrendezve látjuk,
hogy
Innen
, azaz
és adódna. Most definiáljuk a következő függvényt:
Mivel az csak 0-t vagy -et vehet fel, ezért
és
NR
Az függvény meghatározásához fel fogjuk használni
S. SERTÖZ és A. ÖZLÜK által [29]-ben
részletezett generátorfüggvényt:
Legyen most
és
Belátható, hogy olyan polinom, amelynek főegyütthatója
és fokszáma .
L'Hospital-szabállyal közvetlenül igazolható, hogy , így biztos, hogy
is polinom, amelynek főegyüthatója szintén
és fokszáma
A következő azonos átalakítással ki fogjuk mutatni, hogy .
Mivel tudjuk, hogy ez egy -ad fokú polinom, minden ennél
magasabb kitevőjű hatvány együtthatója nulla. Így
Hozzákezdhetünk kiszámításához. A könnyebb kezelhetőség érdekében legyen
Ezzel
Vizsgáljuk külön a számlálót és a nevezőt.
Az -et behelyettesítve
Következzenek most a és deriváltjai. Használjuk fel, hogy
Deriválva a -et
Az -et a két függvény hányadosára vonatkozó deriválási
sza-bály alapján kapjuk:
A bizonyítást két okból is részletesen tárgyaltuk.
Egyrészt látjuk, hogy legegyszerűbb esetben is magasabb segédeszközökre,
ügyes számolási technikára és menet közben több kisebb ötletre is
szükség van a nem felírható számok összegének meghatározásához.
Ezen az úton esetén átláthatalanok lesznek az egyes hatványok
együthatói, ugyanaz az a nehézség lép fel, mint az eredeti Frobenius-probléma
általános megoldása (egyelőre megoldhatatlansága) esetében.
Másrészt öszevethetjük ezt a módszert a később tárgyalandó
teljesen elemi módszerrel is.
Next: A nem felírható számok
Up: A nem felírható számok
Previous: Partíciók és nem felírható
Tartalomjegyzék
root
2004-12-04