Generátor sorozat
A matematika , és különösen a elemzése és kombinatorikai , egy generátor sorozat (korábban úgynevezett generátor funkciót , a terminológia még ma is használják, különösen keretében valószínűségszámítás ) egy formális sorozat , amelynek együtthatóit kódolják sorozat számok (vagy még általánosabban a polinomok stb.); azt mondjuk, hogy a sorozat a folytatáshoz kapcsolódik . Ezeket a sorozatokat Abraham de Moivre vezette be 1730-ban, hogy egyértelmű képleteket kapjon a lineáris megismétlődéssel meghatározott szekvenciákra .
(nál nélnem){\ displaystyle (a_ {n})}
Ez egy olyan fogalom, amely különbözik a polinomiális interpolációtól , ahol egy olyan polinom meghatározására törekszünk, amelynek értékei (és már nem az együtthatók ) egybeesnek egy adott szekvenciával.
Tény, hogy több féle generáló funkciók, mint például generál exponenciális sorozat , a sorozat Lambert , a Dirichlet sor , stb Minden típusú generátorsorozat bármilyen szekvenciához hozzárendelhető, de a sorok kezelésének egyszerűsége jelentősen függ a társított szekvencia jellegétől: például a Dirichlet-sorok aritmetikája teljesen természetes módon tükrözi a szekvenciák tulajdonságait a számelméletben, míg az exponenciális generáló sorozat ideális lesz a permutációkkal stb. kapcsolatos problémák kódolásához.
Gyakran lehetséges tanulmányozni egy adott szekvenciát a kapcsolódó generáló sorok formális manipulációival, valamint a sorozat összegfüggvényének analitikai tulajdonságainak felhasználásával , legalábbis ha ez utóbbi kellően nagy halmaz nagy konvergenciájához kapcsolódik. Ez a gyakorlatban meglehetősen gyakori eset igazolja a generáló függvény megnevezését, és az analitikus kombinatorika alapját képezi (a kombinatorikus objektumok felsorolása és aszimptotikája generáló sorokon keresztül). Vegyük észre azt is, hogy eltérő sorozat , mint a vagy , tökéletesen és szigorúan manipulálható: közelítenek egymáshoz a gyűrűben formális sorozat, látva a megfelelő topológia , és szintén vizsgálták aszimptotikusan (via lehetséges transzformációk).
∑nem≥0nem!xnem{\ displaystyle \ sum _ {n \ geq 0} n! x ^ {n}}∑nem≥02nemxnem{\ displaystyle \ sum _ {n \ geq 0} 2 ^ {n} x ^ {n}}
Definíciók
Az alábbiakban meghatározott sorozatok formális sorozatok , vagyis nem eleve aggódunk a konvergencia területük miatt.
Rendes generátor sorozat
Az a n szekvencia szokásos generátor-sorozata (gyakran egyszerűen a szekvencia generátor-sorozatának hívják) a teljes sorozat
G(nál nélnem;x)=∑nem=0∞nál nélnemxnem{\ displaystyle G (a_ {n}; x) = \ összeg _ {n = 0} ^ {\ infty} a_ {n} x ^ {n}}.
Ez a meghatározás könnyen általánosítható több indexű szekvenciákra. Például, egy szekvenciát egy n , k (ahol n és k természetes számok ), a generáló sorozat
G(nál nélnem,k;x,y)=∑nem,k=0∞nál nélnem,kxnemyk{\ displaystyle G (a_ {n, k}; x, y) = \ sum _ {n, k = 0} ^ {\ infty} a_ {n, k} x ^ {n} y ^ {k}}.
Exponenciális generátor sorozat
Az a n szekvenciához társított exponenciális generátorsorozat az
PÉLDÁUL(nál nélnem;x)=∑nem=0∞nál nélnemxnemnem!{\ displaystyle \ kezelőnév {EG} (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {n} {\ frac {x ^ {n}} {n!}}}.
Poisson-generáló sorozat
A Poisson generáló sorozat egy szekvencia egy n jelentése
PG(nál nélnem;x)=∑nem=0∞nál nélneme-xxnemnem!=e-xPÉLDÁUL(nál nélnem;x){\ displaystyle \ kezelőnév {PG} (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {n} \ mathrm {e} ^ {- x} {\ frac {x ^ {n}} {n!}} = \ mathrm {e} ^ {- x} \, \ operátor neve {EG} (a_ {n}; x)}.
Lambert generátor sorozat
Az a n szekvencia Lambert-sorozata az
LG(nál nélnem;x)=∑nem=1∞nál nélnemxnem1-xnem{\ displaystyle \ kezelőnév {LG} (a_ {n}; x) = \ sum _ {n = 1} ^ {\ infty} a_ {n} {\ frac {x ^ {n}} {1-x ^ { nem}}}}.
Ebben az esetben a definíciós problémát, a sorozat kell kezdeni egy 1 , és nem a 0 .
Haranggenerátor-sorozat
Az a n szekvencia Bell-sorozata egy adott p prímszámra a formális sorozat
BGo(nál nélnem;x)=∑nem=0∞nál nélonemxnem=G(nál nélonem;x){\ displaystyle \ kezelőnév {BG} _ {p} (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {p ^ {n}} x ^ {n} = G ( a_ {p ^ {n}}; x)}.
Dirichlet generátor sorozat
A Dirichlet-sorozatokat gyakran generáló függvényekként osztályozzák, bár ezek nem szigorúan formális sorozatok (a határozatlan egész egész hatványok). A Dirichlet generátor sorozat egy szekvencia egy n jelentése
Főigazgatóság(nál nélnem;s)=∑nem=1∞nál nélnemnems{\ displaystyle \ kezelőnév {DG} (a_ {n}; s) = \ sum _ {n = 1} ^ {\ infty} {\ frac {a_ {n}} {n ^ {s}}}}.
A Dirichlet sor különösen hasznos, ha egy n egy multiplikatív függvény , mert akkor van egy Euler-terméket által adott Bell sorozat:
Főigazgatóság(nál nélnem;s)=∏oBGo(nál nélnem;o-s){\ displaystyle \ kezelőnév {DG} (a_ {n}; s) = \ prod _ {p} \ kezelőnév {BG} _ {p} (a_ {n}; p ^ {- s})}.
Ha egy n egy Dirichlet karakter , a megfelelő Dirichlet sor nevezzük Dirichlet L sorozat .
Polinom szekvenciákat generáló sorozatok
A sorozatgenerálás fogalma kiterjed az objektumok más sorozatára is. Így az első és a második típusú Chebyshev-polinomok (rendes) generáló sorozatai a következők:
∑nem=0∞Tnem(x)tnem=1-tx1-2tx+t2,∑nem=0∞Unem(x)tnem=11-2tx+t2{\ displaystyle \ sum _ {n = 0} ^ {\ infty} T_ {n} (X) t ^ {n} = {\ frac {1-tX} {1-2tX + t ^ {2}}}, \ quad \ sum _ {n = 0} ^ {\ infty} U_ {n} (X) t ^ {n} = {\ frac {1} {1-2tX + t ^ {2}}}}.
A Bernoulli-polinomok (exponenciális) generátorsorozata az
∑nem=0∞Bnem(x)tnemnem!=textet-1{\ displaystyle \ sum _ {n = 0} ^ {\ infty} B_ {n} (X) {\ frac {t ^ {n}} {n!}} = {\ frac {t \ mathrm {e} ^ {Xt}} {\ mathrm {e} ^ {t} -1}}} ;
Általánosabban a binomiális (en) típusú polinomok szekvenciái kapcsolódnak a sorozathoz
exf(t)=∑nem=0∞onem(x)nem!tnem{\ displaystyle e ^ {Xf (t)} = \ sum _ {n = 0} ^ {\ infty} {p_ {n} (X) \ n felett!} t ^ {n}},
ahol ( p n ) egy polinom szekvencia és f ( t ) egy függvény (egy bizonyos formájú); a Sheffer lakosztályok hasonló generátorokkal rendelkeznek. További részletek az " Általános híváspolinom " című cikkben találhatók .
0-ban iterált származékok
A generáló sorozat származékai formálisan az egyes kifejezések származékainak sorozataként vannak meghatározva; például egy közönséges generátor-sorozat
esetében megvan . Különösen a 0-ban van:
G(nál nélnem;x)=∑nál nélnemxnem{\ displaystyle \ operátornév {G} (a_ {n}; x) = \ sum a_ {n} x ^ {n}}G′(nál nélnem;x)=G((nem+1)nál nélnem+1;x){\ displaystyle \ kezelőnév {G} '(a_ {n}; x) = \ kezelőnév {G} ((n + 1) a_ {n + 1}; x)}
Rendes generátor sorozat
Az a n szekvencia szokásos generátorsorának 0-nál iterált származékai megegyeznek:
G(k)(nál nélnem;0)=k!nál nélk{\ displaystyle \ kezelőnév {G} ^ {(k)} (a_ {n}; 0) = k! \, a_ {k}}Exponenciális generátor sorozat
Az a n szekvencia exponenciális generátorsorának 0-nál iterált származékai megegyeznek:
PÉLDÁUL(k)(nál nélnem;0)=nál nélk{\ displaystyle \ kezelőnév {EG} ^ {(k)} (a_ {n}; 0) = a_ {k}}Poisson-generáló sorozat
Az a n szekvencia Poissont generáló sorozatának 0-nál iterált származékai megegyeznek:
PG(k)(nál nélnem;0)=∑én=0k(-1)énVSkénnál nélk-én=∑én=0k(-1)k-énVSkénnál nélén{\ displaystyle \ kezelőnév {PG} ^ {(k)} (a_ {n}; 0) = \ összeg _ {i = 0} ^ {k} (- 1) ^ {i} \, C_ {k} ^ {i} \, a_ {ki} = \ sum _ {i = 0} ^ {k} (- 1) ^ {ki} \, C_ {k} ^ {i} \, a_ {i}}Lambert sorozat
Az a n ( n 1-ből) Lambert-sorozat 0-nál iterált származékai egyenlőek:
LG(k)(nál nélnem;0)=k!∑én|kén=1knál nélén{\ displaystyle \ kezelőnév {LG} ^ {(k)} (a_ {n}; 0) = k! \, \ sum _ {\ overset {i = 1} {i | k}} ^ {k} a_ { én}}Csak annak a szekvenciának a tagjai jelennek meg az összegben, amelynek i indexe osztja k-t .
Példa: négyzetsorozat generálása
Az a n = n 2 négyzetsorozatnak megfelelő, különböző típusú generáló sorok a következők:
Rendes generátor sorozat
G(nem2;x)=∑nem=0∞nem2xnem=x(x+1)(1-x)3{\ displaystyle G (n ^ {2}; x) = \ sum _ {n = 0} ^ {\ infty} n ^ {2} x ^ {n} = {\ frac {x (x + 1)} { (1-x) ^ {3}}}}
Exponenciális generátor sorozat
PÉLDÁUL(nem2;x)=∑nem=0∞nem2xnemnem!=x(x+1)ex{\ displaystyle \ kezelőnév {EG} (n ^ {2}; x) = \ sum _ {n = 0} ^ {\ infty} {\ frac {n ^ {2} x ^ {n}} {n!} } = x (x + 1) e ^ {x}}
Bell sorozat
BGo(nál nélnem;x)=∑nem=0∞(onem)2xnem=11-o2x{\ displaystyle \ kezelőnév {BG} _ {p} (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} (p ^ {n}) ^ {2} x ^ {n} = {\ frac {1} {1-p ^ {2} x}}}
Dirichlet sorozat
Főigazgatóság(nem2;s)=∑nem=1∞nem2nems=ζ(s-2){\ displaystyle \ kezelőnév {DG} (n ^ {2}; s) = \ sum _ {n = 1} ^ {\ infty} {\ frac {n ^ {2}} {n ^ {s}}} = \ zeta (s-2)}(ahol ζ a
Riemann zeta függvény ).
Általánosabban, ha az a n szekvenciának Dirichlet-sorozata van, amely megfelel
Főigazgatóság(nál nélnem;s)=ζ(s)m{\ displaystyle \ kezelőnév {DG} (a_ {n}; s) = \ zeta (s) ^ {m}},
ez a csomag a hétköznapi generátor sorozatokhoz tartozik
G(nál nélnem;x)=∑nem=1∞nál nélnemxnem=x+(m1)∑nál nél=2∞xnál nél+(m2)∑nál nél=2∞∑b=2∞xnál nélb+(m3)∑nál nél=2∞∑b=2∞∑vs.=2∞xnál nélbvs.+(m4)∑nál nél=2∞∑b=2∞∑vs.=2∞∑d=2∞xnál nélbvs.d+...{\ displaystyle {\ begin {aligned} G (a_ {n}; x) = \ összeg \ korlátozza _ {n = 1} ^ {\ infty} a_ {n} x ^ {n} = x & + {m \ válassza az 1} \ összeg \ korlátok _ {a = 2} ^ {\ infty} x ^ {a} + {m \ választás 2} \ összeg \ korlátok _ {a = 2} ^ {\ infty} \ összeg \ korlátok _ lehetőséget {b = 2} ^ {\ infty} x ^ {ab} \\ & + {m \ select 3} \ összeg \ korlátok _ {a = 2} ^ {\ infty} \ összeg \ korlátok _ {b = 2} ^ {\ infty} \ összeg \ korlátok _ {c = 2} ^ {\ infty} x ^ {abc} + {m \ válassza a 4} \ összeg \ korlátok _ {a = 2} ^ {\ infty} \ összeg \ korlátok _ {b = 2} ^ {\ infty} \ összeg \ korlátok _ {c = 2} ^ {\ infty} \ összeg \ korlátok _ {d = 2} ^ {\ infty} x ^ {abcd} + .. . \ end {igazítva}}}
Rendes generátor sorozat
Polinomok
A polinomok a közönséges generáló sorok speciális esetei, amelyek véges szekvenciáknak (vagy egy bizonyos rangból törlő szekvenciáknak) felelnek meg. Ez az értelmezés fontos, például abban az esetben, polinomok Poincaré eredményének megfelelően a Betti számok egy fajta adatok, vagy polinomok Hilbert (en) az osztályozott algebra .
Geometriai szekvencia sorozatának generálása
Fontos szerepet játszik az alkalmazásokban az az állandó szekvencia, amelynek minden kifejezés egyenlő 1-vel; generátorsorozata az
∑nem=0∞xnem=11-x{\ displaystyle \ sum _ {n = 0} ^ {\ infty} x ^ {n} = {1 \ 1-x} felett,
mivel könnyen ellenőrizhetjük, ha formálisan megszorozzuk ezt a sorozatot 1 - x-szel , és megjegyezzük, hogy az első kifejezések kivételével az összes kifejezés 2–2-re törli egymást.
Mi következtethetünk ebből az expresszióját a termelő sorozat sok más szekvenciák: így, a helyettesítési x ↦ ax ad a generáló sorozat egy geometriai szekvencia 1, egy , a 2 , a 3 , ... :
∑nem=0∞(nál nélx)nem=11-nál nélx{\ displaystyle \ sum _ {n = 0} ^ {\ infty} (ax) ^ {n} = {1 \ 1-ax felett}}és különösen .
∑nem=0∞(-1)nemxnem=11+x{\ displaystyle \ sum _ {n = 0} ^ {\ infty} (- 1) ^ {n} x ^ {n} = {1 \ több mint 1 + x}}Cseréje x által x 2 például, megkapjuk a sorozat kapcsolódó szekvenciával 1, 0, 1, 0, 1, 0, 1, 0, ...: .
∑nem=0∞x2nem=11-x2{\ displaystyle \ sum _ {n = 0} ^ {\ infty} x ^ {2n} = {1 \ 1-x ^ felett {2}}}
Az x felé sodródva megkapjuk az 1, 2, 3, 4, 5, ... egész számok sorozatához tartozó sorozatot:
∑nem=0∞(nem+1)xnem=1(1-x)2{\ displaystyle \ sum _ {n = 0} ^ {\ infty} (n + 1) x ^ {n} = {1 \ felett (1-x) ^ {2}}} ;
Hasonlóképpen, az 1, 3, 6, 10, 15, 21, ... háromszögek sorozata , amelynek n-edik tagja a binomiális együttható, megfelel
(nem+22){\ displaystyle {\ tbinom {n + 2} {2}}}
∑nem=0∞(nem+22)xnem=1(1-x)3{\ displaystyle \ sum _ {n = 0} ^ {\ infty} {\ binom {n + 2} {2}} x ^ {n} = {1 \ over (1-x) ^ {3}}}.
Általánosságban elmondható, hogy bármely pozitív k egész szám esetében megvan a képlet a negatív binomiálra :
∑nem=0∞(nem+kk)xnem=1(1-x)k+1{\ displaystyle \ sum _ {n = 0} ^ {\ infty} {\ binom {n + k} {k}} x ^ {n} = {1 \ over (1-x) ^ {k + 1}} }.
Mivel levezetjük (az előző generáló sorok lineáris kombinációjával) a 0, 1, 4, 9, 16, ... négyzet sorozat generáló sorozatát:
(nem+22)=12(nem+1)(nem+2)=12(nem2+3nem+2){\ displaystyle {\ binom {n + 2} {2}} = {\ frac {1} {2}} {(n + 1) (n + 2)} = {\ frac {1} {2}} ( n ^ {2} + 3n + 2)}
G(nem2;x)=∑nem=0∞nem2xnem=2(1-x)3-3(1-x)2+11-x=x(x+1)(1-x)3{\ displaystyle G (n ^ {2}; x) = \ sum _ {n = 0} ^ {\ infty} n ^ {2} x ^ {n} = {2 \ over (1-x) ^ {3 }} - {3 \ over (1-x) ^ {2}} + {1 \ over 1-x} = {\ frac {x (x + 1)} {(1-x) ^ {3}}} }.
Racionális törtek
A szekvencia generáló sorozata akkor és csak akkor fejezhető ki két polinom hányadosaként, ha a szekvencia lineárisan visszatérő szekvencia . Valóban, az ( a n ) szekvencia kielégíti a forma megismétlődését
∀nem≥onál nélnem=vs.1nál nélnem-1+vs.2nál nélnem-2+⋯+vs.o-1nál nélnem-o+1+vs.onál nélnem-o{\ displaystyle \ összes n \ geq p \ quad a_ {n} = c_ {1} a_ {n-1} + c_ {2} a_ {n-2} + \ cdots + c_ {p-1} a_ {n -p + 1} + c_ {p} a_ {np}}
(ahol c 1 , ..., c p konstansok) akkor és csak akkor, ha G ( X ) generátorsorozata szorozva a polinommal
Q(x): =1-vs.1x-⋯-vs.oxo{\ displaystyle Q (X): = 1-c_ {1} X- \ cdots -c_ {p} X ^ {p}},
olyan formális sorozat, amelynek minden tagja nulla a p foktól kezdődően , azaz ha
G(x)=P(x)Q(x){\ displaystyle G (X) = {\ frac {P (X)} {Q (X)}}}
ahol P szigorúan kisebb fokú polinom, mint p (amelynek együtthatói a szekvencia p első tagjától függenek ).
Tudjuk majd számítani ezen racionális frakció G ( X ) által törés le egyszerű elemekből , majd bővülő egyes ilyen elemek, mint az előző példákban.
Példa a
Fibonacci-szekvenciára
Ezt a szekvenciát ( F n ) F 0 = 0, F 1 = 1 és F n = F n –1 + F n –2 határozza meg n ≥ 2 esetén. Generáló sorozata ezért
∑nem∈NEMFnemxnem=F0+(F1-F0)x1-x-x2=x1-x-x2{\ displaystyle \ sum _ {n \ in \ mathbb {N}} F_ {n} X ^ {n} = {\ frac {F_ {0} + (F_ {1} -F_ {0}) X} {1 -XX ^ {2}}} = {\ frac {X} {1-XX ^ {2}}}}.
A gyökerek a nevező a inverzeinek arany arány és annak konjugátum :
φ=1+5.2etφ′=1-5.2{\ displaystyle \ varphi = {\ frac {1 + {\ sqrt {5}}} {2}} \ quad {\ rm {et}} \ quad \ varphi '= {\ frac {1 - {\ sqrt {5 }}} {2}}},
úgy hogy
∑nem∈NEMFnemxnem=15.(11-φx-11-φ′x)=15.(∑nem∈NEM(φx)nem-∑nem∈NEM(φ′x)nem){\ displaystyle \ sum _ {n \ in \ mathbb {N}} F_ {n} X ^ {n} = {\ frac {1} {\ sqrt {5}}} \ bal ({\ frac {1} { 1- \ varphi X}} - {\ frac {1} {1- \ varphi 'X}} \ right) = {\ frac {1} {\ sqrt {5}}} \ bal (\ sum _ {n \ itt: \ mathbb {N}} (\ varphi X) ^ {n} - \ sum _ {n \ in \ mathbb {N}} (\ varphi 'X) ^ {n} \ right)}.Binet képletére
következtetünk :
Fnem=15.(φnem-φ′nem){\ displaystyle F_ {n} = {\ frac {1} {\ sqrt {5}}} (\ varphi ^ {n} - \ varphi '^ {n})}.
Szorzás és konvolúció
A két szekvenciát generáló sorozat terméke megfelel a szekvenciák diszkrét konvolúciójának ( Cauchy-terméküknek ). Így a szekvenciája összegzett: ( a 0 , a 0 + egy 1 , a 0 + egy 1 + a 2 , ...) , a szekvencia a generátor sorozat G ( egy n ; x ) olyan generátor-sorozat G ( a n ; x )x/1 - x, Ezek a megfelelő összegek Cauchy terméket a szekvenciája egy n, amely állandó (1, 1, ...).
Diszkrét Fourier-transzformáció
Ha a generátor sorozat abszolút konvergens , a diszkrét Fourier-transzformáció az eredmény volt 0 , a 1 , ... .
G(nál nélnem;e-énω)=∑nem=0∞nál nélneme-énωnem{\ displaystyle G \ left (a_ {n}; e ^ {- i \ omega} \ right) = \ sum _ {n = 0} ^ {\ infty} a_ {n} e ^ {- i \ omega n} }
Generátor sorozat több változóval
Meghatároztuk ( lásd fent ) azt a generáló sorozatot (több változóval), amely több indexű szekvenciához kapcsolódik.
Például a szekvencia generáló sorozatát a binomiális együtthatók két mutatójával könnyen levezethetjük egy korábban látható geometriai szekvencia generáló sorozatából :
G((nemk);x,y){\ displaystyle G \ bal ({\ binom {n} {k}}; x, y \ jobb)}
∑nem,k≥0(nemk)ykxnem=∑nem≥0(1+y)nemxnem=11-x(1+y){\ displaystyle \ sum _ {n, k \ geq 0} {\ binom {n} {k}} y ^ {k} x ^ {n} = \ sum _ {n \ geq 0} \ bal (1 + y \ jobb) ^ {n} x ^ {n} = {\ frac {1} {1-x \ bal (1 + y \ jobb)}}}.
Aszimptotikus viselkedés
A teljes sorozat együtthatóinak növekedési sebességének vizsgálata általánosságban lehetővé teszi e sorozat konvergencia sugarának meghatározását (lásd a d'Alembert cikk szabályát ). Ezzel ellentétben gyakran lehet felhasználni egy generáló sorozat konvergencia sugarának ismeretét a társított szekvencia aszimptotikus viselkedésének levezetésére .
Egy is gyakran meghatározza ezt a aszimptotikus viselkedést segítségével a szinguláris a Holomorf összege funkciója a generátor sorozat, mint látni fogjuk, pontosabban az alábbi 3. példában; Valóban, tudjuk, hogy a sugara konvergencia a sorozat, R , jelentése megegyezik a távolság a szingularitás legközelebb az eredetét, és hogy azután, minden x > r , van egy n = o ( x n ) . Ha például ez a szingularitás pólus , akkor lehetséges egy nagyobb konvergencia-sugárral rendelkező sorozatot felépíteni egy megfelelő függvény levonásával, és a társított szekvencia együtthatóinak pontos aszimptotikus ekvivalensét kapva. Általánosabban, ha a G ( a n ; x ) generátorsor konvergencia sugara egyenlő r-vel , és írható
G(nál nélnem;x)=NÁL NÉL(x)+B(x)(1-x/r)-βxα{\ displaystyle G (a_ {n}; x) = {\ frac {A (x) + B (x) (1-x / r) ^ {- \ beta}} {x ^ {\ alpha}}}},
ahol A ( x ) és B ( x ) analitikai függvények egy r- nél nagyobb sugarú lemezen , és ahol B ( r ) ≠ 0 , akkor
nál nélnem∼B(r)rαΓ(β)nemβ-1(1/r)nem{\ displaystyle a_ {n} \ sim {\ frac {B (r)} {r ^ {\ alpha} \ Gamma (\ beta)}} \, n ^ {\ beta -1} (1 / r) ^ { nem}}(ahol Γ a
gamma funkciót jelöli ).
Az analitikus kombinatorika ennek a kapcsolatnak a gazdag felhasználása a generátor viselkedésének a szingularitásokhoz közeli viselkedése és az együtthatók növekedése között.
1. példa: a négyzetek sorrendje
Amint fentebb bemutattuk, a négyzetsorozat generáló sorozata az . A r = 1, α = 0, β = 3, A ( X ) = 0, és a B ( x ) = x ( x + 1), ellenőrizzük, hogy a négyzetek valóban növekszik n 2 :
x(x+1)(1-x)3{\ displaystyle {\ frac {x (x + 1)} {(1-x) ^ {3}}}}
nál nélnem∼B(r)rαΓ(β)nemβ-1(1/r)nem=1(1+1)10Γ(3)nem3-1(1/1)nem=nem2{\ displaystyle a_ {n} \ sim {\ frac {B (r)} {r ^ {\ alpha} \ Gamma (\ beta)}} \, n ^ {\ beta -1} (1 / r) ^ { n} = {\ frac {1 (1 + 1)} {1 ^ {0} \, \ Gamma (3)}} \, n ^ {3-1} (1/1) ^ {n} = n ^ {2}}.
2. példa: katalán számok
A katalán számsorozat generáló sorozata az
1-1-4x2x{\ displaystyle {\ frac {1 - {\ sqrt {1-4x}}} {2x}}}.
Ha r = 1/4, α = 1, β = −1/2, A ( x ) = 1/2 és B ( x ) = −1/2, arra a következtetésre jutunk, hogy az n- edik katalán szám, C n , jelölje be
VSnem∼B(r)rαΓ(β)nemβ-1(1/r)nem=-1/2(1/4)1Γ(-1/2)nem-1/2-1(11/4)nem=nem-3/24nemπ{\ displaystyle C_ {n} \ sim {\ frac {B (r)} {r ^ {\ alpha} \ Gamma (\ beta)}} \, n ^ {\ beta -1} (1 / r) ^ { n} = {\ frac {-1/2} {(1/4) ^ {1} \ Gamma (-1/2)}} \, n ^ {- 1 / 2-1} \ bal ({\ frac {1} {1/4}} \ right) ^ {n} = {\ frac {n ^ {- 3/2} \, 4 ^ {n}} {\ sqrt {\ pi}}}}.
3. példa: Bernoulli számok
A Bernoulli- számsorozat exponenciális generátor-sorozata az
xex-1=∑k=0∞Bkxkk!{\ displaystyle {\ frac {x} {e ^ {x} -1}} = \ sum _ {k = 0} ^ {\ infty} B_ {k} \, {\ frac {x ^ {k}} { k!}}}.
Ez nem lehetséges közvetlenül alkalmazni az előző eredményt, mert ez a sorozat túl gyakran nulla (azt kell érdekli a sorozat B 2 k ), de könnyen ellenőrizheti, hogy a sugár a konvergencia r = 2π , mivel a pólusok a a funkció z / (e z -1) vannak Z k = 2i k π (a K nem nulla relatív egész szám), amiből arra következtethetünk, hogy az összes ; észrevenni, majd, hogy a funkció már nem rendelkezik az első két pólus, és ezért a sugara konvergenciája r ' = 4π , vezetjük le pontos megfelelője , majd, köszönhetően a Stirling formula ,
Bnem/nem!=o((2π-ε)-nem){\ displaystyle B_ {n} / n! = o ((2 \ pi - \ varepsilon) ^ {- n})}ε>0{\ displaystyle \ varepsilon> 0}z/(ez-1)-2énπ/(z-2énπ)+2énπ/(z+2énπ){\ displaystyle z / (e ^ {z} -1) -2i \ pi / (z-2i \ pi) + 2i \ pi / (z + 2i \ pi)}B2nem/(2nem)!{\ displaystyle B_ {2n} / (2n)!}
|B2nem|∼4πnem(nemπe)2nem{\ displaystyle | B_ {2n} | \ sim 4 {\ sqrt {\ pi n}} \ bal ({\ frac {n} {\ pi e}} \ jobb) ^ {2n}}.
Alkalmazások
Generáló sorozatokat használnak:
- határozzon meg egy egyértelmű képletet a lineáris visszatérő szekvenciákhoz ;
- fordítva, a generáló sorozat formája oda vezethet, hogy meghatározzuk (vagy legalábbis kitaláljuk) egy szekvencia által kielégített ismétlődési relációt. Hasonlóképpen, a generáló sorok közötti kapcsolatok lehetővé teszik a társított szekvenciák közötti kapcsolatok meghatározását;
- tanulmányozza a lakosztályok aszimptotikus viselkedését.
Analitikus kombinatorika
A analitikai kombinatorikai , tanulmányozzuk egy sor számít egy N , számát reprezentáló objektumok mérete n kielégítő, így vagy az ilyen állapot (például a számát permutációk egy sor N betű, vagy a számát polyominoes az n négyzetek) segítségével a kapcsolódó generátorsor (leggyakrabban közönséges vagy exponenciális); Philippe Flajolet és Robert Sedgewick kifejlesztettek egy szisztematikus módszert (a szimbolikus módszert ) e generáló sorozat meghatározására a vizsgált tárgyakra vonatkozó korlátokból.
Példa a szimbolikus módszerre: a katalán számok
A katalán számok (sok más kombinatorikus definíció mellett) a konvex sokszögek háromszögeléseit számlálják . A háromszögelés felfogható úgy, hogy két (esetleg üres) kisebb sokszög háromszögeléséből áll egy megfelelően megválasztott háromszög két oldalán. A szimbolikus módszer ekkor a háromszögelések sorrendjét a „képlettel” ábrázolja , amelyből mechanikusan levezetjük a T ( x ) = 1 + xT ( x ) 2 összefüggést (ahol a T n generáló sorozata , a d 'háromszögelések száma n csúcsú sokszög ). Ennek az egyenletnek a megoldása explicit képlethez vezet , így Taylor képlete arra következtet, hogy az n- edik katalán szám az .
T{\ displaystyle {\ mathcal {T}}}T={ϵ}+T×Δ×T{\ displaystyle {\ mathcal {T}} = \ {\ epsilon \} + {\ mathcal {T}} \ szor \ Delta \ szorzat {\ mathcal {T}}}T(x)=∑nem=0∞Tnemxnem{\ displaystyle T (x) = \ sum _ {n = 0} ^ {\ infty} T_ {n} x ^ {n}}T(x)=1-1-4x2x{\ displaystyle T (x) = {\ frac {1 - {\ sqrt {1-4x}}} {2x}}}Tnem=1nem+1(2nemnem)=(2nem)!(nem+1)!nem!{\ displaystyle T_ {n} = {\ frac {1} {n + 1}} {2n \ select n} = {\ frac {(2n)!} {(n + 1)! \, n!}}}
Több változóval rendelkező generáló sorok alkalmazása a felsorolásra
A kontingenciatáblák számának kiszámítása, vagyis a természetes számok mátrixai megadva a sor- és oszlopösszegeket, több változóval rendelkező generátorsorozat felhasználásával végezhetők el. Mert asztalok, amelyek r sorok és c oszlopok, az összesen sorok t 1 , ..., t r , és azok számára, oszlopok s 1 , ..., s c , Irving John Good bebizonyította, hogy számuk az együttható ban ben
x1t1...xrtry1s1...yvs.svs.{\ displaystyle x_ {1} ^ {t_ {1}} \ ldots x_ {r} ^ {t_ {r}} y_ {1} ^ {s_ {1}} \ ldots y_ {c} ^ {s_ {c} }}
∏én=1r∏j=1vs.11-xényj{\ displaystyle \ prod _ {i = 1} ^ {r} \ prod _ {j = 1} ^ {c} {\ frac {1} {1-x_ {i} y_ {j}}}}.
Valószínűségek
Azok a sorok, amelyek olyan valószínűség-szekvenciát generálnak, amelynek konvergencia sugara szükségszerűen nagyobb, mint 1, általában összekeverik őket a sorozat összegfüggvényével, ezért az ebben az esetben használt generátorfüggvény neve . Különösen a valószínűség-generáló és a pillanat-generáló függvényről beszélünk .
Megjegyzések és hivatkozások
(fr) Ez a cikk részben vagy egészben venni a Wikipedia cikket
angolul című
„ generálása funkció ” ( lásd a szerzők listáját ) .
-
(in) Donald E. Knuth , The Art of Computer Programming , Vol. 1: Alapvető algoritmusok , Addison-Wesley ,2007, 3 e . , 650 p. ( ISBN 978-0-201-89683-1 és 0-201-89683-4 ) „szakasz 1.2.9: generálása funkciók” , p. 86.
-
Flajolet és Sedgewick 2008 , p. 153.
-
Flajolet és Sedgewick 2008 , p. 154.
-
Egy található Flajolet és Sedgewick 2008 , második rész, egy részletes elemzést az általános eset, amikor több szingularitásoknak létezik ugyanazon körben a konvergencia.
-
Flajolet és Sedgewick 2008 , első rész.
-
Részletes elemzést (számokkal együtt) Flajolet és Sedgewick 2008 , p. 35; ezt követi az itt felvázolt szimbolikus számítás.
-
Az átalakítások és a megfelelő ekvivalens számítások elvégzéséhez a függvénykönyvtár (ún. Combstruct ) elérhető a Maple és a Mathematica programokban .
-
(in) IJ Good , " A szimmetrikus Dirichlet-eloszlások és azok elgondolásainak egy alkalmazása a kontingenciatáblákra " , Ann. Statisztika. , vol. 4, n o 6,1986, P. 1159-1189 ( DOI 10.1214 / aos / 1176343649 ).
Lásd is
Bibliográfia
- ( fr ) Peter Doubilet , Gian-Carlo Rota és Richard Stanley : „ A kombinatorikus elmélet alapjairól. VI. A funkciógeneráló gondolat ” , Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability , vol. 2,1972, P. 267-318 ( online olvasás )
- (hu) Philippe Flajolet és Robert Sedgewick , Elemző kombinatorika , Cambridge University Press ,2008( ISBN 0-521-89806-4 , online olvasás )
- (en) Ronald L. Graham , Donald E. Knuth és Oren Patashnik , Konkrét matematika. Számítástudományi Alapítvány , Addison-Wesley ,1994, 2 nd ed. ( ISBN 0-201-55802-5 ) , fejezet. 7. („Funkciók generálása”) , 12. o. 320-380
- en) Herbert S. Wilf , Funkcionológia generálása , Boston, Academic Press ,1994, 2 nd ed. , 228 o. ( ISBN 978-0-12-751956-2 , online olvasás )
Kapcsolódó cikkek
Külső linkek
-
(en) Funkciók, teljesítménymutatók és érmeváltás létrehozása a vágott csomón
-
Simon Plouffe , Sorozatok és néhány sejtés közelítései , mester tézis, 1992
-
(es) Ignacio Larrosa Cañestro, León-Sotelo, Marko Riedel, Georges Zeller, Suma de números equilibrados , hírcsoport es.ciencia.matematicas
-
(en) Funkciók létrehozása , Ed Pegg, Jr. (en) , Wolfram Demonstrations Project , 2007
- (en) RP Stanley , „Funkciók generálása” , G.-C. Rota , kombinatorikai tanulmányok , MAA ,1978( online olvasható ) , p. 100-141
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">