Partíciók, párpartíciók

Oravecz Ferenc

Az alábbiakban véges elemszámú halmazok bizonyos tulajdonságú részhalmazokra bontásiaval foglalkozunk. A feltett kérdések egyszerûek, akár hétköznapi nyelven is megfogalmazhatók. (Pl.: Hányféleképpen állíthatók párba egy osztály tanulói?) A válaszok is elemi úton kaphatók meg, néha azonban meglepõek; értelmezésük mélyebb összefüggéseket világít meg. Az eredmények egybeesése sok látszólag különbözõ probléma közötti kapcsolatra mutat rá. Felhívjuk az Olvasó figyelmét, hogy a témakörnek nagy irodalma van, ahol számos további részlet is megtalálható (l. az irodalomjegyzéket). A cikk végén egy érdekes alkalmazási lehetõséget mutatunk be, mely a kvantummechanika területén játszik fontos szerepet.

Tekintsünk egy tetszõleges véges elemszámú halmazt, és bontsuk föl diszjunkt részhalmazokra oly módon, hogy a felbontásban szereplõ egyik részhalmaz se legyen üres. Ekkor az eredeti halmaz minden egyes eleme pontosan egy részhalmaznak lesz eleme, a részhalmazok egyesítése pedig kiadja az eredeti halmazt. Az ilyen felbontásokat a halmaz partícióinak nevezzük, a felbontásban szereplõ részhalmazokat pedig az adott partíció blokkjainak hívjuk. Így például egy kilenc elemû halmaz egy lehetséges partíciója látható az 1. ábrán.

∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘
1.ábra

Itt a kis karikák a halmaz elemeit jelképezik, és pontosan azok az elemek tartoznak azonos blokkba, melyek egymással össze vannak kötve.

Ha π = {V_{1}, V_{2}, …, V_{k}} egy partíció, a π partíciót alkotó blokkok számát a |π|, míg az i-edik blokk elemeinek a számát a |V_{i}| szimbólummal fogjuk jelölni.

Példaképpen megadjuk egy három elemû S = {s_{1}, s_{2}, s_{3}} halmaz összes partícióját mind a részhalmazok felsorolásával, mind grafikus ábrázolásban (2. ábra):

π_{1} = {{s_{1}}, {s_{2}}, {s_{3}}}, π_{2} = {{s_{1}}, {s_{2}, s_{3}}}, π_{3} = {{s_{1}, s_{3}}, {s_{2}}} π_{4} = {{s_{1}, s_{2}}, {s_{3}}}, π_{5} = {{s_{1}, s_{2}, s_{3}}}

π_{1} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}}  π_{2} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}}  π_{3} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}}  π_{4} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}}  π_{5} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}}
2.ábra

Látható, hogy egy három elemû halmaznak öt különbözõ partíciója van. Fölmerül a kérdés, hogy az elemszám növekedtével hogyan változik a partíciók száma. A válaszhoz a következõ meggondolással juthatunk el. Jelölje B_{n} az n elemû halmaz partícióinak a számát. Tekintsünk most egy n + 1 elemû halmazt. Azt a blokkot amelybe az utolsó elem tartozik gondolatban kivéve a halmazból, a visszamaradó halmaz lehetséges partícióinak a száma nyilván B_{n−k}, ahol k azt mutatja meg, hogy a kiválasztott blokkban az utolsón kívül hány elem található (tehát k értéke nulla és n között van). Az n elem között a kiválasztott k elem (egymás közötti sorrendjére való tekintet nélkül) \binom{n}{k}féle képpen helyezkedhet el, így n + 1 elem összes lehetséges partícióinak a száma:

B_{n+1} = ∑_{k=0}^{n} \binom{n}{k}B_{n−k}.

Figyelembe véve még, hogy B_{0} = 1, a fenti képlet segítségével a partíciók száma tetszõleges véges elemszámú halmaz esetén kiszámolható. B_{n} neve - Eric Temple Bell tiszteletére - az n-edik Bell-szám.

A páros elemszámú halmazok partíciói között vannak olyanok, melyek minden blokkja pontosan két elemet tartalmaz. Az ilyen speciális partíciókat párpartícióknak hívjuk.

