Cím: Gauss-féle binomiális együtthatók, II.rész (fordította Surányi János)
Szerző(k):  Pólya György 
Füzet: 1973/január, 3 - 7. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Gauss-féle binomális együtthatók*
 

II. rész
 

Megismertük 1, a következő összefüggésekkel definiált Gauss-binomiális együtthatókat:
[nr]=(qn-1)(qn-1-1)⋅...⋅(qn-r+1-1)(q-1)(q2-1)⋅...⋅(qr-1)1≤r≤n,[n0]=1.(1.1)
Írjuk n-et n=r+s alakban. Beláttuk a 3. pontban, hogy ezek a kifejezések q-nak pozitív egész együtthatós polinomjai:
[r+sr]=Ar+s,r,0+Ar+s,r,1q+...+Ar+s,r,rsqrs.(3.2')

A 4. pont tétele az ott értelmezett zegzugos utakkal való következő összefüggést mondta ki: Ar+s,r,αa(0,0) pontból az (r,s) pontba vezető zegzugos utak közül azoknak a száma, amelyek alatti terület α.
 
 

Az 5. pontban a zegzugos utat r darab, egymás mellé helyezett egységnyi alapú téglalapból építettük fel. Ezek alapja vízszintes, magasságuk nem-negatív és s-nél nem nagyobb egész szám; a 0 magasság is előfordulhat. Az alapok a pozitív x tengely mentén sorakoznak a kezdőponttól kezdve, a magasságok nem csökkenő sorozatot alkotnak, és a területek összege (vagy ami ugyanaz, a magasságoké) α, a zegzugos út alatti terület.
 

6. Egy újabb megközelítési mód. Azoknak a zegzugos utaknak a száma, amelyek alatti terület α, megegyezik tehát α-nak r darab nem-negatív egész összeadandóként való előállításai számával. Jelöljük most ezt az előállításszámot Ar+s,r,α-val, elfelejtve egyelőre ennek a jelnek korábbi, fent is használt jelentését.
Egy szám előállítását bizonyos típusú összeadandókból a szám egy particiójának nevezzük. Ezek elméletének alapjait Euler fektette le. 6 Itt az összeadandók nem csökkenő sorrendben következnek, tehát egy előállítás meg van határozva azzal, ha tudjuk, hogy melyik számok szerepelnek összeadandóként és melyik hányszor. Ha tehát pl. a 3 kétszer szerepel egy összegben, azt a 6, 2 számpárral jelölhetjük: a második mutatja, hogy az első szám hány összeadandó összegének tekintendő a particióban.
 

Ilyen módon, ha egy particióban a 0,1,2,...,s összeadandók szerepelhetnek csak, akkor ezek mindegyikéhez számpárok egy-egy végtelen sorozatát kell hozzárendelnünk. A párok elemeit egymás alá írva a 0,1,2,...,s-hez sorra a következő sorozatok tartoznak:
 

  0    0   0  ...  0  ...  0    1    2   n   0    1   2  ... n   ...  0    1    2 n   0    2   4...2n   ...  0    1   2   n   ..........0  s   2s   ...ns   ...  0    1   2   n
Mindegyik sorozatból ki kell vennünk egy-egy párt (ha valamelyik összeadandó nem szerepel egy particióban, akkor a sorozat elején álló (0,0) párt), a megfelelő elemeiket összeadni, és ahányféléképpen létrejön ilyen módon az (α,r) pár, ez a szám adja meg az α szám r-tagú particióinak a számát, ha a tagok s-nél nem nagyobb, nem-negatív egész számok lehetnek, és sorrendjük elő van írva (nem csökkenő).
 

Ezeket a pár-sorozatokat két változó, mondjuk q és x végtelen polinomjaival helyettesíthetjük. Az első elemek sorozatát írjuk q kitevőiként, a másodikat x kitevőjéül. A polinomok tehát
1+x+x2x2+...+xn+...1+qx+q2x2+...+qnxn+...1+q2x+q4x2+...+q2nxn+.......................................1+qsx+q2sx2+...+qsnxn+...
(Az első sorozatban q mindenütt a 0-dik hatványon szerepel.) Ha ezeket összeszorozzuk, akkor minden polinomból kell venni egy-egy tagot, összeszorozni, és ezek összege adja a szorzatpolinomot. Egy ilyen tag képzésénél viszont külön összeadjuk a q-hatványok kitevőit, külön az x-hatványok kitevőit. Ez megegyezik az előbb a párok összeadásáról mondottakkal. Így a szorzatban qαxr együtthatója Ar+s,r,α lesz.
 

Másrészt az első polinom 1/(1-x)-nek polinom-alakja, a többi pedig ebből x helyett qx-et, q2x-et, ..., qsx-et téve adódik. Így, bevezetve a következő jelölést:
(1-x)(1-qx)(1-q2x)...(1-qsx)=g(x),(6.1)
azt nyertük, hogy
1+(Ar+s,1,0+Ar+s,1,1q+...+Ar+s,1,sqs)x+(6.2)+(Ar+s,2,0+Ar+s,2,1q+...+Ar+s,2,2sq2s)x2++...+(Ar+s,n,0+...+Ar+s,n,nsqns)xn+...=1g(x).


Jelöljük itt xr együtthatóját Pr-rel, vagyis
P0=1,(6.3)Ar+s,r,0+Ar+s,r,1q+...+Ar+s,r,rsqrs=Pr,har≥1.


Ekkor (6.2) így írható:
1g(x)=P0+P1x+...+Prx'+...(6.4)

A Pr együtthatók előállítása a célunk. Ehhez felhasználhatjuk a (6.1)-ből közvetlenül adódó következő azonosságot:
1-xg(x)=1-qs+1xg(qx)(6.5)
(vesd össze (2.4)-gyel. I. rész, 98. old.) és figyelembe véve (6.4)-et
(1-x)(1+P1x+...+Prxr+...)=(6.6)=(1-qs+1x)(P0+P1qx+...+Prqrxr+...).


Az egyenlő x-hatványok együtthatóit egybevetve innen adódik, hogy
Pr-Pr-1=qrPr-qr+sPr-1(6.7)
vagy
Pr=qr+s-1qr-1Pr-1,har=1,2,3,...(6.8)
Alkalmazzuk ismételten (6.8)-at r csökkenő értékeire, ekkor az (1.1) definíció és (6.3) alapján azt nyerjük, hogy
Pr=[r+sr]=Ar+s,r,0+Ar+s,r,1q+...+Ar+s,r,rsqrs,(6.9)
ahol most Ar+s,r,α a szóban forgó partició-probléma megoldásainak a számát jelenti, s így a bevezetőben említettek szerint azoknak a zegzugos utaknak a számát is, amelyek alatt α nagyságú terület van. Ezzel újabb bizonyítást is kaptunk a 4. pont tételére.
Ellenőrzésül jegyezzük meg, hogy ha q tart 1-hez, (6.4) a következőbe megy át: 7
1(1-x)s+1=1+(s+11)x+(s+22)x2+...+(s+rr)xr+...(6.4*)

Pr kiszámítása ebben a pontban rendkívül hasonlít Qr, kiszámításához a 2. pontban. Most azonban An,r,α egy kombinatorikus értelmezéséből indultunk ki és ebből jutottunk el a formulához, míg a 4. pontban An,r,α-t mint a (3.2), [ill. (3.2')] formulában fellépő együtthatót definiáltuk és utólag igazoltuk a kombinatorikus értelmét.
 

7. Rövid kitekintés ,,Gauss-féle polinomiális együtthatókra''. 8 Legyen n nem-negatív egész szám és definiáljuk a ,,Gauss-féle faktoriálist'' mint q következő polinomját:
n!!=(q-1)(q2-1)⋅...⋅(qn-1)(q-1)n=(7.1)1⋅(1+q)(1+q+q2)⋅...⋅(1+q+...+qn-1)==Bn,0+Bn,1q+...+Bn,n(n-1)/2qn(n-1)/2.


Ennek Bn,i együtthatói nem-negatív egész számok, foka n(n-1)/2. Definiálhatjuk n!!-t a
0!!=1(7.2)
kezdeti feltétellel és a következő rekurzív formulával is:
(n+1)!!=(1+q+...+qn)n!!(7.3)

Tekintsünk egy n betűből álló ABC-t és az ebben n különböző betűvel leírható ,,szavakat''. Ezek száma nyilvánvalóan n!. Minden ilyen szóban n(n-1)/2 betűpár lép fel; akkor mondjuk, hogy egy ilyen pár inverziót alkot, ha az ABC-sorrendben előbbi betű a szóban hátrább áll. Ekkor Bn,i az n! szó (permutáció) közül azoknak a száma, amelyekben az inverziók száma9 i.
Ez könnyen látható teljes indukcióval a (7.3) rekurziós formula alapján. Vegyünk hozzá a szót alkotó n betűhöz egy új betűt, és ez előzze meg mindegyiket az ABC-sorrendben. Aszerint, hogy az új betű az első, második, harmadik, ..., vagy végül az utolsó helyen áll, az inverziók száma 0-val, 1-gyel, 2-vel, n-nel nő. Pontosan ennek felel meg az, hogy (7.3)-ban az első tényező első, második, harmadik, ..., utolsó tagjával szorozva, q kitevője 0-val, 1-gyel, 2-vel, ..., n-nel nő.
Akár a (7.1) definiáló formulából, akár a kombinatorikus jelentésből következik, hogy
Bn,i=Bn,n(n-1)/2-i,i=0,1,...,n(n-1)/2(7.4)Bn,0+Bn,1+...+Bn,n(n-1)/2=n!.(7.5)



A Gauss-binomiális együtthatókat írhatjuk ilyen alakban:
[nr]=n!!r!!(n-r)!!.(7.6)
Ekkor a többtagúak hatványaiban fellépő polinomiális együtthatók egy Gauss-féle analogonja (háromtagúak esetére)
n!!r!!s!!t!!,(7.7)
ahol r+s+t=n és n, r, s, t nem-negatív egészek; megmutatható, hogy (7.7) is pozitív egész együtthatós polinomja q-nak, fokszáma rs+rt+st. Az együtthatóknak itt is lehet kombinatorikus jelentést tulajdonítani: olyan n-betűből álló sorozatok számát adják meg, amelyek minden betűje x, y, vagy z és amelyekben bizonyos inverziók száma adott érték. Minden ilyen betűsorozat tekinthető a háromdimenziós rácsban egy-egy zegzugos út képviselőjének is. Az inverziószám három terület összegével egyezik meg: a zegzugos útnak a koordinátasíkokon való vetületei alatti területek összegével, de az ,,alatt'' értelmezésével óvatosnak kell lenni.
A még több tagúak hatványaiban fellépő együtthatók Gauss-féle megfelelői hasonlóan értelmezhetők. Ezek is q polinomjai, és a bennük fellépő együtthatók is bizonyos betűsorozatok inverziószámaival vannak kapcsolatban; területekkel kapcsolatos értelmezésük is lehetséges, de nehézkessé válik a dimenziószám növekedésével.
*Megjelent az Elemente der Mathematik 26 (1971), 102‐109. oldalán. Fordította a K. M. L. céljára módosításokkal Surányi János.

1*Pólya György: Gauss-féle binomiális együtthatók, I. rész, K. M. L. 45 (1972), 97‐102. old.

6Leonhard Euler: Introductio in Analisin Infinitorum (Lausanne 1784) 1. köt., 253‐275. old., vagy: Összegyűjtött művei 1. sorozat 8. köt., 313‐338. A szükséges előzmények megtalálhatók Surányi J.: Polinomok és végtelen polinomok II. rész c. cikkében. K. M. L. 45 (1972), 193‐202. old.

7Lásd pl. Surányi János: Polinomok és végtelen polinomok I. rész, K. M. L. 45 (1972), 115. old.

8Kettőnél több tagúak hatványainak tagokra bontott alakját megadhatjuk a következő gondolatmenet alapján: (x+y+z)5-ben pl. x2yz2 alakú tagot úgy kapunk, hogy a hatványt kiírva 5 tényező szorzataként, két tényezőből az x-et, egyből az y-t, kettőből a z-t választjuk ki. Egy ilyen kiválasztást aláhúzással jelölhetünk ki:

(x̲+y+z)(x+y+z̲)(x+y+z̲)(x+y̲+z)(x̲+y+z).
Az aláhúzott tagok a tényezők sorrendjében véve az xxyzz betűk egy permutációját (esetünkben az xzzyx permutációt) adják. Az x2yz2 tag együtthatója (x+y+z)5 tagokra bontott alakjában eszerint ezeknek a permutációknak a száma lesz: 5!/(2!1!2!)=30.
Hasonlóan (x+y+z)n-ben xryszt együtthatója, ha r+s+t=n, ez lesz: n!/(r!s!t!), és általában (x1+x2+...+xk)n-ben, ha t1+t2+...+tk=n, az
x1t1x2t2...xktk
tag a következő együtthatóval szerepel: n!/(t1!t2!...tk!). Ezeket a számokat nevezzük polinomiális együtthatónak.

9Lásd pl, a 4 alatt idézett mű 479: oldalát vagy E. Netto: Lehrbuch der Kombinatorik, 2. kiad. (Leipzig, 1927.) 94‐97. old.