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.
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
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
-1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 |
Az alábbiakban ``nehezebb'' megfordítási képleteket is vizsgálunk.
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
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 3 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 4 | 6 | 4 | 1 | 0 | 0 | 0 | 0 | 0 |
1 | 5 | 10 | 10 | 5 | 1 | 0 | 0 | 0 | 0 |
1 | 6 | 15 | 20 | 15 | 6 | 1 | 0 | 0 | 0 |
1 | 7 | 21 | 35 | 35 | 21 | 7 | 1 | 0 | 0 |
1 | 8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 | 0 |
1 | 9 | 36 | 84 | 126 | 126 | 84 | 36 | 9 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
-1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | -2 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
-1 | 3 | -3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | -4 | 6 | -4 | 1 | 0 | 0 | 0 | 0 | 0 |
-1 | 5 | -10 | 10 | -5 | 1 | 0 | 0 | 0 | 0 |
1 | -6 | 15 | -20 | 15 | -6 | 1 | 0 | 0 | 0 |
-1 | 7 | -21 | 35 | -35 | 21 | -7 | 1 | 0 | 0 |
1 | -8 | 28 | -56 | 70 | -56 | 28 | -8 | 1 | 0 |
-1 | 9 | -36 | 84 | -126 | 126 | -84 | 36 | -9 | 1 |
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+...).
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:
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
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 7 | 6 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 15 | 25 | 10 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 31 | 90 | 65 | 15 | 1 | 0 | 0 | 0 |
0 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | 0 | 0 |
0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 | 0 |
0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 2 | -3 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | -6 | 11 | -6 | 1 | 0 | 0 | 0 | 0 | 0 |
0 | 24 | -50 | 35 | -10 | 1 | 0 | 0 | 0 | 0 |
0 | -120 | 274 | -225 | 85 | -15 | 1 | 0 | 0 | 0 |
0 | 720 | -1764 | 1624 | -735 | 175 | 21 | 1 | 0 | 0 |
0 | -5040 | 13068 | -13132 | 6769 | -1960 | 322 | -28 | 1 | 0 |
0 | 40320 | -109584 | 118124 | -67284 | 22449 | -4536 | 546 | -36 | 1 |
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).