Határozzuk meg, hogy 2n elem esetén hányféle párpartíció képezhetõ! Ehhez képzeletben tegyük az elemeket egy kalapba, és abból húzzunk egyesével. Az elõször kihúzott elem párja legyen a másodszor kihúzott elem; a harmadikként kihúzott párja a negyedikként sorra kerülõ, és így tovább. Ha például az {s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6}} halmaz esetén a húzás sorrendje s_{5}, s_{6}, s_{1}, s_{3}, s_{4}, s_{2}, akkor a kapott párpartíció az {{s_{1}, s_{3}} {s_{2}, s_{4}} {s_{5}, s_{6}}} lesz. A húzások során kialakuló lehetséges sorrendek száma (2n)!. Azonban nem minden lehetséges sorrend határoz meg kölönbözõ párpartíciót. A kapott párpartíció szempontjából mindegy, hogy a kialakuló párokon belül melyik elemet húzzuk ki elõször és melyiket késõbb; ez n pár (2n elem) esetén egy 1/2^{n} faktort eredményez. Ugyanígy az is lényegtelen számunkra, hogy melyik pár kerül sorra elõbb és melyik késõbb. Mivel a párok lehetséges sorrendje n!, így ha 2n elem párpartícióinak a számát P_{2n} jelöli:

P_{2n} = \frac{(2n)!}{2^{n}n!}

A továbbiakban rendezett halmazok partícióit vizsgáljuk. Rendezett halmaz alatt olyan halmazt értünk, melyben valamilyen reláció segítségével az elemek egyértelmûen sorbarendezhetõek. A rendezett halmazok tipikus példái a valós számok részhalmazai, ahol az elemek sorrendjét a szokásos ”kisebb-nagyobb” reláció rögzíti. Természetesen bármely rendezett halmaz helyett gondolhatunk az elsõ n természetes számot tartalmazó halmazra, ahol n a kiválasztott halmaz elemeinek a száma. A rendezett halmazok partíciói esetén lehetõség van egy új fogalom bevezetésére. Tekintsük példaképpen az {1, 2, 3, 4} halmaz következõ két partícióját:

π_{1} = {{1, 4} {2, 3}} , π_{2} = {{1, 3} , {2, 4}} .

π_{1} :_{∘_{1}} _{∘_{2}} _{∘_{3}} _{∘_{4}} π_{2} :_{∘_{1}} _{∘_{2}} _{∘_{3}} _{∘_{4}}

3.ábra

Grafikusan ábrázolva e két partíciót (3. ábra), nyomban szembeötlik köztük egy alapvetõ különbség. Nevezetesen az, hogy míg π_{1} ábrázolása esetén - ha ügyesen járunk el - a blokkokat kijelölõ vonalak nem keresztezik egymást, π_{2} ábrázolása esetén azonban igen. Nevezzük a π_{2}-höz hasonló partíciókat (amelyek grafikus ábrázolásában tehát a blokkokat kijelölõ vonalak - az elemeknek a rendezésnek megfelelõ sorrendje esetén - mindenképpen keresztezik egymást) keresztezõ, míg a többi (π_{1}-hez hasonló) partíciót nemkeresztezõ partíciónak. A fent elmondottakkal ekvivalens a következõ

Definíció: Egy n elemû, ”<” relációval ellátott rendezett S halmaz π partíciója a., keresztezõ, ha létezik V_{1}, V_{2} ∈ π (V_{1} ≠ V_{2}) és létezik v_{1}, v_{2} ∈ V_{1}, w_{1}, w_{2} ∈ V_{2}

úgy, hogy v_{1} < w_{1} < v_{2} < w_{2}, b., nemkeresztezõ, ha nem keresztezõ.

Ha fenti példánkban az elemek sorrendje nem lenne rögzített, π_{2} ábrázolásában a második és harmadik vagy a harmadik és negyedik elem felcserélésével a keresztezés megszûnne; így érthetõ, hogy nem rendezett halmazok esetén e fogalmak értelmüket vesztik.

A 2. ábrán látható, hogy három elem partíciói között nincs keresztezõ; ugyanez igaz az egy és kételemû halmazokra is, amint arról könnyen meggyõzõdhetünk. Sõt, az is könnyen ellenõrízhetõ, hogy egy négy elemû halmaz partíciói közül is csak az az egy lesz keresztezõ, mely a 3. ábrán látható π_{2} partíciónak felel meg. Az elemszám növekedésével azonban a keresztezõ partíciók drasztikusan elszaporodnak és hétnél több elem esetén számuk már meghaladja a nemkeresztezõ partíciók számát.

