Sekvenssin luontitoiminto

Sekvenssin generointifunktio on algebrallinen käsite, jonka avulla voit työskennellä eri kombinatoristen objektien kanssa analyyttisin menetelmin. Ne tarjoavat joustavan tavan kuvata suhteita kombinatoriikassa ja joskus auttavat johtamaan eksplisiittisiä kaavoja tietyntyyppisten kombinatoristen objektien lukumäärälle.

Jos lukujono on annettu , niin niistä voidaan muodostaa muodollinen potenssisarja $\{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}+\pisteetb

jota kutsutaan tämän sekvenssin generoivaksi funktioksi. $A(t)$

Läheisesti liittyvä käsite on sekvenssin eksponentiaalinen generoiva funktio , potenssisarja $\{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}+\pisteetb

jonka kerroin ennen jaetaan luvun kertoimella . $a_n$ $n$

Muistiinpanot

Usein lukujonon generoiva funktio on jonkin analyyttisen funktion Taylor-sarja , jonka avulla voidaan tutkia itse sarjan ominaisuuksia. Yleisessä tapauksessa generoivan funktion ei kuitenkaan tarvitse olla analyyttinen. Esimerkiksi molemmat rivit

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

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

niiden konvergenssisäde on nolla, eli ne eroavat kaikissa pisteissä paitsi nolla, ja nollassa molemmat ovat yhtä suuria kuin 1, eli ne ovat funktioina samat; muodollisina sarjoina ne kuitenkin eroavat toisistaan.

Ominaisuudet

Kahden sekvenssin summan (tai erotuksen) generoiva funktio on yhtä suuri kuin vastaavien generointifunktioiden summa (tai erotus).

Funktioiden ja sekvenssien generointitulos on näiden sekvenssien konvoluution generoiva funktio : $A(x)=\summa _{{n=0}}^{\infty }a_{n}x^{n}$ $B(x)=\summa _{{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)=\summa _{{n=0}}^{\infty }c_{n}x^{n}.

Jos ja ovat sekvenssien ja eksponentiaalisia generoivia funktioita , niin niiden tulo on sekvenssin eksponentiaalinen generoiva funktio . $A(x)=\sum _{{n=0}}^{\infty }a_{n}{\frac {x^{n}}{n!)}}$ $B(x)=\summa _{{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}}$

Käyttöesimerkkejä

Kombinatoriikassa

Kappaleiden määrä

Antaa olla ei-negatiivisen kokonaisluvun n , jonka pituus on m , kokoonpanojen lukumäärä , eli n: n esitykset muodossa , jossa ovat ei-negatiivisia kokonaislukuja . Luku on myös toistojen lukumäärä m :stä n :ään eli n mahdollisesti toistuvan alkion näytteiden lukumäärä joukosta (tässä tapauksessa jokainen koostumuksen jäsen voidaan tulkita i -elementtien lukumääräksi näyte). $B_{m}^{n}$ $n=k_{1}+k_{2}+\cdots +k_{m}$ $\{k_{i}\}$ $B_{m}^{n}$ $\{1,2,\pisteet ,m\}$ $k_i$

Kiinteälle m :lle sekvenssin generoiva funktio on: $B_{m}^{0},B_{m}^{1},\pisteet$

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

Siksi luku voidaan löytää kertoimena at x :n potenssien laajennuksessa . Voit tehdä tämän käyttämällä binomikertoimien määritelmää tai ottaa derivaatan suoraan nollalla n kertaa : $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 \valitse n}.

Yhdistettyjen kaavioiden määrä

Merkitään kaikkien graafien lukumäärällä, joissa on kärkipisteet , ja kaikkien näillä pisteillä yhdistettyjen graafien lukumäärällä. $a_n$ $\{1,\pisteet,n\}$ $c_n$

Huomaa, että . Erityisesti tämän sarjan ensimmäisten termien laskeminen on helppoa $a_{n}=2^{\binom {n}{2))$

{\näyttötyyli 1,\ 2,\ 8,\ 64,\ 1024,\ 32768,\ 2097152,\ \pisteet }

Harkitse näiden sekvenssien eksponentiaalisia generointifunktioita:

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}+\dots

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}+\dots

Molemmat sarjat eroavat arvolla , mutta niitä voidaan pitää muodollisina potenssisarjoina, ja näille sarjoille pätee seuraava suhde: $x\neq 0$

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

mikä tarkoittaa yksinkertaista toistumisrelaatiota , jonka avulla voit nopeasti löytää tämän sekvenssin ensimmäiset jäsenet [1] $c_n$

