Sorozatgeneráló funkció

A sorozat generáló függvénye egy algebrai fogalom, amely lehetővé teszi, hogy különböző kombinatorikus objektumokkal dolgozzon elemzési módszerekkel. Rugalmas módot biztosítanak a kombinatorika összefüggéseinek leírására , és néha segítenek explicit formulák származtatásában az adott típusú kombinatorikus objektumok számához.

Ha adott egy számsorozat , akkor ezekből formális hatványsort szerkeszthetünk $\{a_{n}\}$ $a_{0},a_{1},a_{2},a_{3},\ldots$

A(t)=\sum _{n=0}^{\infty }a_{n}t^{n}=a_{0}+a_{1}t+a_{2}t^{2 }+a_{3}t^{3}+\pontok

amelyet e sorozat generáló függvényének nevezünk . $Nál nél)$

Szorosan kapcsolódó fogalom egy sorozat exponenciális generáló függvénye , a hatványsor $\{a_{n}\}$

A(t)=\sum _{n=0}^{\infty }{\frac {a_{n}t^{n}}{n!)}}=a_{0}+a_{1 } t+{\frac {a_{2}}{2}}t^{2}+{\frac {a_{3}}{6}}t^{3}+\pontb

amelynek előtti együtthatóját elosztjuk a szám faktoriálisával . $a_n$ $n$

Jegyzetek

A számsorozat generáló függvénye gyakran valamilyen analitikus függvény Taylor -sora , amely felhasználható magának a sorozatnak a tulajdonságainak tanulmányozására. Általános esetben azonban a generáló függvénynek nem kell analitikusnak lennie. Például mindkét sor

\sum _{{n=0}}^{\infty }(3^{n})^{n}x^{n}

és

\sum _{{n=0}}^{\infty }(2^{n})^{n}x^{n}

nulla a konvergencia sugara , azaz a nulla kivételével minden pontban eltérnek, és nullánál mindkettő egyenlő 1-gyel, azaz függvényként egybeesnek; formális sorozatként azonban különböznek egymástól.

Tulajdonságok

Két sorozat összegének (vagy különbségének) generáló függvénye egyenlő a megfelelő generáló függvények összegével (vagy különbségével).

A függvények és sorozatok generálásának szorzata ezen sorozatok konvolúciójának generáló függvénye : $A(x)=\összeg _{{n=0}}^{\infty }a_{n}x^{n}$ $B(x)=\összeg _{{n=0}}^{\infty }b_{n}x^{n}$ $\{a_{n}\}$ $\{b_{n}\}$ $c_{n}=\sum _{{k=0}}^{n}a_{k}b_{{nk}}$

A(x)B(x)=\sum _{{n=0}}^{\infty }c_{n}x^{n}.

Ha a és a sorozatok exponenciális generáló függvényei , akkor szorzatuk a sorozat exponenciális generáló függvénye . $A(x)=\sum _{{n=0}}^{\infty }a_{n}{\frac {x^{n}}{n!)}}$ $B(x)=\összeg _{{n=0}}^{\infty }b_{n}{\frac {x^{n}}{n!)}}$ $\{a_{n}\}$ $\{b_{n}\}$ $A(x)\cdot B(x)=\sum _{n=0}^{\infty }c_{n}{\frac {x^{n}}{n!)}}$ $c_{n}=\sum _{{k=0}}^{n}{n \choose k}a_{k}b_{{nk}}$

Használati példák

A kombinatorikában

Dalok száma

Legyen egy m hosszúságú n nem negatív egész szám összetételeinek száma , azaz n alakban szereplő reprezentációi , ahol nemnegatív egész számok . A szám egyben az m - től n -ig ismétlődő kombinációk száma is, azaz a halmazból n esetleg ismétlődő elemből álló minták száma (ebben az esetben az összetétel minden tagja értelmezhető úgy, mint az i elem száma a halmazban a minta). $B_{m}^{n}$ $n=k_{1}+k_{2}+\cdots +k_{m}$ $\{k_{i}\}$ $B_{m}^{n}$ $\{1,2,\pontok ,m\}$ $k_i$

