next up previous contents
Next: A nem felírható számok Up: A nem felírható számok Previous: Partíciók és nem felírható   Tartalomjegyzék

Generátorfüggvény és a nem felírható számok összege

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 $ n=2$ esetre szorítkozunk.

Legyenek $ a$ és $ b$ relatív prím pozitív egészek és jelölje NR$ (a, b)$ azoknak a nemnegatív egészeknek a halmazát, amelyek nem fejezhetők ki $ xa+yb$ alakban, ahol $ x$ és $ y$ nemnegatív egészek. Legyen $ S(a, b)$ ezeknek a nemnegatív egészeknek az összege:

$\displaystyle S(a, b)=\sum\{n: n \in$   NR$\displaystyle (a, b)\}.$

$ G(a, b)$-t és $ N(a, b)$-t is ismerjük (ld. pl. 2. fejezet 3. feladat és 8. feladat):

$\displaystyle G(a, b)=ab-a-b=(a-1)(b-1)-1,$        $\displaystyle N(a, b)=\frac{(a-1)(b-1)}{2}. $

Természetes felső becslést kaphatunk azonnal a nem felírható számok összegére, ha $ (ab-a-b)$-ig a legnagyobb $ \frac{(a-1)(b-1)}{2}$ darab egész számot, és egy alsó becslést, ha a legkisebb $ \frac{(a-1)(b-1)}{2}$ pozitív egész számot vesszük:

$\displaystyle \frac{1}{8}(a-1)^2(b-1)^2+\frac{1}{4}(a-1)(b-1) \le S(a, b)
$

$\displaystyle S(a, b) \le \frac{3}{8}(a-1)^2(b-1)^2-\frac{1}{4}(a-1)(b-1).
$

T. C. BROWN és P. J. SHIUE [2] pontosan meghatározták $ S(a, b)$-t:

TÉTEL 5.2.1   Legyenek $ a$ és $ b$ relatív prím pozitív egészek. Ekkor

$\displaystyle S(a, b)=\frac{1}{12}(a-1)(b-1)(2ab-a-b-1).$

BIZONYÍTÁS: Jelentse $ r(n)$ az $ n$ pozitív egész szám azon $ n=xa+yb$ alakú előállításainak számát, ahol $ x$ és $ y$ nemnegatív egészek. Köny-nyen beláthatjuk, hogy ha $ n \le ab-1$, akkor $ r(n)=0$ vagy $ r(n)=1$. Ellenkező esetben ugyanis az $ n$-et legalább kétféleképpen előállíthatnánk, azaz $ n=x_1a+y_1b=x_2a+y_2b,$ ahol az általánosság meg-szorítása nélkül feltehetjük, hogy $ x_1 > x_2.$ Átrendezve látjuk, hogy $ 0=(x_1-x_2)a+(y_1-y_2)b.$ Innen $ b \mid x_1-x_2$, azaz $ x_1 \ge b$ és $ n \ge ab$ adódna. Most definiáljuk a következő függvényt:

$\displaystyle f(x)=\sum_{n=0}^{ab-a-b}[1-r(n)]x^n.$

Mivel az $ r(n)$ csak 0-t vagy $ 1$-et vehet fel, ezért

$\displaystyle f'(1)=\sum_{n=0}^{ab-a-b}n[1-r(n)]=
\sum \{n: 1 \le n \le ab-a-b$    és $\displaystyle r(n)=0\}
$

$\displaystyle =\sum \{n: n \in$   NR$\displaystyle (a, b)\}=S(a, b).
$

Az $ f(x)$ 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:

$\displaystyle T(x)=\frac{1}{(1-x^a)(1-x^b)}=
\left(\sum_{n=0}^{\infty}x^{an}\right)\left(\sum_{n=0}^{\infty}x^{bn}\right)=
\sum_{n=0}^{\infty}r(n)x^n.
$

Legyen most

$\displaystyle P(x)=\frac {(x^{ab}-1)(x-1)}{(x^a-1)(x^b-1)}$    és  $\displaystyle f^*(x)=\frac {P(x)-1}{x-1}.
$

Belátható, hogy $ P(x)$ olyan polinom, amelynek főegyütthatója $ 1$ és fokszáma $ ab-a-b+1$. L'Hospital-szabállyal közvetlenül igazolható, hogy $ P(1)=1$, így biztos, hogy $ \frac{P(x)-1}{x-1}$ is polinom, amelynek főegyüthatója szintén $ 1$ és fokszáma $ ab-a-b.$