Föltehetõ a kérdés, hogy egy n elelmû rendezett halmaznak hány nemkeresztezõ partíciója van. Jelöljük ezt a számot Q_{n}-nel. A nemkeresztezõ partíciók között lesznek olyanok, melyekben az utolsó elem egyedül alkot egy blokkot; ezek száma nyilván Q_{n−1}. Ha az utolsó elem által meghatározott blokk nem egy elemû, tekintsük a blokk azon elemét, mely az utolsó elemhez a legközelebb fekszik: legyen ez például az n − k-adik elem a sorban. Ekkor ezen és az utolsó elem közötti k − 1 elem egyike sem lehet közös blokkban a halmaz többi elemeivel a partíció nemkeresztezõ volta miatt (valamint a feltevés miatt, miszerint az utolsó elem legközelebbi ”szomszédja” az n − k-adik elem), egymás közt azonban tetszõleges nemkeresztezõ partíciót alkothatnak, akárcsak az elsõ n − k elem. Így az ilyen típusú partíciók száma Q_{n−k}Q_{k−1} lesz, ahol k lehetséges értéke 1 és n − 1 közé esik. Összegezve k különbözõ értékeire és figyelembevéve a gondolatmenet elején említett esetet is, amikor az utolsó elem külön blokkot alkotott, azt kapjuk, hogy

Q_{n} = Q_{n−1}Q_{0} + Q_{n−2}Q_{1} + … + Q_{1}Q_{n−2} + Q_{n−1}.

Mivel Q_{0} = 1, Q_{n−1} helyett írhatunk Q_{n−1}Q_{0}-et is, amivel végül

Q_{n} = Q_{n−1}Q_{0} + Q_{n−2}Q_{1} + … + Q_{1}Q_{n−2} + Q_{n−1}Q_{0}  (⋆)

adódik, ami viszont megegyezik az n-edik Catalan számra vonatkozó ismert rekurzióval (l. például [3]-ban). Q_{0} értékét figyelembe véve Q_{n} nem más, mint az n-edik Catalanszám:

Q_{n} = c_{n} = \frac{1}{n + 1}\binom{2n}{n}.

Természetesen a párpartíciók között is lesznek keresztezõk és nemkeresztezõk. 2n elem nemkeresztezõ párpartícióinak a számát jelöljük S_{2n}-nel. S_{2n} meghatározása történhet az elõbbi gondolatmenethez hasonlóan, a Catalan-számokra vonatkozó (⋆) rekurzión keresztül, s amint errõl az Olvasó maga is könnyen meggyõzõdhet, a választ ismét a Catalan-számok adják meg. Pontosabban

S_{2n} = c_{n} = \frac{1}{n + 1}\binom{2n}{n}.

Az eredményhez azonban más úton is eljuthatunk, s az alább felhasznált gondolat a továbbiakban is fontos szerepet játszik majd. Elõször is vezessünk be egy másik képet a nemkeresztezõ párpartíciók ábrázolására. Minden pár elsõ tagjának feleltessünk meg egy ferdén felfelé mutató nyilat (↗), a párok második tagjainak pedig egy ferdén lefelé mutató nyilat (↘). A nyilakat egymáshoz csatlakoztatva egy síkbeli pályát kapunk. Erre láthatunk példát a 4. ábrán.

∘ ∘ ∘ ∘ ∘∘ ↔

4.ábra

Mivel minden partíció ábrázolásakor nyilván ugyanannyi lefelé irányuló nyilat kapunk mint amennyi a felfelé mutató nyilak száma, így ha a pálya az origóból indul, ”nulla” magasságban, a vízszintes tengelyen fog végzõdni is. Sõt, mivel a felfelé irányuló nyil minden pár esetén megelõzi a lefelé mutatót, belátható, hogy a pálya sohasem megy a vízszintes tengely alá. Az ilyen pályákat szokás Catalanpályáknak nevezni. Figyeljük meg, hogy ha a keresztezõ párpartíciókat is ábrázolni akarnánk a fenti módon, akkor a hozzárendelés már nem lenne egy-egy értelmû. Ennek belátásához elég például az 5. ábrán lévõ párpartícióhoz tartozó pályát felrajzolni; könnyen ellenõrízhetõ, hogy ez megegyezik a 4. ábrán bemutatottal.

