next up previous contents
Next: Generátorfüggvény és a nem Up: A nem felírható számok Previous: A nem felírható számok   Tartalomjegyzék

Partíciók és nem felírható számok

Az itt szereplő fogalmakat és eredményeket FREUD RÓBERT és GYARMATI EDIT Számelmélet [9] című egyetemi tankönyve, valamint J. RAMÍREZ ALFONSÍN összefoglaló cikke [24] alapján állítottuk össze.

Az $ n$ pozitív egész szám partícióin az $ n$ szám pozitív egészek összegeként történő lényegesen különböző előállításait értjük és ezek számát $ p(n)$-nel jelöljük. A partíciókkal kapcsolatos problémák hatékony kezelésének eszköze a generátorfüggvény. EULER megmutatta, hogy a $ p(n)$ generátorfüggvénye

$\displaystyle \prod\limits_{i=1}^{\infty}\frac{1}{1-x^i}=
1+\sum\limits_{i=1}^{\infty}p(n)x^n.
$

Jelöljük $ d(m; a_1, a_2, \ldots , a_n)$-nel az $ m=\sum\limits_{i=1}^{n}x_ia_i$ diofantoszi egyenlet megoldásainak számát, ahol $ x_i \ge 0.$ Tehát $ d(m; a_1, a_2, \ldots , a_n)$ az $ m$ pozitív egésznek az $ a_1, a_2, \ldots , a_n$ összeadandókból képzett partíciói számát jelöli. Ezt a függvényt SYLVESTER definiálta és ,,denumerant''-nak, leszámlálónak nevezte. Erre is megadható a $ p(n)$-hez hasonlóan generátorfüggvény:

$\displaystyle f(x)=1+\sum\limits_{i=1}^{\infty} d(m; a_1, a_2, \ldots , a_n)x^m =
$

$\displaystyle = \frac{1}{(1-x^{a_1})(1-x^{a_2}) \cdots (1-x^{a_n})}.
$

$ G(a_1, a_2, \ldots ,a_n)$ a legnagyobb olyan $ k$ lesz, amelyre a generátorfüggvényben az $ x^k$ együtthatója nulla. Ezt az analízisből vett szóhasználattal úgy is fogalmazhatjuk, hogy a legnagyobb olyan $ k$, amelyre a generátorfüggvény $ k$-adik deriváltja, $ f^{k}(0)=0.$ A generátorfüggvény bevezetésével és vizsgálatával számtalan aszimptotikus becslés született $ d(m; a_1, a_2, \ldots , a_n)$-re. SCHUR és NETTO vizsgálatai szerint

$\displaystyle d(m; a_1, a_2, \ldots , a_n) \thicksim \frac {m^{n-1}}{P_n(n-1)!}$     $\displaystyle \text { ha } m \to \infty,
$

ahol $ P_n$ az $ a_1, a_2, \ldots , a_n$ számok szorzata. Ez az eredmény is mutatja, hogy ha az $ m$ elegendően nagy, akkor $ d(m; a_1, a_2, \ldots , a_n)$ biztosan leg-alább $ 1$, létezik tehát a legnagyobb nem felírható szám. Jelen dolgozatban nem célunk a Frobenius problémakör és az analízis kapcsolatának részletekbe menő bemutatása. Az ebből a néhány fogalomból, gondolatból is érzékelhető, hogy érdekes, nehéz, és egyelőre sokkal több kérdést vet fel, mint amennyire az $ n > 2$ esetben sikeresnek mutatkozik.


next up previous contents
Next: Generátorfüggvény és a nem Up: A nem felírható számok Previous: A nem felírható számok   Tartalomjegyzék
root 2004-12-04