Megfordítási képletek

 

Legyen N egy n elemű halmaz és K egy k elemű halmaz. Képezzük az összes N->K függvény halmazát, illetve csupán a szürjektív függvények halmazát. A két függvényhalmaz elemszáma legyen össz(n,k), illetve szürj(n,k). Rögzítsük le n-et és k-t változtassuk. így két sorozathoz jutunk. A két sorozat között egyszerű kapcsolat van. {szürj(n,0), szürk(n,1), szürj(n,2), ...} ismeretében {össz(n,0), össz(n,1), össz(n,2), ...} könnyen meghatározható: össz(n,k)=+{(nl)szürj(n,l): l=0,1,...,k}.

Vajon a fenti kapcsolat megfordítható-e? Azaz {össz(n,0), össz(n,1), össz(n,2), ...} ismeretében {szürj(n,0), szürk(n,1), szürj(n,2), ...} könnyen meghatározható-e? Ha igen, akkor szürj(n,k)=k!S(n,k)-ra formulát is nyerünk, hiszen tudjuk, hogy össz(n,k)=kn.

Sok hasonló sorozatok közötti származtatási szabály esetén felvethető hasonló kérdés. Ha igen, akkor milyen szabály, képlet alapján? Ha létezik ilyen képlet, akkor megfordítási képletnek nevezzük. Az alábbiakban néhány megfordítási képletet vizsgálunk.

 
 
I
 

A legegyszerűbb megfordítási képlet: Legyen {ai} egy sorozat. Ebből a következő szabályok szerint definiáljuk a {bi} sorozatot: b0=a0, b1=a0+a1, b2=a0+a1+a2,... Azaz a {bi} sorozat az {ai} sorozat első néhány tagjainak összegeiből alkotott sorozat.

Könnyen látható, hogy van megfordítási képlet és ez az ai=bi-bi-1 képlet (képletsorozat, hiszen i=0,1,2,...).

Tétel: Legyen {ai} és {bi} két sorozat. Ekkor a következők ekvivalensek.

(i) Minden i természetes számra bi=a0+a1+a2+...+ai, azaz például i=0 esetén b0=a0,

(ii) minden i természetes számra ai=bi-bi-1.

Bizonyítás: Könnyen meggondolható.

Következmény: (x(i>=j): i=0,1,2,...,n és j=0,1,2,...,n) mátrix inverze (ahol x(i>=j) az i>=j reláció karakterisztikusfüggvé;nye, azaz x(i>=j)=1 akkor és csak akkor, ha i>=j, és x(i>=j)=0 akkor és csak akkor, ha i < j) (y(i,j): i=0,1,2,...,n és j=0,1,2,...,n) mátrix (ahol y(i,j)=1 akkor és csak akkor, ha i=j, y(i,j)=-1 akkor és csak akkor, ha i = j-1, és minden más esetben y(i,j)=0). Például a
1000000000
1100000000
1110000000
1111000000
1111100000
1111110000
1111111000
1111111100
1111111110
1111111111
mátrix inverze a
 
1000000000
-1100000000
0-110000000
00-11000000
000-1100000
0000-110000
00000-11000
000000-1100
0000000-110
00000000-11
mátrix.

Az alábbiakban ``nehezebb'' megfordítási képleteket is vizsgálunk.

 
 
II
 
Legyen {ai} egy sorozat és ebből egy {bi} sorozatot képezünk úgy, hogy bi=(i0)a0+(i1)a1+...+(ii)ai (i=0,1,2,3,...). Hogyan fordítható meg ez a képlet, azaz a {bi} sorozat ismeretében hogyan számolható ki az {ai} sorozat? Kis indexek esetén a megfordítási képlet léte könnyen ellenőrizhető, a képlet könnyen felírható: a0=b0, a1=b1-b0, a2=b2-2b1+b0, a3=b3-3b2+3b1-b0. Ezekből a kezdeti értékekből könnyen megsejthető egy általános képlet.

Tétel: A {ai} és {bi} sorozatok között az alábbi két kapcsolat ekvivalens:

(i) minden i természetes számra bi=(i0)a0+(i1)a1+...+(ii)ai,

(ii) minden i természetes számra ai=(ii)bi-(ii-1)bi-1+...+(-1)i(i0)a0. A tétel könnyen igazolható teljes indukcióval. Mi egy másik jóval absztraktabb, operátorokat használó bizonyítást is ismertetünk.

