Funcția de generare a secvenței

Funcția generatoare a unei secvențe este un concept algebric care vă permite să lucrați cu diferite obiecte combinatorii prin metode analitice. Ele oferă o modalitate flexibilă de a descrie relațiile în combinatorie și uneori ajută la derivarea unor formule explicite pentru numărul de obiecte combinatorii de un anumit tip.

Dacă este dată o succesiune de numere , atunci se poate construi o serie formală de puteri din ele $\{un}\}$ $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}+\dotsb

care se numeşte funcţia generatoare a acestei secvenţe. $La)$

Un concept strâns legat este funcția generatoare exponențială a unei secvențe , seria de puteri $\{un}\}$

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

al cărui coeficient înainte se împarte la factorialul numărului . $un$ $n$

Note

Adesea, funcția generatoare a unei secvențe de numere este seria Taylor a unei funcții analitice , care poate fi folosită pentru a studia proprietățile secvenței în sine. Cu toate acestea, în cazul general, funcția generatoare nu trebuie să fie analitică. De exemplu, ambele rânduri

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

și

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

au o rază de convergență zero, adică diverg în toate punctele cu excepția zero, iar la zero ambele sunt egale cu 1, adică coincid ca funcții; totuși, ca serii formale diferă.

Proprietăți

Funcția generatoare a sumei (sau diferenței) a două secvențe este egală cu suma (sau diferența) funcțiilor generatoare corespunzătoare.

Produsul funcțiilor și secvențelor generatoare este funcția generatoare a convoluției acestor secvențe: $A(x)=\sum _{{n=0}}^{\infty }a_{n}x^{n}$ $B(x)=\sum _{{n=0}}^{\infty }b_{n}x^{n}$ $\{un}\}$ $\{b_{n}\}$ $c_{n}=\sum _{{k=0}}^{n}a_{k}b_{{nk}}$

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

Dacă și sunt funcții generatoare exponențiale ale secvențelor și , atunci produsul lor este funcția generatoare exponențială a secvenței . $A(x)=\sum _{{n=0}}^{\infty }a_{n}{\frac {x^{n}}{n!)}}$ $B(x)=\sum _{{n=0}}^{\infty }b_{n}{\frac {x^{n}}{n!)}}$ $\{un}\}$ $\{b_{n}\}$ $A(x)\cdot B(x)=\sum _{n=0}^{\infty }c_{n}{\frac {x^{n}}{n!)}}$ $c_{n}=\sum _{{k=0}}^{n}{n \alegeți k}a_{k}b_{{nk}}$

Exemple de utilizare

În combinatorică

Numărul de melodii

Fie numărul de compoziții ale unui întreg nenegativ n de lungime m , adică reprezentări ale lui n sub forma , unde sunt numere întregi nenegative . Numărul este, de asemenea, numărul de combinații cu repetări de la m la n , adică numărul de eșantioane de n elemente care se repetă eventual din mulțime (în acest caz, fiecare membru al compoziției poate fi interpretat ca numărul de i elemente din proba). $B_{m}^{n}$ $n=k_{1}+k_{2}+\cdots +k_{m}$ $\{k_{i}\}$ $B_{m}^{n}$ $\{1,2,\puncte ,m\}$ $k_i$

Pentru un m fix , funcția generatoare a șirului este: $B_{m}^{0},B_{m}^{1},\puncte$

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

Prin urmare, numărul poate fi găsit ca un coeficient at în expansiunea în puteri a lui x . Pentru a face acest lucru, puteți utiliza definiția coeficienților binomi sau puteți lua direct derivata la zero n ori : $B_{m}^{n}$ $x^n$ $(1-x)^{{-m}}$

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

Numărul de grafice conectate

Notați prin numărul tuturor graficelor cu vârfuri și prin numărul tuturor graficelor conectate cu aceste vârfuri. $un$ $\{1,\puncte,n\}$ $c_n$

Rețineți că . În special, este ușor de calculat primii termeni ai acestei secvențe $a_{n}=2^{\binom {n}{2)}$

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

Luați în considerare funcțiile generatoare exponențiale ale acestor secvențe:

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

Ambele serii diverg la , cu toate acestea, ele pot fi considerate ca serii de puteri formale și următoarea relație este valabilă pentru aceste serii: $x\neq 0$

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

ceea ce implică o relație simplă de recurență pentru , care vă permite să găsiți rapid primii membri ai acestei secvențe [1] $c_n$

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