∘ ∘ ∘ ∘ ∘∘
5.ábra

Emiatt ezt a fajta ábrázolást a keresztezõ partíciókra nem is akarjuk kiterjeszteni. Könnyen ellenõrízhetõ azonban, hogy különbözõ nemkeresztezõ párpartíciókhoz már különbözõ pálya tartozik. Egy 2n hosszúságú Catalan-pályához az azt definiáló nemkeresztezõ párpartíciót pedig úgy kaphatjuk vissza, ha az egy szinten lévõ, egymáshoz legközelebbi fel-le nyilpároknak megfelelõ elemeket választjuk pároknak. Különbözõ pályák esetén most is különbözõ partíciókat kapunk, tehát a hozzárendelés bijektív. Ebbõl az következik, hogy 2n elem nemkeresztezõ párpartícióinak a száma megegyezik a 2n hosszúságú Catalan-pályák számával. Az viszont nyilván egyenlõ a 2n hosszúságú, origóból induló és a vízszintes tengelyen végzõdõ (de az alá is mehetõ) pályák számának és a 2n hosszúságú, origóból induló és a vízszintes tengelyen végzõdõ, −1-et elérõ pályák számának a különbségével. Ez utóbbi pedig megegyezik a −2bõl induló, vízszintes tengelyen végzõdõ 2n hosszúságú pályák számával, ami az úgynevezett André-féle tükrözési elv segítségével látható be (6. ábra).

6.ábra

Válasszuk ki azt a pontot, ahol a pálya elõször éri el a −1-et. A pályának az ezt megelõzõ szakaszát tükrözzük az y = −1 egyenesre, a kiválasztott pont utáni részét viszont hagyjuk változatlanul. Így nyilván egy −2-bõl induló, nullában végzõdõ pályát kapunk. Könnyen átgondolható, hogy ez a hozzárendelés is egy-egy értelmû, amivel állításunkat igazoltuk. Így végül azt kapjuk, hogy

S_{2n} = #{2n hosszú Catalan-pályák}
= #{0 → 0 pályák} − #{0 → 0, − 1-et elérõ pályák}
= #{0 → 0 pályák} − #{−2 → 0 pályák}
= \binom{2n}{n} − \binom{2n}{n − 1} = \frac{(2n)!}{n!n!} − \frac{(2n)!}{(n + 1)!(n − 1)!}
= \frac{(2n)!}{n!n!} [1 − \frac{n}{n + 1}] = \binom{2n}{n}\frac{n + 1 − n}{n + 1} = \frac{1}{n + 1}\binom{2n}{n}.

(A negyedik egyenlõségnél felhasználtuk, hogy 2n helyre k számú felfelé mutató és 2n − k számú lefelé mutató nyilat \binom{2n}{k} féle sorrendben tudunk elhelyezni.)

Tehát a nemkeresztezõ párpartíciók a számát ismét a Catalan számok határozzák meg! Eszerint egy 2n elemû rendezett halmaz nemkeresztezõ párpartícióinak a száma ugyanannyi, mint ahány nemkeresztezõ partíciója van egy n elemû rendezett halmaznak. Erre az elsõ látásra meglepõ eredményre a késõbbiek során még visszatérünk.

Legyen π = {V_{1}, V_{2}, …, V_{k}} egy n elemû halmaz tetszõleges nemkeresztezõ partíciója. π szokásos ábrázolása esetén az egyes blokkokat kijelölõ összekötõ vonalak a felsõ félsíkot n + 1 − k komponensre osztják. Ez a következõképpen látható be. Amíg csak az elemeket rajzoljuk be az ”x tengelyre”, addig az egész felsõ félsík összefüggõ. A V_{1} blokkot kijelölõ összekötõ vonal berajzolása |V_{1}| − 1 új komponenst eredményez (7. ábra). A V_{2} blokkot kijelölõ összekötõ vonalak berajzolása további |V_{2}| − 1 új komponenst eredményez (8. ábra), és így tovább. Végül tehát a blokkok berajzolásakor összesen 1 + (|V_{1}| − 1) + (|V_{2}| − 1) + … + (|V_{k}| − 1) = 1 + |V_{1}| + |V_{2}| + … + |V_{k}| − k = n + 1 − k komponensre bontjuk a felsõ félsíkot.

