Sekvensgenererande funktion

Den genererande funktionen för en sekvens är ett algebraiskt koncept som låter dig arbeta med olika kombinatoriska objekt med analytiska metoder. De tillhandahåller ett flexibelt sätt att beskriva samband i kombinatorik , och ibland hjälper de till att härleda explicita formler för antalet kombinatoriska objekt av en viss typ.

Om en talföljd ges , då kan man konstruera en formell potensserie från dem $\{en}\}$ $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

som kallas genereringsfunktionen för denna sekvens. $På)$

Ett närbesläktat koncept är den exponentiella genererande funktionen av en sekvens , potensserien $\{en}\}$

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

vars koefficient före divideras med talets faktorial . $en$ $n$

Anteckningar

Ofta är den genererande funktionen för en talsekvens Taylor-serien av någon analytisk funktion , som kan användas för att studera egenskaperna hos själva sekvensen. Men i det allmänna fallet behöver genereringsfunktionen inte vara analytisk. Till exempel båda raderna

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

och

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

har en konvergensradie på noll, det vill säga de divergerar vid alla punkter utom noll, och vid noll är båda lika med 1, det vill säga de sammanfaller som funktioner; som formella serier skiljer de sig dock åt.

Egenskaper

Genereringsfunktionen för summan (eller skillnaden) av två sekvenser är lika med summan (eller skillnaden) av motsvarande genererande funktioner.

Produkten av att generera funktioner och sekvenser är den genererande funktionen av faltningen av dessa sekvenser: $A(x)=\summa _{{n=0}}^{\infty }a_{n}x^{n}$ $B(x)=\summa _{{n=0}}^{\infty }b_{n}x^{n}$ $\{en}\}$ $\{b_{n}\}$ $c_{n}=\summa _{{k=0}}^{n}a_{k}b_{{nk}}$

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

Om och är exponentiellt genererande funktioner för sekvenserna och , då är deras produkt den exponentiellt genererande funktionen för sekvensen . $A(x)=\summa _{{n=0}}^{\infty }a_{n}{\frac {x^{n}}{n!)}}$ $B(x)=\summa _{{n=0}}^{\infty }b_{n}{\frac {x^{n}}{n!)}}$ $\{en}\}$ $\{b_{n}\}$ $A(x)\cdot B(x)=\sum _{n=0}^{\infty }c_{n}{\frac {x^{n}}{n!)}}$ $c_{n}=\summa _{{k=0}}^{n}{n \choose k}a_{k}b_{{nk}}$

Användningsexempel

I kombinatorik

Antal låtar

Låta vara antalet sammansättningar av ett icke-negativt heltal n av längden m , det vill säga representationer av n i formen , Där är icke-negativa heltal . Antalet är också antalet kombinationer med repetitioner från m till n , det vill säga antalet sampel av n möjligen upprepande element från mängden (i detta fall kan varje medlem i kompositionen tolkas som antalet i element i provexemplaret). $B_{m}^{n}$ $n=k_{1}+k_{2}+\cdots +k_{m}$ $\{k_{i}\}$ $B_{m}^{n}$ $\{1,2,\dots ,m\}$ $k_i$

För en fast m är sekvensens genererande funktion : $B_{m}^{0},B_{m}^{1},\dots$

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

Därför kan talet hittas som en koefficient vid i expansionen i potenser av x . För att göra detta kan du använda definitionen av binomialkoefficienter eller direkt ta derivatan vid noll n gånger : $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 \välj n}.

Antal anslutna grafer

Beteckna med antalet av alla grafer med hörn och med antalet anslutna grafer med dessa hörn. $en$ $\{1,\dots,n\}$ $c_n$

Observera att . I synnerhet är det lätt att beräkna de första termerna i denna sekvens $a_{n}=2^{\binom {n}{2))$

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

Betrakta de exponentiella genererande funktionerna för dessa sekvenser:

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

Båda serierna divergerar vid , men de kan betraktas som formella potensserier, och följande relation gäller för dessa serier: $x\neq 0$

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

vilket innebär en enkel återkommande relation för , vilket gör att du snabbt kan hitta de första medlemmarna i denna sekvens [1] $c_n$

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