În teoria probabilității

If este o variabilă aleatorie întreagă pozitivă (un caz special al uneia discrete) cu o distribuție de probabilitate $X$

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

atunci așteptarea sa matematică poate fi exprimată în termenii funcției generatoare a șirului $\{p_{i}\}$

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

ca valoare a primei derivate la unitate: (este de remarcat ca seria pentru P(s) converge, cel putin pentru ). Într-adevăr, $M[X]=P'(1)$ $|s|\leq 1$

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

Când înlocuim, obținem valoarea , care, prin definiție, este așteptarea matematică a unei variabile aleatoare discrete. Dacă această serie diverge, atunci - a are o așteptare matematică infinită, $s=1$ $P'(1)=\sum _{{k=1}}^{\infty }{kp_{k}}$ $\lim _{{s\to 1}}P'(s)=\infty$ $X$ $P'(1)=M[X]=\infty$

Acum luăm funcția generatoare a secvenței de „cozi” ale distribuției $Q(e)$ $\{q_{k}\}$

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

Această funcție generatoare este legată de funcția definită anterior prin proprietatea: at . Din aceasta, conform teoremei valorii medii , rezultă că așteptarea matematică este pur și simplu valoarea acestei funcție la unitate: $P(e)$ $Q(s)={\frac {1-P(s)}{1-s}}$ $|s|<1$

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

Diferențiând și folosind relația , obținem: $P'(s)=\sum _{{k=1}}^{\infty }{kp_{k}s^{{k-1}}}$ $P'(s)=Q(s)-(1-s)Q'(s)$

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

Pentru a obține varianța , această expresie trebuie adăugată la , ceea ce duce la următoarele formule pentru calcularea varianței: $D[X]$ $M[X]-M^{2}[X]$

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

În cazul varianţei infinite . $\lim _{{s\to 1}}P''(s)=\infty$

Variații și generalizări

Funcția de generare a Dirichlet

Funcția generatoare a unei secvențe Dirichlet este o serie formală $\{un}\}$

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

Funcția generatoare Dirichlet a șirului de unități 1,1,... este funcția zeta Riemann : $\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s)}}.$

Dacă și sunt funcțiile generatoare de Dirichlet ale secvențelor și , atunci produsul lor este funcția generatoare de Dirichlet a secvenței . $\alpha (s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s)}}$ $\beta (s)=\sum _{n=1}^{\infty }{\frac {b_{n}}{n^{s)))$ $\{un}\}$ $\{b_{n}\}$ $\alpha (s)\cdot \beta (s)=\sum _{n=0}^{\infty }{\frac {c_{n}}{n^{s))}$ $c_{n}=\sum _{d\mid n}a_{d}b_{n/d)$

Istorie

Metoda funcției generatoare a fost dezvoltată de Euler în anii 1750 ; un exemplu clasic este teorema pentagonală a lui Euler .

Note

↑ Harari F., Palmer E. Enumeration of graphs. - Lumea, 1977.

Literatură

Bronstein E. M. Funcții generatoare // Soros Educational Journal . - 2001. - T. 7 , nr 2 . - S. 103-108 .
Voronin S., Kulagin A. Metoda de generare a funcţiilor // Kvant . - 1984. - Nr 5 .
Lando S. K. Prelegeri despre combinatorică . - MTsNMO , 1994.
Lando SK Prelegeri despre generarea de funcţii . - ed. a 3-a, Rev. - M . : MTsNMO , 2007. - 144 p. - ISBN 978-5-94057-042-4 . (link indisponibil)
Tabachnikov S.L., Fuchs D.B. Divertisment matematic. - MTSNMO, 2011. - ISBN 978-5-94057-731-7 .
Rybnikov K.A. Introducere în analiza combinatorie. - Universitatea de Stat din Moscova, 1972.
V. Feller. Capitolul XI. Valori întregi. Funcții generatoare // Introduction to probability theory and its applications = An introduction to probability theory and its applications / Per. din engleza. R. L. Dobrushin, A. A. Yushkevich, S. A. Molchanov; Cu o prefață de A. N. Kolmogorov; Ed. E. B. Dynkina. - Ed. a II-a. - M . : Mir, 1964. - S. 270-272.
Herbert S. Wilf. Functionologie generatoare . - Academic Press, 1994. - ISBN 0-12-751956-4 .

Link -uri

Funcții de generare