Következmény: ((ij): i=0,1,2,...,n és j=0,1,2,...,n) mátrix inverze a ((-1)i+j(ij): i=0,1,2,...,n és j=0,1,2,...,n) mátrix. Például a
1000000000
1100000000
1210000000
1331000000
1464100000
151010510000
1615201561000
17213535217100
182856705628810
193684126126843691
mátrix inverze a
 
1000000000
-1100000000
1-210000000
-13-31000000
1-46-4100000
-15-1010-510000
1-615-2015-61000
-17-2135-3521-7100
1-828-5670-5628-810
-19-3684-126126-8436-91
mátrix.

Következmény:

(i) szürj(n,k)=össz(n,k)-(kk-1)össz(n,k-1) -(kk-2)össz(n,k-2)-(kk-3)össz(n,k-3) -(kk-4)össz(n,k-4)-(kk-5)össz(n,k-5)+...

(ii) S(n,k)=1/k!(kn-(kk-1)(k-1)n -(kk-2)(k-2)n+(kk-3)(k-3)n -(kk-4)(k-4)n-(kk-5)(k-5)n+...).

 
 
III
 

Az első- és másodfajú Stirling-számok órán tárgyalt két generátor függvénye között formális hasonlóság van. Ez a hasonlóság matematikailag is pontossá tehető. Így egy újabb megfordítási képlethez jutunk.

A legfeljebb d-ed fokú polinomok vektorteret alkotnak. A vektortér dimenziója d+1. Ennek igazolása legegyszerűbb módon úgy történik, hogy megadunk egy d+1 elemű bázist, azaz polinomok egy lineárisan független halmazát, amelyekből minden más polinom (legfeljebb d-ed fokú) kikombinálható.

A standard bázis: B={1,x,x2,...,xd}

Más bázisok is megadhatók. Néhány példa mutatóba:

Ezek bázis volta könnyen ellenőrizhető.

Két bázis esetén definiálható az egyikről a másikra való áttérés mátrixa. Ez a mátrix az egyik bázis másik bázisban történő felírásának (mindegyik bázis elemet felírunk, mint a másik bázis elemeinek lineáris kombinációja) együtthatóit tartalmazó mátrix. Két bázis esetén két átmeneti mátrix van. Könnyen meggondolható, hogy a két átmeneti mátriz egymás inverze.

Következmény: ((S(i,j): i=0,1,2,...,n és j=0,1,2,...,n) mátrix inverze a (s(i,j): i=0,1,2,...,n és j=0,1,2,...,n) mátrix. Például a
1000000000
0100000000
0110000000
0131000000
0176100000
0115251010000
01319065151000
016330135014021100
01127966170110502662810
012553025777069512646462361
mátrix inverze a
 
1000000000
0100000000
0-110000000
02-31000000
0-611-6100000
024-5035-1010000
0-120274-22585-151000
0720-17641624-73517521100
0-504013068-131326769-1960322-2810
040320-109584118124-6728422449-4536546-361
mátrix.

Tehát az átmeneti mátrixok invertálhatóak, nem elfajulóak. Ez az állítás meg fordítható. Ha egy dimenzió elemszámú vektorhalmaz (esetünkben polinomhalmaz) egy adott bázisban történő felírásának mátrixa invertálható, akkor a vektorhalmaz bázist alkot. A fenti példák esetén több átmeneti mátrix alsó trianguláris mátrix nem nulla elemekkel a főátlón. Ez alapján is bizonyítható bázis voltuk.

B és B(1) esetén a két átmeneti mátrix az első fajú, illetve másodfajú Striling-számokat tartalmazó mátrixok. Ezek tehát egymás inverzei.

Ennek egy másik megfogalmazása egy megfordítási képlet:

Tétel: Legyen {ai:i=0,1,...} és {bi:i=0,1,...} két sorozat ekkor a következő két összefüggés ekvivalens. (i) an=adjuk össze az {s(n,k)bk:k=0,1,...,n} számokat, (ii) bn=adjuk össze az {S(n,k)ak:k=0,1,...,n} számokat.

A két sorozat közti összefüggéseket mátrix alakba írva egyszerű mátrix aritmetikával adódik azeredmény (felhasználva a korábbi invertálhatósági összefüggést).