I sannolikhetsteorin

If är en positiv heltalsvariabel ( ett specialfall av en diskret) med en sannolikhetsfördelning $X$

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

då kan dess matematiska förväntan uttryckas i termer av sekvensens genererande funktion $\{pi}\}$

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

som värdet av den första derivatan vid enhet: (det är värt att notera att serien för P(s) konvergerar, åtminstone för ). Verkligen, $M[X]=P'(1)$ $|s|\leq 1$

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

När vi ersätter får vi värdet , som per definition är den matematiska förväntan av en diskret slumpvariabel. Om denna serie divergerar, då - a har en oändlig matematisk förväntning, $s=1$ $P'(1)=\summa _{{k=1}}^{\infty }{kp_{k}}$ $\lim _{{s\to 1}}P'(s)=\infty$ $X$ $P'(1)=M[X]=\infty$

Nu tar vi den genererande funktionen av sekvensen av "svansar" av fördelningen $Frågor$ $\{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}.

Denna genererande funktion är relaterad till den tidigare definierade funktionen av egenskapen: at . Av detta, enligt medelvärdessatsen , följer det att den matematiska förväntan helt enkelt är värdet av denna funktion vid enhet: $P(s)$ $Q(s)={\frac {1-P(s)}{1-s}}$ $|s|<1$

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

Genom att differentiera och använda relationen får vi: $P'(s)=\summa _{{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)

För att få variansen måste detta uttryck läggas till , vilket leder till följande formler för att beräkna variansen: $D[X]$ $M[X]-M^{2}[X]$

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

Vid oändlig varians . $\lim _{{s\to 1}}P''(s)=\infty$

Variationer och generaliseringar

Dirichlet genererande funktion

Den genererande funktionen för en Dirichlet-sekvens är en formell serie $\{en}\}$

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

Den Dirichlet-genererande funktionen för sekvensen av enheter 1,1,... är Riemann zeta-funktionen : $\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s))}.$

Om och är de Dirichlet-genererande funktionerna för sekvenserna och , då är deras produkt den Dirichlet-genererande funktionen för sekvensen . ${\displaystyle \alpha (s)=\summa _{n=1}^{\infty }{\frac {a_{n}}{n^{s))))$ ${\displaystyle \beta (s)=\summa _{n=1}^{\infty }{\frac {b_{n}}{n^{s))))$ $\{en}\}$ $\{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))$

Historik

Den genererande funktionsmetoden utvecklades av Euler på 1750 -talet ; ett klassiskt exempel är Eulers femkantiga teorem .

Anteckningar

↑ Harari F., Palmer E. Uppräkning av grafer. - Världen, 1977.

Litteratur

Bronstein E. M. Genererande funktioner // Soros Educational Journal . - 2001. - T. 7 , nr 2 . - S. 103-108 .
Voronin S., Kulagin A. Metoden för att generera funktioner // Kvant . - 1984. - Nr 5 .
Lando S. K. Föreläsningar om kombinatorik . — MTsNMO , 1994.
Lando SK Föreläsningar om genererande funktioner . - 3:e upplagan, Rev. - M . : MTsNMO , 2007. - 144 sid. - ISBN 978-5-94057-042-4 . (inte tillgänglig länk)
Tabachnikov S.L., Fuchs D.B. Matematisk divertissement. - MTSNMO, 2011. - ISBN 978-5-94057-731-7 .
Rybnikov K.A. Introduktion till kombinatorisk analys. - Moscow State University, 1972.
V. Feller. Kapitel XI. Heltalsvärden. Genererande funktioner // Introduktion till sannolikhetsteori och dess tillämpningar = En introduktion till sannolikhetsteori och dess tillämpningar / Per. från engelska. R.L. Dobrushin, A.A. Yushkevich, S.A. Molchanov; Med ett förord av A. N. Kolmogorov; Ed. E. B. Dynkina. - 2:a uppl. - M . : Mir, 1964. - S. 270-272.
Herbert S. Wilf. Generera funktionologi . - Academic Press, 1994. - ISBN 0-12-751956-4 .

Länkar

Genererar funktioner