⋯ ∘ ∘ ∘ ∘ ∘ ∘ ⋯
7.ábra

⋯ ∘ ∘ ∘ ∘ ∘ ∘ ⋯
8.ábra

Az eredeti n elemû halmazunk legyen az S = {1, 2, …, n} halmaz (láttuk, hogy ez nem csorbítja az általánosságot). Vezessünk be egy másik, S′ halmazt a következõképpen:

S′ = \{1′, 2′, …, n′\} = \{1\frac{1}{2}, 2\frac{1}{2}, …, n\frac{1}{2}\} .

Ezután tekintsük S′ azon elemeit összetartozóknak, melyek nagyságuknak megfelelõ helyükre illesztve a felsõ félsík azonos komponensében helyezkednek el. Így megkapjuk S′ egy partícióját, amit K(π)-vel jelölünk, és amit az eredeti π partíció Kreweras komplementerének hívunk Kreweras francia matematikus tiszteletére, aki 1972-ben vezette be ezt a leképezést. A konstrukcióból látszik, hogy K(π) S′-nek nemkeresztezõ partíciója, és hogy K(π) blokkjainak száma n + 1 − k, hiszen a felsõ félsík minden komponensében található legalább egy i′ elem. Sõt, az is látható, hogy π és K(π) együtt egy 2n elemû halmaz egy partícióját határozzák meg, mely a konstrukció révén megintcsak nemkeresztezõ. Ennek az új partíciónak a jele T wice(π). A 9. ábra nyolc elem π = {{1, 3} {2} {4, 7, 8} {5, 6}} partíciójából kiindulva mutatja be az eljárás különbözõ lépéseit. Az ábrán az üres karikák az eredeti S = {1, 2, …, 8} halmazt, a folytonos vonalak a π partíciót, a sötét karikák az S′ = {1′, 2′, …, n′} halmazt, a szaggatott vonalak K(π)-t jelölik; mindezt ”összeolvasva” pedig T wice(π) ábrázolása jelenik meg.

∘ • ∘ • ∘ • ∘ • ∘ • ∘ • ∘ • ∘•
9.ábra

Mielõtt továbblépnénk, megmutatjuk, hogy K kétszeri alkalmazása, azaz K^{2}(π) egy ”rotáció”. Ez a partíciók úgynevezett cirkuláris ábrázolásából rögtön látszik. A cirkuláris reprezentáció esetén a halmaz elemeit nem egy egyenes mentén, hanem egy körvonalon helyezzük el, egyenletes távolságban egymástól. A 10. ábra a 9. ábrán látható partíciók cirkuláris ábrázolását adja meg. Ha mármost S′-t tekintjük alaphalmaznak a K(π) partícióval, akkor K(K(π)) megkonstruálása során az (1′)′ = 2, (2′)′ = 3, …, (n′)′ = 1 megfeleltetéseket kapjuk, és K(K(π)) meg fog egyezni azzal a partícióval, melynek cirkuláris reprezentációját a π partíció cirkuláris reprezentációjának a kör mentén egy egységgel való, az óramutató járásával megegyezõ irányú elforgatásával kapunk. Könnyen belátható, hogy K eme tulajdonsága egyben azt is biztosítja, hogy K bijekció.

10.ábra