Fix m esetén a sorozat generáló függvénye : $B_{m}^{0},B_{m}^{1},\pontok$

\sum _{{n=0}}^{\infty }B_{m}^{n}x^{n}=(1+x+x^{2}+\cdots )^{m}=(1 -x)^{{-m}}.

Ezért a szám az at együtthatóként található x hatványainak kiterjesztésében . Ehhez használhatja a binomiális együtthatók definícióját, vagy közvetlenül veheti fel a derivált nulla n - szeresével : $B_{m}^{n}$ $x^n$ $(1-x)^{{-m}}$

B_{m}^{n}=(-1)^{n}{-m \choose n}={\frac {m(m+1)\cdots (m+n-1)}{n!)} ={m+n-1 \choose n}.

Összekapcsolt grafikonok száma

Jelölje az összes csúcsú gráfok számával és az ezekkel a csúcsokkal összekapcsolt gráfok számával . $a_n$ $\{1,\pontok,n\}$ $c_n$

Jegyezze meg, hogy . Különösen könnyű kiszámítani ennek a sorozatnak az első tagjait $a_{n}=2^{\binom {n}{2))$

1,\ 2,\ 8,\ 64,\ 1024,\ 32768,\ 2097152,\ \dots

Tekintsük ezeknek a sorozatoknak az exponenciális generáló függvényeit:

a(x)=a_{1}\cdot x+{\tfrac {1}{2}}\cdot a_{2}\cdot x^{2}+\dots +{\tfrac {1}{n !}}\cdot a_{n}\cdot x^{n}+\pontok

c(x)=c_{1}\cdot x+{\tfrac {1}{2}}\cdot c_{2}\cdot x^{2}+\dots +{\tfrac {1}{n !}}\cdot c_{n}\cdot x^{n}+\pontok

Mindkét sorozat eltér a -nál , azonban formális hatványsornak tekinthetők, és a következő összefüggés áll fenn ezekre a sorozatokra: $x\neq 0$

1+a(x)=e^{c(x)},

ami egy egyszerű ismétlődési relációt jelent a számára , amely lehetővé teszi, hogy gyorsan megtalálja ennek a sorozatnak az első tagjait [1] $c_n$

1,\ 1,\ 4,\ 38,\ 728,\ 26704,\ 1866256,\ 251548592,\ 66296291072,\ \dots

A valószínűségszámításban

If egy pozitív egész valószínűségi változó (a diszkrét speciális esete), valószínűségi eloszlással $x$

{\mathbb {P}}(X=j)=p_{j},\;j=0,1,...;\quad \sum \limits _{{j=0}}^{{\infty } }p_{j}=1

akkor annak matematikai elvárása a sorozat generáló függvényével fejezhető ki $\{p_{i}\}$

P(s)=\sum _{{k=0}}^{\infty }\;p_{k}s^{k},

mint az első derivált értéke egységnél: (érdemes megjegyezni, hogy a P(s) sorozat legalábbis konvergál ). Igazán, $M[X]=P'(1)$ $|s|\leq 1$

P'(s)=\sum _{{k=1}}^{\infty }{kp_{k}s^{{k-1}}}.

Behelyettesítéskor az értéket kapjuk , amely definíció szerint egy diszkrét valószínűségi változó matematikai elvárása. Ha ez a sorozat eltér, akkor - a -nak végtelen matematikai elvárása van, $s=1$ $P'(1)=\összeg _{{k=1}}^{\infty }{kp_{k}}$ $\lim _{{s\to 1}}P'(s)=\infty$ $x$ $P'(1)=M[X]=\infty$

Most vesszük az eloszlás "farok" sorozatának generáló függvényét $Q(s)$ $\{q_{k}\}$

q_{k}={\mathbb {P}}(X>k)=\sum _{{j=k+1}}^{\infty }{p_{j}});\quad Q(s)= \ összeg _{{k=0}}^{\infty }\;q_{k}s^{k}.

