Funcție generatoare

În matematică o funcție generatoare este o serie de puteri formale ai cărei coeficienți sunt componentele lui _n într- o succesiune indexată cu numere naturale ; de multe ori această succesiune este reprezentată efectiv de funcția generatoare, mai ales atunci când se găsește o expresie suficient de ușor de gestionat și semnificativă pentru aceasta.

Sunt studiate diferite tipuri de funcții de generare, cum ar fi funcțiile de generare obișnuite , funcțiile de generare exponențiale , seria Lambert , seria Bell și seria Dirichlet ; definițiile și câteva exemple sunt date mai jos. Funcțiile de generare de toate tipurile pot fi asociate fiecărei secvențe. Care funcție generatoare particulară este cea mai utilă într-un context dat depinde de natura secvenței și de detaliile problemei abordate.

Funcțiile de generare se găsesc adesea într-o formă închisă ca funcții ale unei variabile formale x . Uneori este util să evaluați o funcție generatoare pentru o anumită valoare reală sau complexă a lui x . Cu toate acestea, trebuie avut în vedere faptul că funcțiile de generare sunt serii formale de putere și convergența nu este neapărat necesară pentru anumite valori atribuite lui x .

Definiție

O funcție generatoare este o linie de îmbrăcăminte utilizată pentru a agăța o secvență de numere pentru afișare.

- Herbert Wilf, funcționare generatoare (1994)

Funcție generatoare obișnuită

Funcția generatoare obișnuită a unei secvențe a _n este

G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.