Azt, hogy T wice(π) 2n elem egy nemkeresztezõ partíciója, már láttuk. Ugyanez természetesen igaz lesz K(T wice(π))-re is. Álljon az eredeti π partíciónk k blokkból. Ekkor a fentebb említettek szerint K(π) n+1−k blokkból, T wice(π) k+(n+1−k) = n + 1 blokkból, K(T wice(π)) pedig 2n + 1 − (n + 1) = n blokkból áll. Megmutatjuk, hogy K(T wice(π)) minden blokkjában legalább két elem található. Hogy legalább egy elem van, azt már láttuk K megkonstruálásakor. Tegyük most fel, hogy van olyan blokk, amelyben pontosan egy elem van. Az, hogy az elem az adott komponensben egyedül van azt jelenti, hogy a két szomszédos elem össze van kötve egymással, azaz közös blokkban van. Ez azonban nem lehetséges, hisz a feltételezett egyedüli elem baloldali szomszédja a K(π) partíció alaphalmazát alkotó {1′, 2′, …, n′} halmazba tartozik, míg jobboldali szomszédja (a sor végén álló elem esetén ezt ciklikusan értve) a π partíció alaphalmazául szolgáló {1, 2, …, n} halmazba tartozik (vagy fordítva), mely halmazok a partíciók szintjén egymástól ”elszeparáltak”. Tehát valóban igaz, hogy K(T wice(π)) minden blokkjában legalább két elem van, ami - figyelembe véve, hogy 2n elemünk és n blokkunk van - azt jelenti, hogy minden blokkba pontosan két elem kerül. Ebbõl pedig az következik, hogy K(T wice(π)) egy (nemkeresztezõ) párpartíció. Ezzel beláttuk, hogy tetszõleges π nemkeresztezõ partícióból kiindulva a K ∘ T wice leképezés segítségével egy kétszeres elemszámú halmaz egy nemkeresztezõ párpartícióját kapjuk meg. Mivel - amint azt fentebb láttuk - K bijekció, a K ∘T wice leképezés egy-egy értelmû. Annak belátására, hogy K ∘T wice bijekció ezek után elég azt megmutatni, hogy a 2n elemû halmaz bármely ν nemkeresztezõ párpartíciójához található olyan π nemkeresztezõ partíciója az n elemû halmazunknak, melyre K ∘ T wice(π) = ν. Ennek igazolása legegyszerûbben a K ∘ T wice leképezés inverzének közvetlen meghatározásával történhet; az érdeklõdõ Olvasó a bizonyítást maga is könnyen elvégezheti. A K ∘ T wice leképezés jól mutatja a nemkeresztezõ partíciók és a kétszeres elemszámú halmaz nemkeresztezõ párpartíciói között fennálló szoros kapcsolatot. Segítségével azonnal adódik például, hogy ezek száma megegyezik, amint arra már korábban felhívtuk a figyelmet.

A 11. ábra egy egyszerû példán mutatja be a fentieket.

∘ × • × ∘ × • × ∘ × • × ∘ × •×

Az üres karikák az azokat összekötõ folytonos vonalakkal most is az alaphalmazt és a kiindulási π partíciót jelölik, a sötét karikák és az azokat összekötõ szaggatott vonalak a K(π) partíciót és az annak megfelelõ új halmazt ábrázolják, e kettõ együtt alkotja az összes karika halmazának T wice(π) partícióját, a kis keresztek és az azokat összekötõ hullámos vonalak pedig a K(T wice(π)) párpartíciót szimbolizálják.

További részletek helyett nézzünk meg két egyszerû, de érdekes alkalmazást.

Az elsõ a nemkeresztezõ párpartíciók és a szintaktikusan helyes zárójelsorozatok közötti szoros és közvetlen kapcsolaton alapszik. Világos, hogy ha a nemkeresztezõ párpartícióknak a korábban említett, Catalan-pályákkal való ábrázolásában a nyilacskákat nyitó illetve záró zárójelekkel helyettesítjük (felfelé mutató nyil esetén nyitó, lefelé mutató nyil esetén záró zárójelet írunk), akkor a nemkeresztezõ párpartícióknak egy, szabályos zárójelsorozatokkal való ábrázolását kapjuk. A 4. ábrán látható párpartíciónak például a következõ zárójelsorozat felel meg:

( ( ) ) ( )

Könnyen látható, hogy nemkeresztezõ párpartíciókra szorítkozva ez a hozzárendelés is bijektív.

Ezekután világos, hogy a zárójelezésekkel kapcsolatos problémák nagy része a nemkeresztezõ párpartíciók nyelvén is tárgyalható (mint ahogy a nemkeresztezõ párpartíciókra vonatkozó kérdések is megközelíthetõek a szintaktikailag helyes zárójelezések szabályszerûségeinek felhasználásával). A Polygon 1997 júniusi számában több ilyen problémát is találhat az Olvasó (l. [3])