Ez a generáló függvény a korábban definiált függvényhez kapcsolódik a következő tulajdonsággal: at . Ebből az átlagérték tétel szerint az következik, hogy a matematikai elvárás egyszerűen ennek a függvénynek az egységnyi értéke: $P(ek)$ $Q(s)={\frac {1-P(s)}{1-s}}$ $|s|<1$

M[X]=P'(1)=Q(1)

Megkülönböztetve és a relációt használva a következőt kapjuk: $P'(s)=\sum _{{k=1}}^{\infty }{kp_{k}s^{{k-1}}}$ $P'(ek)=Q(s)-(1-s)Q'(s)$

M[X(X-1)]=\összeg {k(k-1)p_{k}}=P''(1)=2Q'(1)

Az eltérés kiszámításához ezt a kifejezést hozzá kell adni a -hoz , ami a következő képletekhez vezet a variancia kiszámításához: $D[X]$ $M[X]-M^{2}[X]$

D[X]=P''(1)+P'(1)-P'^{2}(1)=2Q'(1)+Q(1)-Q^{2}(1)

Végtelen szórás esetén . $\lim _{{s\to 1}}P''(s)=\infty$

Változatok és általánosítások

Dirichlet generáló függvény

A Dirichlet-sorozat generáló függvénye egy formális sorozat $\{a_{n}\}$

{\displaystyle \sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s))))

Az 1,1,… egységsorozat Dirichlet-generáló függvénye a Riemann zéta függvény : $\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s))}.$

Ha és a sorozatok Dirichlet-generáló függvényei és , akkor szorzatuk a sorozat Dirichlet-generáló függvénye . ${\displaystyle \alpha (s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s))))$ ${\displaystyle \beta (s)=\sum _{n=1}^{\infty }{\frac {b_{n}}{n^{s))))$ $\{a_{n}\}$ $\{b_{n}\}$ ${\displaystyle \alpha (s)\cdot \beta (s)=\sum _{n=0}^{\infty }{\frac {c_{n}}{n^{s))))$ ${\displaystyle c_{n}=\sum _{d\mid n}a_{d}b_{n/d))$

Történelem

A generáló függvény módszerét Euler fejlesztette ki az 1750 -es években ; klasszikus példa erre Euler ötszögletű tétele .

Jegyzetek

↑ Harari F., Palmer E. Grafikonok felsorolása. - Világ, 1977.

Irodalom

Bronstein E. M. Funkciók generálása // Soros Educational Journal . - 2001. - T. 7 , 2. sz . - S. 103-108 .
Voronin S., Kulagin A. A függvénygenerálás módszere // Kvant . - 1984. - 5. sz .
Lando S. K. Előadások a kombinatorikáról . – MTsNMO , 1994.
Lando SK Előadások a függvények generálásáról . - 3. kiadás, Rev. - M . : MTsNMO , 2007. - 144 p. - ISBN 978-5-94057-042-4 . (nem elérhető link)
Tabachnikov S.L., Fuchs D.B. Matematikai divertisment. - MTSNMO, 2011. - ISBN 978-5-94057-731-7 .
Rybnikov K.A. Bevezetés a kombinatorikus elemzésbe. - Moszkvai Állami Egyetem, 1972.
V. Feller. fejezet XI. Egész értékek. Függvények generálása // Bevezetés a valószínűségszámításba és annak alkalmazásaiba = Bevezetés a valószínűségszámításba és annak alkalmazásaiba / Per. angolról. R. L. Dobrusin, A. A. Juskevics, S. A. Molcsanov; A. N. Kolmogorov előszavával; Szerk. E. B. Dynkina. - 2. kiadás - M . : Mir, 1964. - S. 270-272.
Herbert S. Wilf. Funkcionológia generálása . - Academic Press, 1994. - ISBN 0-12-751956-4 .

Linkek

Funkciók generálása