A következő azonos átalakítással ki fogjuk mutatni, hogy $ f=f^*$.

$\displaystyle f^*(x)=\frac{P(x)-1}{x-1}=\frac{P(x)}{x-1}+\frac{1}{1-x}=(x^{ab}-1)T(x)+\frac{1}{1-x}=
$

$\displaystyle =\sum_{n=0}^{\infty}r(n)x^{ab+n}+\sum_{n=0}^{\infty}[1-r(n)]x^n=
$

$\displaystyle =\sum_{n=ab}^{\infty}[r(n-ab)+1-r(n)]x^n+\sum_{n=0}^{ab-1}[1-r(n)]x^n.
$

Mivel tudjuk, hogy ez egy $ (ab-a-b)$-ad fokú polinom, minden ennél magasabb kitevőjű hatvány együtthatója nulla. Így

$\displaystyle f^*(x)=\frac{P(x)-1}{x-1}=\sum_{n=0}^{ab-a-b}[1-r(n)]x^n=f(x).$

Hozzákezdhetünk $ f'(1)$ kiszámításához. A könnyebb kezelhetőség érdekében legyen $ y=x^a.$ Ezzel

$\displaystyle P(x)=\frac {(x^{ab}-1)(x-1)}{(x^a-1)(x^b-1)}=\frac{\sum\limits_{k=0}^{b-1}y^k}{\sum\limits_{k=0}^{b-1}x^k}.
$

$\displaystyle f(x)=\frac{P(x)-1}{x-1}=
\frac{\sum\limits_{k=0}^{b-1}y^k-\sum\li...
...k=1}^{b-1} \frac{y^k-x^k}{x-1}}{\sum\limits_{k=0}^{b-1}x^k}=\frac{g(x)}{h(x)}.
$

Vizsgáljuk külön a számlálót és a nevezőt.

$\displaystyle g(x)=\sum_{k=0}^{b-1}\frac{y^k-x^k}{x-1}=\sum_{k=0}^{b-1}\frac {x^{ak}-x^k}{x-1}=
\sum_{k=1}^{b-1}(x^k+x^{k+1}+ \ldots +x^{ak-1}).
$

Az $ 1$-et behelyettesítve

$\displaystyle g(1)=\sum_{k=1}^{b-1}(a-1)k=\frac{1}{2}(a-1)(b-1)b,$     $\displaystyle h(1)=b.
$

Következzenek most a $ g(x)$ és $ h(x)$ deriváltjai. Használjuk fel, hogy

$\displaystyle k+(k+1)+ \ldots +(ka-1)=\frac{1}{2}ka(ka-1)-\frac{1}{2}k(k-1)=
$

$\displaystyle =\frac{1}{2}(k^2(a^2-1)-k(a-1)).
$

Deriválva a $ g(x)$-et

$\displaystyle g'(1)=\sum\limits_{k=1}^{b-1}(k+(k+1)+ \ldots +(ka-1))=
$

$\displaystyle =\sum\limits_{k=1}^{b-1}\frac{1}{2}(k^2(a^2-1)-k(a-1)=
$

$\displaystyle =\frac{1}{2}(a^2-1)\sum\limits_{k=1}^{b-1}k^2-\frac{1}{2}(a-1)\sum\limits_{k=1}^{b-1}k=
$

$\displaystyle =\frac{1}{2}(a^2-1)\frac{1}{6}(b-1)b(2b-1)-\frac{1}{2}(a-1)\frac{1}{2}(b-1)b=
$

$\displaystyle =b(a-1)(b-1)\left(\frac{(a+1)(2b-1)}{12}-\frac{1}{4}\right).
$

$\displaystyle h'(1)=1+2+ \ldots +(b-1)=\frac{1}{2}(b-1)b.
$

Az $ f'(1)$-et a két függvény hányadosára vonatkozó deriválási sza-bály alapján kapjuk:

$\displaystyle S(a, b)=f'(1)=\frac{h(1)g'(1)-g(1)h'(1)}{(h(1))^2}=
$

$\displaystyle =\frac{b^2(a-1)(b-1)\left(\frac{(a+1)(2b-1)}{12}-\frac{1}{4}\right)
-\frac{1}{4}b^2(a-1)(b-1)^2}{b^2}=
$

$\displaystyle =\frac{1}{12}(a-1)(b-1)((a+1)(2b-1)-3-3(b-1))=
$

$\displaystyle =\frac{1}{12}(a-1)(b-1)(2ab-a-b-1).
\blacksquare
$

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 $ n > 2$ 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 up previous contents
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