A másik alkalmazás a fizikához kapcsolódik. A kvantummechanikában részecskerendszerek leírásakor gyakran találkozhatunk az úgynevezett keltõ és eltüntetõ operátorokkal. Amint azt már a nevük is sugallja, a keltõ operátor a vákuumból (a ”semmibõl”) egy adott állapotú részecskét hoz létre, azaz egy részecskerendszerre alkalmazva azt a rendszerben megjelenik egy újabb részecske. Ezzel szemben az eltüntetõ operátor ennek pont az ellenkezõjére képes: egy adott állapotú részecskét eltüntet a rendszerbõl, ha eredetileg volt benne ilyen. Ha pedig a rendszerben nincs olyan állapotú részecske amit az eltüntetõ operátor eltüntethetne, akkor az operáció értéke nulla lesz és az egész rendszerünk kihal (amin már semmilyen keltõ operátor sem segíthet). A szokásos részecskék leírására használatos eltüntetõ és keltõ operátorok alkalmazásakor általában megjelennek még bizonyos, a rendszerben szereplõ részecskék számától függõ faktorok is, de mi most az egyszerûség kedvéért ezekrõl feledkezzünk meg. Ezenkívül feledkezzünk meg a részecskék különbözõ állapotairól is, figyelmünket csak arra fordítsuk, hogy van-e rendszerben részecske vagy nincs, és ha van akkor hány darab. (Ez a leegyszerûsített modell fontos szerepet játszik az elmúlt tíz évben fejlõdésnek indult szabad valószínûségelméletben [4])

A részecske nélküli üres tér (a vákuum) szokásos jele Φ a keltõ és eltüntetõ operátorokat pedig jelölje rendre l és l^{+}. Legyen továbbá az i részecskét tartalmazó rendszer jele |i⟩. (Így például Φ = |0⟩ .) Ekkor az eltüntetõ és keltõ operátorok hatása a következõképpen írható le:

l |i⟩ = |i + 1⟩  i = 0, 1, 2, …,
l^{+} |i⟩ = |i − 1⟩  i = 1, 2, …,
l^{+} |0⟩ = 0.

A részecskerendszerek terében (melynek pontos matematikai meghatározására most nem térünk ki) a különbözõ részecskeszámú rendszerek ”ortogonálisak” egymásra, sõt, a fizikában elterjedt írásmóddal