{\näyttötyyli 1,\ 1,\ 4,\ 38,\ 728,\ 26704,\ 1866256,\ 251548592,\ 66296291072,\ \dots }

Todennäköisyysteoriassa

If on positiivinen kokonaisluku satunnaismuuttuja (diskreetin erikoistapaus), jolla on todennäköisyysjakauma $X$

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

silloin sen matemaattinen odotus voidaan ilmaista sekvenssin generoivana funktiona $\{p_{i}\}$

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

ensimmäisen derivaatan arvona yksikössä: (on syytä huomata, että sarja P(s) konvergoi, ainakin ). Todella, $M[X]=P'(1)$ $|s|\leq 1$

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

Korvaamalla saamme arvon , joka määritelmän mukaan on diskreetin satunnaismuuttujan matemaattinen odotus. Jos tämä sarja poikkeaa, niin - a :lla on ääretön matemaattinen odotus, $s = 1$ $P'(1)=\summa _{{k=1}}^{\infty }{kp_{k}}$ $\lim _{{s\to 1}}P'(s)=\infty$ $X$ $P'(1)=M[X]=\infty$

Otetaan nyt jakauman "pyrstöjen" sekvenssin generoiva funktio $Q(t)$ $\{q_{k}\}$

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

Tämä generoiva funktio liittyy aiemmin määritettyyn funktioon ominaisuudella: at . Tästä seuraa keskiarvolauseen mukaan , että matemaattinen odotus on yksinkertaisesti tämän funktion arvo yksikössä: $P(t)$ $Q(s)={\frac {1-P(s)}{1-s}}$ $|s|<1$

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

Erottamalla ja käyttämällä suhdetta saamme: $P'(s)=\sum _{{k=1}}^{\infty }{kp_{k}s^{{k-1}}}$ $P'(s) = Q(s)-(1-s)Q'(s)$

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

Varianssin saamiseksi tämä lauseke on lisättävä kohtaan , mikä johtaa seuraaviin kaavoihin varianssin laskemiseksi: $D[X]$ $M[X]-M^{2}[X]$

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

Äärettömän varianssin tapauksessa . $\lim _{{s\to 1}}P''(s)=\infty$

Muunnelmia ja yleistyksiä

Dirichlet-generointifunktio

Dirichlet-sekvenssin generoiva funktio on muodollinen sarja $\{a_{n}\}$

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

Yksiköiden sekvenssin 1,1,… Dirichletin generoiva funktio on Riemannin zeta-funktio : $\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s))}.$

Jos ja ovat sekvenssien Dirichletin generoivia funktioita ja , niin niiden tulo on sekvenssin Dirichletin generoiva funktio . ${\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))$

Historia

Euler kehitti generointifunktion menetelmän 1750- luvulla ; klassinen esimerkki on Eulerin viisikulmainen lause .

Muistiinpanot

↑ Harari F., Palmer E. Graafeiden luettelointi. - Maailma, 1977.

Kirjallisuus

Bronstein E. M. Toimintojen luominen // Soros Educational Journal . - 2001. - T. 7 , nro 2 . - S. 103-108 .
Voronin S., Kulagin A. Funktioiden generointimenetelmä // Kvant . - 1984. - Nro 5 .
Lando S. K. Luennot kombinatoriikasta . – MTsNMO , 1994.
Lando SK Luennot generointifunktioista . - 3. painos, Rev. - M . : MTsNMO , 2007. - 144 s. - ISBN 978-5-94057-042-4 . (linkki ei saatavilla)
Tabachnikov S.L., Fuchs D.B. Matemaattinen suuntaaminen. - MTSNMO, 2011. - ISBN 978-5-94057-731-7 .
Rybnikov K.A. Johdatus kombinatoriseen analyysiin. - Moskovan valtionyliopisto, 1972.
V. Feller. XI luku. Kokonaislukuarvot. Funktioiden generointi // Johdatus todennäköisyysteoriaan ja sen sovelluksiin = An Johdatus todennäköisyysteoriaan ja sen sovelluksiin / Per. englannista. R. L. Dobrushin, A. A. Juskevitš, S. A. Molchanov; A. N. Kolmogorovin esipuheella; Ed. E. B. Dynkina. - 2. painos - M .: Mir, 1964. - S. 270-272.
Herbert S. Wilf. Funktionologian luominen . - Academic Press, 1994. - ISBN 0-12-751956-4 .

Linkit

Toimintojen luominen