{\ displaystyle G (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {n} x ^ {n}.}

{\ displaystyle G (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {n} x ^ {n}.}

Când termenul funcție generatoare este utilizat fără calificare, se înțelege de obicei că este o funcție generatoare obișnuită.

Dacă secvența a _n este o funcție de probabilitate de masă a unei variabile aleatorii discrete , atunci funcția sa generatoare obișnuită se numește funcție generatoare de probabilitate .

Funcția generatoare obișnuită poate fi generalizată la secvențe relative la mai mulți indici. De exemplu, funcția obișnuită de a genera o succesiune _{m, n} (cu n și m numere naturale) are forma

G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.

{\ displaystyle G (a_ {m, n}; x, y) = \ sum _ {m, n = 0} ^ {\ infty} a_ {m, n} x ^ {m} y ^ {n}.}

{\ displaystyle G (a_ {m, n}; x, y) = \ sum _ {m, n = 0} ^ {\ infty} a_ {m, n} x ^ {m} y ^ {n}.}

Funcție generatoare exponențială

Funcția generatoare exponențială a unei secvențe a _n este

EG(a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.

{\ displaystyle EG (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {n} {\ frac {x ^ {n}} {n!}}.}

{\ displaystyle EG (a_ {n}; x) = \ sum _ {n = 0} ^ {\ infty} a_ {n} {\ frac {x ^ {n}} {n!}}.}

Seria Lambert

Seria Lambert a unei secvențe în _n este

LG(a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.

{\ displaystyle LG (a_ {n}; x) = \ sum _ {n = 1} ^ {\ infty} a_ {n} {\ frac {x ^ {n}} {1-x ^ {n}}} .}

{\ displaystyle LG (a_ {n}; x) = \ sum _ {n = 1} ^ {\ infty} a_ {n} {\ frac {x ^ {n}} {1-x ^ {n}}} .}

Rețineți că într-o serie Lambert indicele n are ca primă valoare 1, nu 0.

Seria Bell

Seria Bell asociată cu o funcție aritmetică f ( n ) și un număr prim p este

f_{p}(x):=\sum _{n=0}^{\infty }f(p^{n})x^{n}.

{\ displaystyle f_ {p} (x): = \ sum _ {n = 0} ^ {\ infty} f (p ^ {n}) x ^ {n}.}

{\ displaystyle f_ {p} (x): = \ sum _ {n = 0} ^ {\ infty} f (p ^ {n}) x ^ {n}.}

Seria Dirichlet

Seriile Dirichlet sunt în general clasificate ca funcții generatoare, deși strict vorbind nu sunt serii formale de putere. Funcția generatoare a seriei Dirichlet a unei secvențe la _n este

DG(a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.

{\ displaystyle DG (a_ {n}; s) = \ sum _ {n = 1} ^ {\ infty} {\ frac {a_ {n}} {n ^ {s}}}.}

{\ displaystyle DG (a_ {n}; s) = \ sum _ {n = 1} ^ {\ infty} {\ frac {a_ {n}} {n ^ {s}}}.}

Funcția de generare a seriei Dirichlet este utilă mai ales atunci când a _n este o funcție multiplicativă , adică atunci când are o expresie a produsului Euler în ceea ce privește seria Bell a funcției

DG(a_{n};s)=\prod _{p}f_{p}(p^{-s}).

{\ displaystyle DG (a_ {n}; s) = \ prod _ {p} f_ {p} (p ^ {- s}).}

{\ displaystyle DG (a_ {n}; s) = \ prod _ {p} f_ {p} (p ^ {- s}).}

Dacă a _n este un caracter Dirichlet , atunci funcția generatoare cu seria Dirichlet se numește seria Dirichlet L.

Secvențe polinomiale

Noțiunea de funcție generatoare poate fi extinsă la secvențe de obiecte care nu sunt numere simple. Astfel, de exemplu, secvențele polinomiale de tip binomial sunt generate de

e^{xf(t)}=\sum _{n=0}^{\infty }{p_{n}(x) \over n!}t^{n},

{\ displaystyle e ^ {xf (t)} = \ sum _ {n = 0} ^ {\ infty} {p_ {n} (x) \ over n!} t ^ {n},}

{\ displaystyle e ^ {xf (t)} = \ sum _ {n = 0} ^ {\ infty} {p_ {n} (x) \ over n!} t ^ {n},}

unde p _n ( x ) este o secvență polinomială și f ( t ) o funcție a unei forme date. Secvențele Sheffer sunt generate în mod similar. Pentru mai multe informații despre acest subiect, consultați intrarea principală Appell's Generalized Polynomials .

Secvența pătratelor

Să examinăm funcțiile de generare pentru succesiunea pătratelor perfecte la _n = n ² .

Funcție generatoare obișnuită

G(n^{2};x)=\sum _{n=0}^{\infty }n^{2}x^{n}={\frac {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}}}.}

{\ displaystyle G (n ^ {2}; x) = \ sum _ {n = 0} ^ {\ infty} n ^ {2} x ^ {n} = {\ frac {x (x + 1)} { (1-x) ^ {3}}}.}

Funcție generatoare exponențială

EG(n^{2};x)=\sum _{n=0}^{\infty }{\frac {n^{2}x^{n}}{n!}}=x(x+1)e^{x}.

{\ displaystyle EG (n ^ {2}; x) = \ sum _ {n = 0} ^ {\ infty} {\ frac {n ^ {2} x ^ {n}} {n!}} = x ( x + 1) și ^ {x}.}

{\ displaystyle EG (n ^ {2}; x) = \ sum _ {n = 0} ^ {\ infty} {\ frac {n ^ {2} x ^ {n}} {n!}} = x ( x + 1) și ^ {x}.}

Seria Bell

f_{p}(x)=\sum _{n=0}^{\infty }p^{2n}x^{n}={\frac {1}{1-p^{2}x}}.

{\ displaystyle f_ {p} (x) = \ sum _ {n = 0} ^ {\ infty} p ^ {2n} x ^ {n} = {\ frac {1} {1-p ^ {2} x }}.}

{\ displaystyle f_ {p} (x) = \ sum _ {n = 0} ^ {\ infty} p ^ {2n} x ^ {n} = {\ frac {1} {1-p ^ {2} x }}.}

Funcție generatoare cu seria Dirichlet

DG(n^{2};s)=\sum _{n=1}^{\infty }{\frac {n^{2}}{n^{s}}}=\zeta (s-2).

{\ displaystyle DG (n ^ {2}; s) = \ sum _ {n = 1} ^ {\ infty} {\ frac {n ^ {2}} {n ^ {s}}} = \ zeta (s -2).}

{\ displaystyle DG (n ^ {2}; s) = \ sum _ {n = 1} ^ {\ infty} {\ frac {n ^ {2}} {n ^ {s}}} = \ zeta (s -2).}

Exemple

Exemplu IT

În informatică, funcțiile de generare sunt utilizate pe scară largă, în special în ceea ce privește analiza algoritmilor . De exemplu, doriți să determinați de câte ori se execută un bloc de instrucțiuni într-un construct iterativ.

CAZUL A

 ...
pentru (i = 1; i <= n; i ++)
{printf („salut”);}
...

În acest caz, imprimăm șirul salut pentru iterații variind de la 1 la n . O înțelegem așa

\sum _{i=1}^{n}1=n,

{\ displaystyle \ sum _ {i = 1} ^ {n} 1 = n,}

{\ displaystyle \ sum _ {i = 1} ^ {n} 1 = n,}

presupunând că imprimarea șirului de salut are un cost uniform.

CAZUL B

 ...
pentru (i = 1; i <= n; i ++)
pentru (j = 1; j <= i; j ++)
{printf („salut”);}
...

șirul salut este tipărit o dată la fiecare iterație a buclei interioare (j) și ori la fiecare iterație a buclei exterioare (i). Per total:

\sum _{i=1}^{n}\sum _{j=1}^{i}1=\sum _{i=1}^{n}i={\frac {n(n+1)}{2}},

{\ displaystyle \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {i} 1 = \ sum _ {i = 1} ^ {n} i = {\ frac {n (n +1)} {2}},}

{\ displaystyle \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {i} 1 = \ sum _ {i = 1} ^ {n} i = {\ frac {n (n +1)} {2}},}

amintind de formula lui Gauss .

În general, având k cicluri altoite, se conduce înapoi la calcularea unei însumări a formei

\sum _{i_{1}=1}^{n}\sum _{i_{2}=1}^{i_{1}}...\sum _{i_{k}=1}^{i_{k-1}}1.

{\ displaystyle \ sum _ {i_ {1} = 1} ^ {n} \ sum _ {i_ {2} = 1} ^ {i_ {1}} ... \ sum _ {i_ {k} = 1} ^ {i_ {k-1}} 1.}

{\ displaystyle \ sum _ {i_ {1} = 1} ^ {n} \ sum _ {i_ {2} = 1} ^ {i_ {1}} ... \ sum _ {i_ {k} = 1} ^ {i_ {k-1}} 1.}

CAZUL C

 pentru (i = 1; i <= n; i ++)
pentru (j = 1; j <= i; j ++)
pentru (k = 1; k <= j; k ++)
{printf („salut”);}

\sum _{i=1}^{n}\sum _{j=1}^{i}\sum _{k=1}^{j}1=\sum _{i=1}^{n}\sum _{j=1}^{i}j=\sum _{i=1}^{n}{\frac {i(i+1)}{2}}.

{\ displaystyle \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {i} \ sum _ {k = 1} ^ {j} 1 = \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {i} j = \ sum _ {i = 1} ^ {n} {\ frac {i (i + 1)} {2}}.}

{\ displaystyle \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {i} \ sum _ {k = 1} ^ {j} 1 = \ sum _ {i = 1} ^ {n} \ sum _ {j = 1} ^ {i} j = \ sum _ {i = 1} ^ {n} {\ frac {i (i + 1)} {2}}.}

Acesta din urmă trebuie calculat. Prin urmare:

\sum _{i=1}^{n}{\frac {i(i+1)}{2}}={\frac {1}{2}}\left(\sum _{i=1}^{n}i^{2}+\sum _{i=1}^{n}i\right)={\frac {n(n+1)(2n+1)}{2\cdot 6}}+{\frac {n(n+1)}{2\cdot 2}}={\frac {n^{3}}{6}}+{\frac {n^{2}}{2}}+{\frac {n}{3}}.

{\ displaystyle \ sum _ {i = 1} ^ {n} {\ frac {i (i + 1)} {2}} = {\ frac {1} {2}} \ left (\ sum _ {i = 1} ^ {n} i ^ {2} + \ sum _ {i = 1} ^ {n} i \ right) = {\ frac {n (n + 1) (2n + 1)} {2 \ cdot 6 }} + {\ frac {n (n + 1)} {2 \ cdot 2}} = {\ frac {n ^ {3}} {6}} + {\ frac {n ^ {2}} {2} } + {\ frac {n} {3}}.}

{\ displaystyle \ sum _ {i = 1} ^ {n} {\ frac {i (i + 1)} {2}} = {\ frac {1} {2}} \ left (\ sum _ {i = 1} ^ {n} i ^ {2} + \ sum _ {i = 1} ^ {n} i \ right) = {\ frac {n (n + 1) (2n + 1)} {2 \ cdot 6 }} + {\ frac {n (n + 1)} {2 \ cdot 2}} = {\ frac {n ^ {3}} {6}} + {\ frac {n ^ {2}} {2} } + {\ frac {n} {3}}.}

Manipularea unei funcții generatoare

Funcțiile de generare pot fi construite prin îmbogățirea formei de funcții de generare mai simple. De exemplu, să începem cu

G(1;x)=\sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}

{\ displaystyle G (1; x) = \ sum _ {n = 0} ^ {\ infty} x ^ {n} = {\ frac {1} {1-x}}}

{\ displaystyle G (1; x) = \ sum _ {n = 0} ^ {\ infty} x ^ {n} = {\ frac {1} {1-x}}}

și înlocuiți $X$ ${\ displaystyle x}$ $X$ cu $2x$ ${\ displaystyle 2x}$ $2x$ ; noi obținem

G(1;2x)={\frac {1}{1-2x}}=1+(2x)+(2x)^{2}+\ldots +(2x)^{n}+\ldots =G(2^{n};x).

{\ displaystyle G (1; 2x) = {\ frac {1} {1-2x}} = 1+ (2x) + (2x) ^ {2} + \ ldots + (2x) ^ {n} + \ ldots = G (2 ^ {n}; x).}

{\ displaystyle G (1; 2x) = {\ frac {1} {1-2x}} = 1+ (2x) + (2x) ^ {2} + \ ldots + (2x) ^ {n} + \ ldots = G (2 ^ {n}; x).}

Numere Fibonacci

Același subiect în detaliu: numerele Fibonacci .

Să luăm în considerare problema găsirii unei formule închise pentru numerele Fibonacci f _n definite de f ₀ : = 0, f ₁ : = 1 și f _n : = f _{n −1} + f _{n −2} pentru n ≥ 2. Compunem funcția generatrix obișnuită

f=\sum _{n\geq 0}f_{n}X^{n}

{\ displaystyle f = \ sum _ {n \ geq 0} f_ {n} X ^ {n}}

{\ displaystyle f = \ sum _ {n \ geq 0} f_ {n} X ^ {n}}

pentru această succesiune. Funcția generatoare pentru secvența ( f _{n −1} ) este Xf și cea a ( f _{n −2} ) este X ² f . Din relația de recurență rezultă că seria de putere Xf + X ² f are aceiași coeficienți ca f cu excepția primelor două. Ținând cont de acestea, constatăm că

f=Xf+X^{2}f+X.

{\ displaystyle f = Xf + X ^ {2} f + X.}

{\ displaystyle f = Xf + X ^ {2} f + X.}

Acesta este pasul crucial; Relațiile de recurență pot fi aproape întotdeauna traduse în ecuații pentru generarea funcțiilor. Rezolvând această ecuație pentru f obținem

f={\frac {X}{1-X-X^{2}}}.

{\ displaystyle f = {\ frac {X} {1-XX ^ {2}}}.}

{\ displaystyle f = {\ frac {X} {1-X-X ^ {2}}}.}

Numitorul poate fi luat în considerare folosind secțiunea de aur φ ₁ = (1 + √5) / 2 și φ ₂ = (1 - √5) / 2; tehnica descompunerii în fracții parțiale duce la

f={\frac {1/{\sqrt {5}}}{1-\phi _{1}X}}-{\frac {1/{\sqrt {5}}}{1-\phi _{2}X}}.

{\ displaystyle f = {\ frac {1 / {\ sqrt {5}}} {1- \ phi _ {1} X}} - {\ frac {1 / {\ sqrt {5}}} {1- \ phi _ {2} X}}.}

{\ displaystyle f = {\ frac {1 / {\ sqrt {5}}} {1- \ phi _ {1} X}} - {\ frac {1 / {\ sqrt {5}}} {1- \ phi _ {2} X}}.}

Cei doi termeni din dreapta sunt suma a două serii geometrice ; comparând coeficienții termenilor de grad egal găsim formula explicită

f_{n}={\frac {1}{\sqrt {5}}}(\phi _{1}^{n}-\phi _{2}^{n}).

{\ displaystyle f_ {n} = {\ frac {1} {\ sqrt {5}}} (\ phi _ {1} ^ {n} - \ phi _ {2} ^ {n}).}

{\ displaystyle f_ {n} = {\ frac {1} {\ sqrt {5}}} (\ phi _ {1} ^ {n} - \ phi _ {2} ^ {n}).}

Aplicații

Funcțiile generatorului sunt utilizate pentru diverse procese.

Găsirea relațiilor de recurență pentru componentele secvențelor: Forma unei funcții generatoare poate sugera o formulă de recurență.
Găsirea relațiilor între secvențe: dacă funcțiile de generare a două secvențe au forme similare, probabil aceleași secvențe se află într-o relație semnificativă.
Explorează comportamentul asimptotic al secvențelor.
Demonstrați identități legate de moșteniri.
Rezolvarea problemelor de enumerare combinatorie .
Evaluează valorile la care converg seriile date.

Bibliografie

Herbert S. Wilf (1994): funcționarea generatoare (Ediția a doua). Academic Press. ISBN 0127519564 . Pentru o versiune descărcabilă gratuit oferită de Herbert Wilf și Academic Press, consultați pagina Descărcați cartea Generatingfunctionology .

Elemente conexe

linkuri externe

Generarea de funcții, indicii de putere și schimbarea monedei , la cut-the-knot.org .
Generatingfunctionology (PDF) ( PDF ), pe math.upenn.edu .

Controlul autorității	Tesauro BNCF 70287 · LCCN (EN) sh85053815 · GND (DE) 4152979-0 · BNF (FR) cb12259609r (data)

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

V · D · M Combinatorial
Orientare generală	Combinatorică · Istoria combinatoriei · Matematică discretă · Secțiunea 05-XX din MSC
Noțiuni introductive	Permutații · Dispoziții · Combinații · Coeficienți binomiali · Partiții de numere întregi · Partiții de mulțimi finite - Identități și bijecții combinatorii
Configurări	Pătrat latin · pătrate magice · Desene Block · geometrii finite · Matroids - mozaicare · Polimini
Teoria graficelor	Copaci · Mers pe grafice ( Eulerian , Hamiltonian ) · Conexiune în grafice - grafice plane · Vopsirea graficelor și teorema celor patru culori ) · hipergrafe · Grafice și grupuri · digraf · Grafic al fluxului de numerar · Plimbări aleatorii pe grafice · omomorfismul graficelor · Algoritmi pe grafice
Combinatorie algebrică	Tabelul lui Young · funcții simetrice - serie de puteri formale · Funcții de generare · Polinoame ortogonale · Părți ale unui grup de structuri combinatorii - Aspecte algebră comutativă combinatorie
Alte domenii	Calculul umbrelor ( secvențe polinomiale de tip binomial · secvențe Sheffer ) - Combinatorial extremal