⟨i, j⟩ = \{ \begin{matrix}1,  ha i = j, \\ 0,  ha i ≠ j, \end{matrix}  (⋆⋆)

ahol a ⟨ , ⟩ szimbólum egy, a részecskerendszerek terén értelmezett skalárszorzat.

A keltõ és eltüntetõ operátorokból bonyolultabb operátorok is összerakhatók. Egy részecskerendszerekre ható operátor n-edik hatványa által a vákuumból generált rendszer és a vákuum-állapot skalárszorzatát szokták az operátor n-edik momentumának nevezni. Nevezetesen ha A egy ilyen operátort jelöl, akkor A n-edik momentumát a következõ képlet adja meg:

m_{n}^{A} = ⟨A^{n}0, 0⟩ n = 0, 1, 2, …

(Egy operátor n-edik hatványa az operátor n-szer egymás után való alkalmazását jelenti.)

Ha például A = l, kapjuk, hogy

m_{n}^{l} = ⟨l^{n}0, 0⟩ = ⟨n, 0⟩ = \{ \begin{matrix}1, ha n = 0, \\ 0, ha n ≠ 0. \end{matrix}

Egy operátor momentumsorozata a hozzáértõknek sokmindent elárul magáról az operátorról; így a momentumok meghatározása gyakran fontos feladat, mely sok esetben könnyen kapcsolatba hozható bizonyos halmazok partícióival vagy párpartícióival.

Példaképpen tekintsük az úgynevezett mezõoperátort, mely a keltõ és eltüntetõ operátor összege. Ez az operátor fontos szerepet tölt be a kvantummechanikában. Keressük tehát az

m_{n} = ⟨(l + l^{+})^{n}0, 0⟩

mennyiségeket. Mivel l és l^{+} egymással nem felcserélhetõ (ll^{+} ≠ l^{+}l, hisz l^{+}l |0⟩ = |0⟩, míg ll^{+} |0⟩ = 0), a hatványok kifejtésénél nem alkalmazható a binomiális formula. n = 3 esetén például (l+l^{+})^{3} = lll+lll^{+}+ll^{+}l+ll^{+}l^{+}+l^{+}ll+l^{+}ll^{+}+l^{+}l^{+}l+l^{+}l^{+}l^{+}, ami nem egyezik meg a a kommutatív esetben várt l^{3} + 3l^{2}l^{+} + 3l(l^{+})^{2} + (l^{+})^{3} kifejezéssel.

Az n-edik hatványt kifejtve tehát … ll^{+}l^{+}ll …típusú szorzatokat kapunk, vagyis keltések és eltüntetések bizonyos sorozatait. Az ilyen szorzatoknak feleltessünk meg olyan síkbeli bolyongásokat, melyek az origóból indulnak, és minden lépésben vagy ferdén fölfelé, vagy ferdén lefelé ugranak egyet, attól függõen, hogy az adott helyen keltõ vagy eltüntetõ operátor áll-e a szorzatban. Így például az lll^{+}l^{+}ll^{+} szorzatnak pont a 4. ábrán látható Catalan-pálya fog megfelelni. A (⋆⋆) egyenletek alapján egy adott szorzatnak csak akkor van járuléka, ha azt a vákuumra hattatva ismét a részecske nélküli rendszert kapjuk vissza, ami persze egyben azt is jelenti, hogy a rendszerünk menetközben nem szûnt meg létezni, vagyis az eltüntetõ operátornak mindig volt mit eltüntetnie. Végiggondolható, hogy a momentumok kiszámításánál csak azok a szorzatok adnak járulékot (mégpedig mindig egységnyi járulékot), amelyeknek azok az origóból induló pályák felelnek meg, melyek a vízszintes tengelyen végzõdnek, és sehol sem kerülnek az alá. Ezek azonban nem mások, mint a korábban a nemkeresztezõ párpartíciók ábrázolására használt Catalan-pályák! Innen a keresett momentumok azonnal adódnak:

m_{n} = S_{n} = \{ \begin{matrix}0, ha n páratlan \\ \frac{1}{n+1} \binom{2n}{n}, ha n páros. \end{matrix}

Bonyolultabb operátorok esetében gyakran kényelmesebb a nemkeresztezõ párpartíciók helyett nemkeresztezõ partíciókat rendelni a felbukkanó szorzatokhoz, az eljárás menete azonban sok esetben hasonlóan vezet eredményre.

IRODALOM

[1] George E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and its Aplications, Addison-Wesley Publishing Company, 1976 .

[2] Peter Hilton, Jean Pedersen, Catalan Numbers, Their Generalization, and Their Uses, The Mathematical Intelligencer Vol. 13, No.2, 1991.

[3] Csákány Béla, Zárójeles megjegyzések, Polygon, 1997. junius

[4] Roland Speicher, Combinatorial Theory of The Free Product with Amalgamation and Operator-valued free probability theory, Universitat Heidelberg, 1995.

[5] R. Graham, D.Knuth, O. Patashnik, Konkrét matematika.

[6] Hajnal Péter, Egyenlõségek, oszthatóságok bizonyítása kombinatorkus módszerekkel, Polygon IV kötet 1. szám 27-43.

[7] Hajnal Péter, Összeszámlálási problémák, Polygon Jegyzettár, Szeged, 1997.

[8] Rényi Alfréd, Új módszerek és eredmények a kombinatorikus analízisben I., Magyar Tud. Akad. Közleményei, 1966, 77-105.

[9] Vilenkin, Kombinatorika.

Oravecz Ferenc doktorandusz

Budapesti Mûszaki Egyetem Matematikai Intézet Analízis Tanszék

Budapest, Egry József u. 1, H épület 26 1111

e-mail:oravecz@math.bme.hu tel: 4632475 fax: 4633172

Partíciók, párpartíciók 13

ÁBRÁK

∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘

1.ábra

π_{1} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}} π_{2} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}} π_{3} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}} π_{4} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}} π_{5} :_{∘_{s_{1}}} _{∘_{s_{2}}} _{∘_{s_{3}}}

2.ábra

π_{1} :_{∘_{1}} _{∘_{2}} _{∘_{3}} _{∘_{4}} π_{2} :_{∘_{1}} _{∘_{2}} _{∘_{3}} _{∘_{4}}

3.ábra

∘ ∘ ∘ ∘ ∘∘ ↔ 4.ábra ∘ ∘ ∘ ∘ ∘∘ 5.ábra ⋯ ∘ ∘ ∘ ∘ ∘ ∘ ⋯

7.ábra

⋯ ∘ ∘ ∘ ∘ ∘ ∘ ⋯

8.ábra

∘ • ∘ • ∘ • ∘ • ∘ • ∘ • ∘ • ∘•

9.ábra

10.ábra

∘ × • × ∘ × • × ∘ × • × ∘ × •×