Genereringsfunktion - Generating function

I matematik är en genererande funktion ett sätt att koda en oändlig sekvens av tal ( a _n ) genom att behandla dem som koefficienterna för en formell kraftserie . Denna serie kallas sekvensens genereringsfunktion. Till skillnad från en vanlig serie krävs inte att den formella kraftserien konvergerar : i själva verket betraktas inte den genererande funktionen som en funktion , och "variabeln" förblir en obestämd . Genereringsfunktioner introducerades först av Abraham de Moivre 1730 för att lösa det allmänna linjära återkommande problemet. Man kan generalisera till formella maktserier i mer än en obestämd, för att koda information om oändliga flerdimensionella matriser.

Det finns olika typer av genereringsfunktioner, inklusive vanliga genereringsfunktioner , exponentiella genereringsfunktioner , Lambert -serier , Bell -serier och Dirichlet -serier ; definitioner och exempel ges nedan. Varje sekvens har i princip en genereringsfunktion av varje typ (förutom att Lambert- och Dirichlet -serien kräver att index börjar med 1 snarare än 0), men hur lätt de kan hanteras kan skilja sig avsevärt. Den speciella genereringsfunktion, om någon, som är mest användbar i ett givet sammanhang beror på sekvensens art och detaljerna i problemet som tas upp.

Genereringsfunktioner uttrycks ofta i sluten form (snarare än som en serie), genom något uttryck som involverar operationer definierade för formella serier. Dessa uttryck i termer av det obestämda  x kan innefatta aritmetiska operationer, differentiering med avseende på  x och sammansättning med (dvs substitution i) andra genererande funktioner; eftersom dessa operationer också definieras för funktioner, ser resultatet ut som en funktion av  x . Faktum är att det slutna formuttrycket ofta kan tolkas som en funktion som kan utvärderas till (tillräckligt små) konkreta värden på x , och som har den formella serien som serieutvidgning ; detta förklarar beteckningen "genererande funktioner". En sådan tolkning krävs dock inte för att vara möjlig, eftersom formella serier inte krävs för att ge en konvergent serie när ett numeriskt värde utan noll ersätts med  x . Inte alla uttryck som är meningsfulla som funktioner för  x är meningsfulla som uttryck som betecknar formella serier; Exempelvis är negativa och fraktionerade effekter av  x exempel på funktioner som inte har en motsvarande formell effektserie.

Generering av funktioner är inte funktioner i formell mening av en kartläggning från en domän till en kodomän . Genereringsfunktioner kallas ibland för att generera serier , genom att en rad termer kan sägas vara generator för dess sekvens av termkoefficienter.

Definitioner

En genererande funktion är en anordning som liknar en väska. Istället för att bära många små föremål avskilt, vilket kan vara pinsamt, lägger vi dem alla i en påse, och sedan har vi bara ett föremål att bära, påsen.

- George Pólya , Matematik och rimligt resonemang (1954)

En genererande funktion är en klädstreck där vi lägger på en sekvens av nummer för visning.

- Herbert Wilf , Generatingfunctionalology (1994)

Vanlig genereringsfunktion (OGF)

Den vanliga genereringsfunktionen för en sekvens a _n är

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

När termen genereringsfunktion används utan kvalifikation, brukar det förstås som en vanlig genereringsfunktion.

Om a _n är sannolikhetsmassafunktionen för en diskret slumpmässig variabel , kallas dess vanliga genereringsfunktion för en sannolikhetsgenererande funktion .

Den vanliga genereringsfunktionen kan generaliseras till matriser med flera index. Till exempel är den vanliga genereringsfunktionen för en tvådimensionell array a _{m, n} (där n och m är naturliga tal)

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

Exponential generating function (EGF)

Den exponentiella alstringsfunktionen för en sekvens a _n är

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

Exponentiella genereringsfunktioner är i allmänhet mer praktiska än vanliga genereringsfunktioner för kombinatoriska uppräkningsproblem som involverar märkta objekt.

Poisson -genererande funktion

Den Poisson genererande funktionen av en sekvens en _n är

${\ displaystyle \ operatorname {PG} (a_ {n}; x) = \ sum _ {n = 0}^{\ infty} a_ {n} e^{-x} {\ frac {x^{n}} {n!}} = e^{-x} \, \ operatorname {EG} (a_ {n}; x).}$

Lambert -serien

Den Lambert serie av en sekvens en _n är

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

Lambert -seriens koefficienter i kraftserieutvidgningarna för heltal är relaterade med divisorsumman . Huvudartikeln ger flera fler klassiska eller åtminstone välkända exempel relaterade till speciella aritmetiska funktioner inom talteori . I en Lambert -serie börjar index n vid 1, inte vid 0, eftersom den första termen annars skulle vara odefinierad. ${\ displaystyle b_ {n}: = [x^{n}] \ operatorname {LG} (a_ {n}; x)}$${\ displaystyle n \ geq 1}$ ${\ textstil b_ {n} = \ sum _ {d | n} a_ {d}}$

Bell -serien

Den Bell serie av en sekvens en _n är ett uttryck i termer av både obestämd x och ett mycket attraktivt p och ges av

${\ displaystyle \ operatorname {BG} _ {p} (a_ {n}; x) = \ sum _ {n = 0}^{\ infty} a_ {p^{n}} x^{n}.}$

Dirichlet -seriens genereringsfunktioner (DGF)

Formella Dirichlet -serier klassificeras ofta som genererande funktioner, även om de inte är strikt formella kraftserier. Den dirichletserie genererande funktionen av en sekvens en _n är

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

Serien genererande funktionen Dirichlet är särskilt användbart när en _n är en multiplikativ funktion , i vilket fall den har en Euler produkt uttryck i termer av funktionens Bell serie

${\ displaystyle \ operatorname {DG} (a_ {n}; s) = \ prod _ {p} \ operatorname {BG} _ {p} (a_ {n}; p^{-s}) \ ,.}$

Om en _n är en Dirichlet karaktär då dess serie genereringsfunktion Dirichlet kallas en Dirichlet L-serien . Vi har också ett samband mellan paret av koefficienter i Lambert -seriens expansioner ovan och deras DGF. Vi kan nämligen bevisa att om och bara om var är Riemann zeta -funktionen . ${\ displaystyle [x^{n}] \ operatorname {LG} (a_ {n}; x) = b_ {n}}$${\ displaystyle \ operatorname {DG} (a_ {n}; s) \ zeta (s) = \ operatorname {DG} (b_ {n}; s)}$${\ displaystyle \ zeta (s)}$

Polynomiska sekvensgenererande funktioner

Idén med att generera funktioner kan utökas till sekvenser av andra objekt. Således genereras till exempel polynomiska sekvenser av binomial typ av

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

där p _n ( x ) är en sekvens av polynom och f ( t ) är en funktion av en viss form. Sheffer -sekvenser genereras på ett liknande sätt. Se huvudartikeln generaliserade Appell -polynom för mer information.

Vanliga genereringsfunktioner

Exempel på generering av funktioner för enkla sekvenser

Polynom är ett speciellt fall av vanliga genereringsfunktioner, motsvarande ändliga sekvenser, eller motsvarande sekvenser som försvinner efter en viss punkt. Dessa är viktiga eftersom många ändliga sekvenser användbart kan tolkas som genererande funktioner, såsom Poincaré -polynomet och andra.

En grundläggande genereringsfunktion är den för den konstanta sekvensen 1, 1, 1, 1, 1, 1, 1, 1, 1, ..., vars vanliga genereringsfunktion är den geometriska serien

${\ displaystyle \ sum _ {n = 0}^{\ infty} x^{n} = {\ frac {1} {1-x}}.}$

Den vänstra sidan är expansionen av Maclaurin-serien på höger sida. Alternativt kan jämlikheten motiveras genom att multiplicera effektserien till vänster med 1 -  x och kontrollera att resultatet är den konstanta effektserien 1 (med andra ord att alla koefficienter utom den på x ⁰ är lika med 0) . Dessutom kan det inte finnas några andra kraftserier med den här egenskapen. Vänster sida betecknar därför multiplikativ invers av 1-  x i ringen av kraftserier.

Uttryck för den vanliga genereringsfunktionen för andra sekvenser härrör lätt från denna. Till exempel ger substitutionen x  →  ax genereringsfunktionen för den geometriska sekvensen 1, a , a ² , a ³ , ... för en konstant a :

${\ displaystyle \ sum _ {n = 0}^{\ infty} (ax)^{n} = {\ frac {1} {1-ax}}.}$

(Jämlikheten följer också direkt av det faktum att den vänstra sidan är Maclaurin-serien på höger sida.) I synnerhet

${\ displaystyle \ sum _ {n = 0}^{\ infty} (-1)^{n} x^{n} = {\ frac {1} {1+x}}.}$

Man kan också införa regelbundna "luckor" i sekvensen genom att ersätta x med någon effekt av x , så till exempel för sekvensen 1, 0, 1, 0, 1, 0, 1, 0, ... (som hoppar över x , x ³ , x ⁵ , ...) får man genereringsfunktionen

${\ displaystyle \ sum _ {n = 0}^{\ infty} x^{2n} = {\ frac {1} {1-x^{2}}}.}$

Genom att kvadrera den initiala genereringsfunktionen, eller genom att hitta derivatan från båda sidor med avseende på x och göra en ändring av körvariabeln n  →  n  + 1, ser man att koefficienterna bildar sekvensen 1, 2, 3, 4, 5, ..., så har man

${\ displaystyle \ sum _ {n = 0}^{\ infty} (n+1) x^{n} = {\ frac {1} {(1-x)^{2}}},}$

och den tredje kraften har som koefficienter triangulära siffror 1, 3, 6, 10, 15, 21, ... vars term n är binomialkoefficienten , så att ${\ displaystyle {\ tbinom {n+2} {2}}}$

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

Mer allmänt, för alla icke-negativa heltal k och icke-noll verkligt värde a , är det sant att

${\ displaystyle \ sum _ {n = 0}^{\ infty} a^{n} {\ binom {n+k} {k}} x^{n} = {\ frac {1} {(1-axel )^{k+1}}} \ ,.}$

Eftersom

${\ displaystyle 2 {\ binom {n+2} {2}}-3 {\ binom {n+1} {1}}+{\ binom {n} {0}} = 2 {\ frac {(n+ 1) (n+2)} {2}}-3 (n+1)+1 = n^{2},}$

man kan hitta den vanliga genereringsfunktionen för sekvensen 0, 1, 4, 9, 16, ... av kvadrattal genom linjär kombination av binomial-koefficientgenererande sekvenser:

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

Vi kan också växla växelvis för att generera samma kvadratsekvens som en summa av derivat av den geometriska serien i följande form:

${\ displaystyle {\ begin {align} G (n^{2}; x) & = \ sum _ {n = 0}^{\ infty} n^{2} x^{n} = \ sum _ {n = 0}^{\ infty} n (n-1) x^{n}+\ sum _ {n = 0}^{\ infty} nx^{n} \\ & = x^{2} D^{ 2} \ vänster [{\ frac {1} {1-x}} \ höger]+xD \ vänster [{\ frac {1} {1-x}} \ höger] \\ & = {\ frac {2x^ {2}} {(1-x)^{3}}}+{\ frac {x} {(1-x)^{2}}} = {\ frac {x (x+1)} {(1 -x)^{3}}}. \ end {align}}}$

Genom induktion kan vi på liknande sätt visa för positiva heltal det ${\ displaystyle m \ geq 1}$

${\ displaystyle n^{m} = \ sum _ {j = 0}^{m} \ left \ {{\ begin {matrix} m \\ j \ end {matrix}} \ right \} {\ frac {n !} {(nj)!}},}$

där beteckna Stirling -siffrorna av det andra slaget och där genereringsfunktionen , så att vi kan bilda de analoga genereringsfunktionerna över de integrala -th -krafterna som generaliserar resultatet i kvadratfallet ovan. I synnerhet eftersom vi kan skriva kan vi tillämpa en välkänd ändlig summaidentitet som involverar Stirling-siffrorna för att få det ${\ displaystyle \ left \ {{\ begin {matrix} n \\ k \ end {matrix}} \ right \}}$${\ textstil \ sum _ {n \ geq 0} n!/(nj)! \, z^{n} = j! \ cdot z^{j}/(1-z)^{j+1}}$${\ displaystyle m}$${\ displaystyle {\ frac {z^{k}} {(1-z)^{k+1}}} = \ sum _ {i = 0}^{k} {\ binom {k} {i}} {\ frac {(-1)^{ki}} {(1-z)^{i+1}}}}$

${\ displaystyle \ sum _ {n \ geq 0} n^{m} z^{n} = \ sum _ {j = 0}^{m} \ left \ {{\ begin {matrix} m+1 \\ j+1 \ end {matris}} \ höger \} {\ frac {(-1)^{mj} j!} {(1-z)^{j+1}}}.}$

Rationella funktioner

Den vanliga genereringsfunktionen för en sekvens kan uttryckas som en rationell funktion (förhållandet mellan två ändliga polynom) om och endast om sekvensen är en linjär rekursiv sekvens med konstanta koefficienter; detta generaliserar exemplen ovan. Omvänt uppfyller varje sekvens som genereras av en bråkdel av polynom ett linjärt återfall med konstanta koefficienter; dessa koefficienter är identiska med koefficienterna för fraktionsnämnaren polynom (så att de kan avläsas direkt). Denna observation visar att det är lätt att lösa för att generera funktioner för sekvenser definierade av en linjär ändlig skillnadsekvation med konstanta koefficienter, och därav för uttryckliga slutna formler för koefficienterna för dessa genererande funktioner. Det prototypiska exemplet här är att härleda Binets formel för Fibonacci -talen via generering av funktionstekniker.

Vi märker också att klassen av rationella genereringsfunktioner exakt motsvarar de genereringsfunktioner som räknar upp kvasi-polynomiska sekvenser av formen

${\ displaystyle f_ {n} = p_ {1} (n) \ rho _ {1}^{n} +\ cdots +p _ {\ ell} (n) \ rho _ {\ ell}^{n},}$

där de ömsesidiga rötterna ,, är fasta skaler och var finns ett polynom för alla . ${\ displaystyle \ rho _ {i} \ in \ mathbb {C}}$${\ displaystyle p_ {i} (n)}$${\ displaystyle n}$${\ displaystyle 1 \ leq i \ leq \ ell}$

I allmänhet producerar Hadamards produkter av rationella funktioner rationella genererande funktioner. På samma sätt om är ett bivariat rationell genererande funktion, då dess motsvarande diagonal genererande funktionen , är algebraisk . Till exempel om vi låter ${\ textstil F (s, t): = \ sum _ {m, n \ geq 0} f (m, n) w^{m} z^{n}}$${\ textstil \ operatornamn {diag} (F): = \ sum _ {n \ geq 0} f (n, n) z^{n}}$

${\ displaystyle F (s, t): = \ sum _ {i, j \ geq 0} {\ binom {i+j} {i}} s^{i} t^{j} = {\ frac {1 } {1-st}},}$

då ges denna genereringsfunktions diagonal koefficientgenererande funktion med den välkända OGF-formeln

${\ displaystyle \ operatorname {diag} (F) = \ sum _ {n \ geq 0} {\ binom {2n} {n}} z^{n} = {\ frac {1} {\ sqrt {1-4z }}}.}$

Detta resultat beräknas på många sätt, inklusive Cauchys integrala formel eller konturintegration , tar komplexa rester eller genom direkta manipulationer av formella kraftserier i två variabler.

Funktioner för att generera funktioner

Multiplikation ger konvolution

Multiplikation av vanliga genereringsfunktioner ger en diskret konvolution ( Cauchy -produkten ) av sekvenserna. Till exempel sekvensen av kumulativa summor (jämför med den lite mer allmänna Euler – Maclaurin -formeln )

${\ displaystyle (a_ {0}, a_ {0}+a_ {1}, a_ {0}+a_ {1}+a_ {2}, \ ldots)}$

av en sekvens med vanlig genereringsfunktion G ( a _n ;  x ) har genereringsfunktionen

${\ displaystyle G (a_ {n}; x) \ cdot {\ frac {1} {1-x}}}$

eftersom 1/(1 -  x ) är den vanliga genereringsfunktionen för sekvensen (1, 1, ...). Se även avsnittet om konvolutions i applikationsavsnittet i den här artikeln nedan för ytterligare exempel på problemlösning med omvandlingar av genererande funktioner och tolkningar.

Skiftande sekvensindex

För heltal , har vi följande två analoga identiteter för de modifierade genererande funktioner räkna upp den skiftade sekvensvarianter av och , respektive: ${\ displaystyle m \ geq 1}$${\ displaystyle \ langle g_ {nm} \ rangle}$${\ displaystyle \ langle g_ {n+m} \ rangle}$

${\ displaystyle {\ begin {align} z^{m} G (z) & = \ sum _ {n \ geq m} g_ {nm} z^{n} \\ {\ frac {G (z) -g_ {0} -g_ {1} z- \ cdots -g_ {m-1} z^{m-1}} {z^{m}}} & = \ sum _ {n \ geq 0} g_ {n+ m} z^{n}. \ end {align}}}$

Differentiering och integration av genererande funktioner

Vi har följande respektive kraftserieutvidgningar för det första derivatet av en genererande funktion och dess integral:

${\ displaystyle {\ begin {align} G^{\ prime} (z) & = \ sum _ {n \ geq 0} (n+1) g_ {n+1} z^{n} \\ z \ cdot G^{\ prime} (z) & = \ sum _ {n \ geq 0} ng_ {n} z^{n} \\\ int _ {0}^{z} G (t) \, dt & = \ summa _ {n \ geq 1} {\ frac {g_ {n-1}} {n}} z^{n}. \ end {align}}}$

Differentierings -multiplikationsoperationen för den andra identiteten kan upprepas gånger för att multiplicera sekvensen med , men det kräver växling mellan differentiering och multiplikation. Om istället göra differentieringar i följd, är effekten att multiplicera med ^e fallande faktoriell : ${\ displaystyle k}$${\ displaystyle n^{k}}$${\ displaystyle k}$${\ displaystyle k}$

${\ displaystyle z^{k} G^{(k)} (z) = \ sum _ {n \ geq 0} n^{\ understrykning {k}} g_ {n} z^{n} = \ sum _ {n \ geq 0} n (n-1) \ dotsb (n-k+1) g_ {n} z^{n} {\ text {för alla}} k \ i \ mathbb {N}.}$

Med hjälp av Stirling -nummer av det andra slaget kan det förvandlas till en annan formel för att multiplicera med följande (se huvudartikeln om generering av funktionstransformationer ): ${\ displaystyle n^{k}}$

${\ displaystyle \ sum _ {j = 0}^{k} \ left \ {{\ begin {matrix} k \\ j \ end {matrix}} \ right \} z^{j} F^{(j) } (z) = \ sum _ {n \ geq 0} n^{k} f_ {n} z^{n} {\ text {för alla}} k \ i \ mathbb {N}.}$

En negativ ordningsomvändning av denna sekvensmaktformel som motsvarar driften av upprepad integration definieras av zeta-serietransformationen och dess generaliseringar definierade som en derivatbaserad transformation av genererande funktioner , eller alternativt termiskt genom att utföra en integrerad transformation på sekvensen genererande funktion. Relaterade operationer för att utföra fraktionerad integration på en sekvensgenererande funktion diskuteras här .

Räkna upp aritmetiska progresser av sekvenser

I detta avsnitt ger vi formler för genererande funktioner räkna upp den sekvens som ges en vanlig genererande funktionen där , och (se huvudartikeln på transformationer ). För detta är helt enkelt den välbekanta sönderdelningen av en funktion i jämna och udda delar (dvs jämna och udda krafter): ${\ displaystyle \ {f_ {an+b} \}}$${\ displaystyle F (z)}$${\ displaystyle a, b \ in \ mathbb {N}}$${\ displaystyle a \ geq 2}$${\ displaystyle 0 \ leq b <a}$${\ displaystyle a = 2}$

${\ displaystyle \ sum _ {n \ geq 0} f_ {2n} z^{2n} = {\ frac {1} {2}} \ vänster (F (z)+F (-z) \ höger)}$

${\ displaystyle \ sum _ {n \ geq 0} f_ {2n+1} z^{2n+1} = {\ frac {1} {2}} \ left (F (z) -F (-z) \ höger).}$

Mer allmänt antar att och det betecknar ^e primitiva Enhetsrot . Sedan, som en tillämpning av den diskreta Fouriertransformen , har vi formeln ${\ displaystyle a \ geq 3}$${\ displaystyle \ omega _ {a} = \ exp \ left (2 \ pi \ imath /a \ right)}$${\ displaystyle a}$

${\ displaystyle \ sum _ {n \ geq 0} f_ {an+b} z^{an+b} = {\ frac {1} {a}} \ sum _ {m = 0}^{a-1} \ omega _ {a}^{-mb} F \ vänster (\ omega _ {a}^{m} z \ höger).}$

För heltal genereras en annan användbar formel som ger något omvända golvade aritmetiska framsteg - som effektivt upprepar varje koefficienttid - av identiteten ${\ displaystyle m \ geq 1}$${\ displaystyle m}$

${\ displaystyle \ sum _ {n \ geq 0} f _ {\ left \ lfloor {\ frac {n} {m}} \ right \ rfloor} z^{n} = {\ frac {1-z^{m} } {1-z}} F (z^{m}) = \ vänster (1+z+\ cdots+z^{m-2}+z^{m-1} \ höger) F (z^{m} ).}$

P-rekursiva sekvenser och holonomiska genererande funktioner

Definitioner

En formell kraftserie (eller funktion) sägs vara holonomisk om den uppfyller en linjär differentialekvation av formen ${\ displaystyle F (z)}$

${\ displaystyle c_ {0} (z) F^{(r)} (z)+c_ {1} (z) F^{(r-1)} (z)+\ cdots+c_ {r} (z ) F (z) = 0,}$

där koefficienterna är inom området för rationella funktioner, . På motsvarande sätt är det holonomiskt om vektorutrymmet som omfattas av uppsättningen för alla dess derivat är ändligt dimensionellt. ${\ displaystyle c_ {i} (z)}$${\ displaystyle \ mathbb {C} (z)}$${\ displaystyle F (z)}$${\ displaystyle \ mathbb {C} (z)}$

Eftersom vi kan rensa nämnare om det behövs i den tidigare ekvationen kan vi anta att funktionerna är polynom i . Således kan vi se ett ekvivalent villkor att en genererande funktion är holonomisk om dess koefficienter uppfyller en P-återfall av formen ${\ displaystyle c_ {i} (z)}$${\ displaystyle z}$

${\ displaystyle {\ widehat {c}} _ {s} (n) f_ {n+s}+{\ widehat {c}} _ {s-1} (n) f_ {n+s-1}+\ cdots +{\ widehat {c}} _ {0} (n) f_ {n} = 0,}$

för alla tillräckligt stora och där de är fasta ändliga polynom i . Med andra ord är egenskaperna att en sekvens är P-rekursiv och har en holonomisk genererande funktion ekvivalenta. Holonomiska funktioner stängs under Hadamards produktoperation för generering av funktioner. ${\ displaystyle n \ geq n_ {0}}$${\ displaystyle {\ widehat {c}} _ {i} (n)}$${\ displaystyle n}$${\ displaystyle \ odot}$

Exempel

Funktionerna , , , , , den dilogarithm funktion , de generaliserade hypergeometriska funktionen och funktionerna som definieras av potensserie och den icke-konvergent är alla holonomic. Exempel på P-rekursiva sekvenser med holonomic genererande funktioner inkluderar och , där sekvenser såsom och är inte P-rekursiv på grund av arten av singulariteter i deras motsvarande genererande funktioner. På liknande sätt, funktioner med oändligt-många singulariteter såsom , och är inte holonomic funktioner. ${\ displaystyle e^{z}}$${\ displaystyle \ log (z)}$${\ displaystyle \ cos (z)}$${\ displaystyle \ arcsin (z)}$${\ displaystyle {\ sqrt {1+z}}}$${\ displaystyle \ operatorname {Li} _ {2} (z)}$ ${\ displaystyle _ {p} F_ {q} (...; ...; z)}$${\ textstil \ sum _ {n \ geq 0} z^{n}/(n!)^{2}}$${\ textstil \ sum _ {n \ geq 0} n! \ cdot z^{n}}$${\ textstil f_ {n}: = {\ frac {1} {n+1}} {\ binom {2n} {n}}}$${\ displaystyle f_ {n}: = 2^{n}/(n^{2} +1)}$${\ displaystyle {\ sqrt {n}}}$${\ displaystyle \ log (n)}$${\ displaystyle \ tan (z)}$${\ displaystyle \ sec (z)}$${\ displaystyle \ Gamma (z)}$

Programvara för att arbeta med P-rekursiva sekvenser och holonomiska genereringsfunktioner

Verktyg för bearbetning och arbete med P-rekursiva sekvenser i Mathematica inkluderar mjukvarupaket som tillhandahålls för icke-kommersiell användning på RISC Combinatorics Groups algoritmiska kombinatoriska mjukvarusida . Trots att de mestadels är slutna källor tillhandahålls särskilt kraftfulla verktyg i denna mjukvarupaket av Guess- paketet för att gissa P-återkommande för godtyckliga ingångssekvenser (användbart för experimentell matematik och utforskning) och Sigma- paketet som kan hitta P-återfall för många summor och lösa för slutna lösningar på P-återfall med generaliserade harmoniska tal . Andra paket som listas på denna specifika RISC -webbplats är inriktade på att arbeta med holonomiska genereringsfunktioner specifikt. ( Beroende på hur ingående denna artikel kommer på ämnet finns det många, många andra exempel på användbara programverktyg som kan listas här eller på den här sidan i ett annat avsnitt. )

Förhållande till Fouriertransform i diskret tid

När serien konvergerar absolut ,

${\ displaystyle G \ left (a_ {n}; e^{-i \ omega} \ right) = \ sum _ {n = 0}^{\ infty} a_ {n} e^{-i \ omega n} }$

är den diskreta Fourier-transformen av sekvensen a ₀ ,  a ₁ ,….

Asymptotisk tillväxt av en sekvens

I kalkyl kan ofta tillväxttakten för koefficienterna i en effektserie användas för att härleda en konvergensradie för effektserierna. Det omvända kan också hålla; ofta kan konvergensradien för en genererande funktion användas för att härleda den asymptotiska tillväxten av den underliggande sekvensen.

Till exempel om en vanlig genereringsfunktion G ( a _n ;  x ) som har en begränsad radie av konvergens av r kan skrivas som

${\ displaystyle G (a_ {n}; x) = {\ frac {A (x)+B (x) \ vänster (1-{\ frac {x} {r}} \ höger)^{-\ beta} } {x^{\ alpha}}}}$

där var och en av A ( x ) och B ( x ) är en funktion som är analytisk till en konvergensradie större än r (eller är hel ), och där B ( r ) ≠ 0 då

${\ displaystyle a_ {n} \ sim {\ frac {B (r)} {r^{\ alpha} \ Gamma (\ beta)}} \, n^{\ beta -1} (1/r)^{ n} \ sim {\ frac {B (r)} {r^{\ alpha}}} {\ binom {n+\ beta -1} {n}} (1/r)^{n} = {\ frac { B (r)} {r^{\ alpha}}} \ vänster (\! \! {\ Binom {\ beta} {n}} \! \! \ Höger) (1/r)^{n} \, ,}$

med Gamma -funktionen , en binomial koefficient eller en multiset koefficient .

Ofta kan denna metod itereras för att generera flera termer i en asymptotisk serie för en _n . Särskilt,

${\ displaystyle G \ left (a_ {n} -{\ frac {B (r)} {r^{\ alpha}}} {\ binom {n+\ beta -1} {n}} (1/r)^ {n}; x \ höger) = G (a_ {n}; x)-{\ frac {B (r)} {r^{\ alpha}}} \ vänster (1-{\ frac {x} {r }} \ höger)^{-\ beta} \ ,.}$

Den asymptotiska tillväxten av koefficienterna för denna genereringsfunktion kan sedan sökas via fyndet av A , B , a , ß och r för att beskriva den genererande funktionen, såsom ovan.

Liknande asymptotisk analys är möjlig för exponentiella genererande funktioner. Med en exponentiell genererande funktion är det en _n / n ! som växer enligt dessa asymptotiska formler.

Asymptotisk tillväxt av kvadratsekvensen

Som härledd ovan är den vanliga genereringsfunktionen för kvadratsekvensen

${\ displaystyle {\ frac {x (x+1)} {(1-x)^{3}}}.}$

Med r  = 1, α = −1, β = 3, A ( x ) = 0 och B ( x ) =  x +1 kan vi verifiera att rutorna växer som förväntat, som rutorna:

${\ displaystyle a_ {n} \ sim {\ frac {B (r)} {r^{\ alpha} \ Gamma (\ beta)}} \, n^{\ beta -1} \ left ({\ frac { 1} {r}} \ höger)^{n} = {\ frac {1+1} {1^{-1} \, \ Gamma (3)}} \, n^{3-1} (1/ 1)^{n} = n^{2}.}$

Asymptotisk tillväxt av de katalanska talen

Den vanliga genereringsfunktionen för de katalanska talen är

${\ displaystyle {\ frac {1-{\ sqrt {1-4x}}} {2x}}.}$

Med r  = 1/4, α = 1, β = −1/2, A ( x ) = 1/2 och B ( x ) = −1/2 kan vi dra slutsatsen att för de katalanska talen,

${\ displaystyle a_ {n} \ sim {\ frac {B (r)} {r^{\ alpha} \ Gamma (\ beta)}} \, n^{\ beta -1} \ left ({\ frac { 1} {r}} \ höger)^{n} = {\ frac {-{\ frac {1} {2}}} {({\ frac {1} {4}})^{1} \ Gamma ( -{\ frac {1} {2}})}} \, n^{-{\ frac {1} {2}}-1} \ vänster ({\ frac {1} {\ frac {1} {4 }}} \ höger)^{n} = {\ frac {1} {\ sqrt {\ pi}}} n^{-{\ frac {3} {2}}} \, 4^{n}.}$

Bivariata och multivariata genererande funktioner

Man kan definiera genereringsfunktioner i flera variabler för matriser med flera index. Dessa kallas multivariata genereringsfunktioner eller ibland supergenererande funktioner . För två variabler kallas dessa ofta bivariata genererande funktioner .

Eftersom till exempel den vanliga genereringsfunktionen för binomialkoefficienter för ett fast n är , kan man begära en bivariat genererande funktion som genererar binomialkoefficienterna för alla k och n . För att göra detta, betrakta som en sekvens i n , och hitta den genererande funktionen i y som har dessa sekvensvärden som koefficienter. Eftersom genereringsfunktionen för is ${\ displaystyle (1+x)^{n}}$${\ textstil {\ binom {n} {k}}}$${\ displaystyle (1+x)^{n}}$${\ displaystyle a^{n}}$

${\ displaystyle {\ frac {1} {1-ay}},}$

genereringsfunktionen för binomialkoefficienterna är:

${\ displaystyle \ sum _ {n, k} {\ binom {n} {k}} x^{k} y^{n} = {\ frac {1} {1- (1+x) y}} = {\ frac {1} {1-å-xy}}.}$

Representation med fortsatta fraktioner (J-fraktioner av Jacobi-typ)

Definitioner

Utvidgningar av (formella) Jacobi-typ och Stieltjes-typ fortsatta fraktioner ( J-fraktioner respektive S-fraktioner ) vars rationella konvergenter representerar -order noggranna kraftserier är ett annat sätt att uttrycka de typiskt divergerande vanliga genereringsfunktionerna för många speciella och tvåvariata sekvenser. Den speciella formen av Jacobi-typen fortsatta fraktioner (J-fraktioner) expanderas som i följande ekvation och har nästa motsvarande effektserieutvidgningar med avseende på vissa specifika, applikationsberoende komponentsekvenser, och , där betecknar den formella variabeln i den andra kraftserieutvidgningen nedan: ${\ displaystyle h^{th}}$${\ displaystyle 2h}$${\ displaystyle z}$${\ displaystyle \ {{\ text {ab}} _ {i} \}}$${\ displaystyle \ {c_ {i} \}}$${\ displaystyle z \ neq 0}$

${\ displaystyle {\ begin {align} J^{[\ infty]} (z) & = {\ cfrac {1} {1-c_ {1} z-{\ cfrac {{\ text {ab}} _ { 2} z^{2}} {1-c_ {2} z-{\ cfrac {{\ text {ab}} _ {3} z^{2}} {\ ddots}}}}}} \\ & = 1+c_ {1} z+\ vänster ({\ text {ab}} _ {2}+c_ {1}^{2} \ höger) z^{2}+\ vänster (2 {\ text {ab} } _ {2} c_ {1}+c_ {1}^{3}+{\ text {ab}} _ {2} c_ {2} \ höger) z^{3}+\ cdots. \ End {justerat }}}$

Koefficienterna för , betecknade i stenografi med , i de tidigare ekvationerna motsvarar matrislösningar för ekvationerna ${\ displaystyle z^{n}}$${\ displaystyle j_ {n}: = [z^{n}] J^{[\ infty]} (z)}$

${\ displaystyle {\ begin {bmatrix} k_ {0,1} & k_ {1,1} & 0 & 0 & \ cdots \\ k_ {0,2} & k_ {1,2} & k_ {2,2} & 0 & \ cdots \\ k_ {0,3} & k_ {1,3} & k_ {2,3} & k_ {3,3} & \ cdots \\\ vdots & \ vdots & \ vdots & \ vdots \ end {bmatrix}} = {\ begin { bmatrix} k_ {0,0} & 0 & 0 & 0 & \ cdots \\ k_ {0,1} & k_ {1,1} & 0 & 0 & \ cdots \\ k_ {0,2} & k_ {1,2} & k_ {2,2} & 0 & \ cdots \\\ vdots & \ vdots & \ vdots & \ vdots \ end {bmatrix}} \ cdot {\ begin {bmatrix} c_ {1} & 1 & 0 & 0 & \ cdots \\ {\ text {ab}} _ {2} & c_ { 2} & 1 & 0 & \ cdots \\ 0 & {\ text {ab}} _ {3} & c_ {3} & 1 & \ cdots \\\ vdots & \ vdots & \ vdots & \ vdots \ end {bmatrix}},}$

där , för , om och var för alla heltal , har vi en additionsformelrelation som ges av ${\ displaystyle j_ {0} \ equiv k_ {0,0} = 1}$${\ displaystyle j_ {n} = k_ {0, n}}$${\ displaystyle n \ geq 1}$${\ displaystyle k_ {r, s} = 0}$${\ displaystyle r> s}$${\ displaystyle p, q \ geq 0}$

${\ displaystyle j_ {p+q} = k_ {0, p} \ cdot k_ {0, q}+\ sum _ {i = 1}^{\ min (p, q)} {\ text {ab}} _ {2} \ cdots {\ text {ab}} _ {i+1} \ gånger k_ {i, p} \ cdot k_ {i, q}.}$

Egenskaperna hos den h ^{: te} konvergenta funktioner

För (fast i praktiken när ) kan vi definiera de rationella konvergenterna till den oändliga J-fraktionen , expanderad med ${\ displaystyle h \ geq 0}$${\ displaystyle h \ geq 2}$${\ displaystyle h^{\ text {th}}}$${\ displaystyle J^{[\ infty]} (z)}$

${\ displaystyle \ operatorname {Conv} _ {h} (z): = {\ frac {P_ {h} (z)} {Q_ {h} (z)}} = j_ {0}+j_ {1} z+ \ cdots +j_ {2h-1} z^{2h-1} +\ sum _ {n \ geq 2h} {\ widetilde {j}} _ {h, n} z^{n},}$

komponentmässigt genom sekvenserna och definierade rekursivt av ${\ displaystyle P_ {h} (z)}$${\ displaystyle Q_ {h} (z)}$

${\ displaystyle {\ begin {align} P_ {h} (z) & = (1-c_ {h} z) P_ {h-1} (z)-{\ text {ab}} _ {h} z^ {2} P_ {h-2} (z)+\ delta _ {h, 1} \\ Q_ {h} (z) & = (1-c_ {h} z) Q_ {h-1} (z) -{\ text {ab}} _ {h} z^{2} Q_ {h-2} (z)+(1-c_ {1} z) \ delta _ {h, 1}+\ delta _ {0 , 1}. \ End {align}}}$

Dessutom innebär rationaliteten i den konvergenta funktionen, för alla, ytterligare ändliga skillnadsekvationer och kongruensegenskaper som uppfylls av sekvensen av , och för om vi då har kongruensen ${\ displaystyle {\ text {Conv}} _ {h} (z)}$${\ displaystyle h \ geq 2}$${\ displaystyle j_ {n}}$${\ displaystyle M_ {h}: = {\ text {ab}} _ {2} \ cdots {\ text {ab}} _ {h+1}}$${\ displaystyle h | \ mid M_ {h}}$

${\ displaystyle j_ {n} \ equiv [z^{n}] \ operatorname {Conv} _ {h} (z) {\ pmod {h}},}$

för icke-symboliskt, bestämda val av parametersekvenser, och , när , dvs när dessa sekvenser gör inte underförstått att bero på ett hjälp parameter såsom , eller såsom i de exempel som finns i tabellen nedan. ${\ displaystyle \ {{\ text {ab}} _ {i} \}}$${\ displaystyle \ {c_ {i} \}}$${\ displaystyle h \ geq 2}$${\ displaystyle q}$${\ displaystyle x}$${\ displaystyle R}$

Exempel

Nästa tabell ger exempel på formler med sluten form för komponentsekvenserna som finns beräknat (och därefter visade sig vara korrekta i de citerade referenserna) i flera specialfall av de föreskrivna sekvenserna , genererade av de allmänna utvidgningarna av J-fraktionerna definierade i den första underavsnitt. Här definierar vi och parametrarna , och för att vara obestämda med avseende på dessa expansioner, där de föreskrivna sekvenserna som räknas upp med expansioner av dessa J-fraktioner definieras i termer av q-Pochhammer-symbolen , Pochhammer-symbolen och binomialkoefficienterna . ${\ displaystyle j_ {n}}$${\ displaystyle 0 <| a |, | b |, | q | <1}$${\ displaystyle R}$${\ displaystyle \ alpha \ in \ mathbb {Z} ^{+}}$${\ displaystyle x}$

${\ displaystyle j_ {n}}$	${\ displaystyle c_ {1}}$	${\ displaystyle c_ {i} (i \ geq 2)}$	${\ displaystyle {\ text {ab}} _ {i} (i \ geq 2)}$
${\ displaystyle q^{n^{2}}}$	${\ displaystyle q}$	${\ displaystyle q^{2h-3} \ left (q^{2h}+q^{2h-2} -1 \ right)}$	${\ displaystyle q^{6h-10} \ left (q^{2h-2} -1 \ right)}$
${\ displaystyle (a; q) _ {n}}$	${\ displaystyle 1-a}$	${\ displaystyle q^{h-1} -aq^{h-2} \ vänster (q^{h}+q^{h-1} -1 \ höger)}$	${\ displaystyle aq^{2h-4} (aq^{h-2} -1) (q^{h-1} -1)}$
${\ displaystyle \ left (zq^{-n}; q \ right) _ {n}}$	${\ displaystyle {\ frac {qz} {q}}}$	${\ displaystyle {\ frac {q^{h} -z-qz+q^{h} z} {q^{2h-1}}}}$	${\ displaystyle {\ frac {(q^{h-1} -1) (q^{h-1} -z) \ cdot z} {q^{4h-5}}}}}$
${\ displaystyle {\ frac {(a; q) _ {n}} {(b; q) _ {n}}}}$	${\ displaystyle {\ frac {1-a} {1-b}}}$	${\ displaystyle {\ frac {q^{i-2} \ left (q+abq^{2i-3}+a (1-q^{i-1} -q^{i})+b (q^ {i} -q-1) \ höger)} {(1-bq^{2i-4}) (1-bq^{2i-2})}}}}$	${\ displaystyle {\ frac {q^{2i-4} (1-bq^{i-3}) (1-aq^{i-2}) (a-bq^{i-2}) (1- q^{i-1})} {(1-bq^{2i-5}) (1-bq^{2i-4})^{2} (1-bq^{2i-3})}}}}$
${\ displaystyle \ alpha ^{n} \ cdot \ left ({\ frac {R} {\ alpha}} \ right) _ {n}}$	${\ displaystyle R}$	${\ displaystyle R+2 \ alpha (i-1)}$	${\ displaystyle (i-1) \ alpha (R+(i-2) \ alpha)}$
${\ displaystyle (-1)^{n} {\ binom {x} {n}}}$	${\ displaystyle -x}$	${\ displaystyle-{\ frac {(x+2 (i-1)^{2})} {(2i-1) (2i-3)}}}}$	${\displaystyle {\begin{cases}-{\frac {(x-i+2)(x+i-1)}{4\cdot (2i-3)^{2}}}&i\geq 3;\\-{\frac {1}{2}}x(x+1)&i=2.\end{cases}}}$
${\ displaystyle (-1)^{n} {\ binom {x+n} {n}}}$	${\ displaystyle -(x+1)}$	${\ displaystyle {\ frac {(x-2i (i-2) -1)} {(2i-1) (2i-3)}}}}$	${\displaystyle {\begin{cases}-{\frac {(x-i+2)(x+i-1)}{4\cdot (2i-3)^{2}}}&i\geq 3;\\-{\frac {1}{2}}x(x+1)&i=2.\end{cases}}}$

Konvergensradierna för dessa serier som motsvarar definitionen av Jacobi-typ J-fraktionerna ovan skiljer sig i allmänhet från den för motsvarande kraftserieutvidgningar som definierar de vanliga genereringsfunktionerna för dessa sekvenser.

Exempel

Genereringsfunktioner för sekvensen av kvadratnummer a _n = n ² är:

Vanlig genereringsfunktion

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

Exponentiell genererande funktion

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

Lambert -serien

Som ett exempel på en Lambert -serieidentitet som inte anges i huvudartikeln kan vi visa att vi har det ${\ displaystyle | x |, | xq | <1}$

${\ displaystyle \ sum _ {n \ geq 1} {\ frac {q^{n} x^{n}} {1-x^{n}}} = \ sum _ {n \ geq 1} {\ frac {q^{n} x^{n^{2}}} {1-qx^{n}}}+\ sum _ {n \ geq 1} {\ frac {q^{n} x^{n ( n+1)}} {1-x^{n}}},}$

där vi har specialfallet identitet för den genererande funktionen av sigmafunktionen , som ges av ${\ displaystyle d (n) \ equiv \ sigma _ {0} (n)}$

${\ displaystyle \ sum _ {n \ geq 1} {\ frac {x^{n}} {1-x^{n}}} = \ sum _ {n \ geq 1} {\ frac {x^{n ^{2}} (1+x^{n})} {1-x^{n}}}.}$

Bell -serien

${\ displaystyle \ operatorname {BG} _ {p} (n^{2}; x) = \ sum _ {n = 0}^{\ infty} (p^{n})^{2} x^{n } = {\ frac {1} {1-p^{2} x}}}$

Dirichlet -serien genererar funktion

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

med Riemann zeta -funktionen .

Sekvensen a _k genererad av en Dirichlet -seriens genereringsfunktion (DGF) motsvarande:

${\ displaystyle \ operatorname {DG} (a_ {k}; s) = \ zeta (s)^{m}}$

var är Riemann zeta -funktionen , har den vanliga genereringsfunktionen: ${\ displaystyle \ zeta (s)}$

${\ displaystyle \ sum _ {k = 1}^{k = n} a_ {k} x^{k} = x+{m \ välj 1} \ sum _ {2 \ leq a \ leq n} x^{a }+{m \ välj 2} {\ underset {ab \ leq n} {\ sum _ {a \ geq 2} \ sum _ {b \ geq 2}}} x^{ab}+{m \ välj 3} {\ underset {abc \ leq n} {\ sum _ {a \ geq 2} \ sum _ {c \ geq 2} \ sum _ {b \ geq 2}}} x^{abc}+{m \ välj 4 } {\ underset {abcd \ leq n} {\ sum _ {a \ geq 2} \ sum _ {b \ geq 2} \ sum _ {c \ geq 2} \ sum _ {d \ geq 2}}} x ^{abcd}+\ cdots}$

Multivariata genereringsfunktioner

Multivariata genereringsfunktioner uppstår i praktiken vid beräkning av antalet beredskapstabeller för icke-negativa heltal med angivna rad- och kolumntotaler. Anta att tabellen har r rader och c -kolumner; radsummorna är och kolumnsummorna är . Sedan, enligt IJ Good , är antalet sådana tabeller koefficienten för ${\ displaystyle t_ {1}, \ ldots t_ {r}}$${\ displaystyle s_ {1}, \ ldots s_ {c}}$

${\ displaystyle x_ {1}^{t_ {1}} \ ldots x_ {r}^{t_ {r}} y_ {1}^{s_ {1}} \ ldots y_ {c}^{s_ {c} }}$

i

${\ displaystyle \ prod _ {i = 1}^{r} \ prod _ {j = 1}^{c} {\ frac {1} {1-x_ {i} y_ {j}}}.}$

I det bivariata fallet inkluderar icke-polynomiska dubbelsummas exempel på så kallade " dubbla " eller " super " -genererande funktioner i formuläret följande två-variabla genereringsfunktioner för binomialkoefficienter , Stirling-tal och Eulerian-tal : ${\ displaystyle G (w, z): = \ sum _ {m, n \ geq 0} g_ {m, n} w^{m} z^{n}}$

${\ displaystyle {\ begin {align} e^{z+wz} & = \ sum _ {m, n \ geq 0} {\ binom {n} {m}} w^{m} {\ frac {z^ {n}} {n!}} \\ e^{w (e^{z} -1)} & = \ sum _ {m, n \ geq 0} \ left \ {{\ begin {matris} n \ \ m \ end {matris}} \ höger \} w^{m} {\ frac {z^{n}} {n!}} \\ {\ frac {1} {(1-z)^{w} }} & = \ sum _ {m, n \ geq 0} \ left [{\ begin {matrix} n \\ m \ end {matrix}} \ right] w^{m} {\ frac {z^{n }} {n!}} \\ {\ frac {1-w} {e^{(w-1) z} -w}} & = \ sum _ {m, n \ geq 0} \ left \ langle { \ begin {matris} n \\ m \ end {matris}} \ höger \ rangle w^{m} {\ frac {z^{n}} {n!}} \\ {\ frac {e^{w} -e^{z}} {we^{z} -ze^{w}}} & = \ sum _ {m, n \ geq 0} \ left \ langle {\ begin {matris} m+n+1 \ \ m \ end {matris}} \ höger \ rangle {\ frac {w^{m} z^{n}} {(m+n+1)!}}. \ end {align}}}$

Ansökningar

Olika tekniker: Utvärdering av summor och hantering av andra problem med att generera funktioner

Exempel 1: En formel för summor av harmoniska tal

Att generera funktioner ger oss flera metoder för att manipulera summor och för att fastställa identiteter mellan summor.

Det enklaste fallet inträffar när . Vi vet då det för motsvarande vanliga genereringsfunktioner. ${\ textstyle s_ {n} = \ sum _ {k = 0}^{n} {a_ {k}}}$${\ textstil S (z) = {\ frac {A (z)} {1-z}}}$

Till exempel kan vi manipulera , var är de harmoniska talen . Låt vara den vanliga genereringsfunktionen för de harmoniska talen. Sedan ${\ textstyle s_ {n} = \ sum _ {k = 1}^{n} H_ {k}}$${\ textstil H_ {k} = 1+{\ frac {1} {2}}+\ cdots+{\ frac {1} {k}}}$${\ textstil H (z) = \ sum _ {n \ geq 1} {H_ {n} z^{n}}}$

${\ displaystyle H (z) = {\ dfrac {\ sum _ {n \ geq 1} {{\ frac {1} {n}} z^{n}}} {1-z}} \ ,,}$

och sålunda

${\ displaystyle S (z) = \ sum _ {n \ geq 1} {s_ {n} z^{n}} = {\ dfrac {\ sum _ {n \ geq 1} {{\ frac {1} { n}} z^{n}}} {(1-z)^{2}}} \ ,.}$

Användning , konvolvering med täljaren ger ${\ displaystyle {\ frac {1} {(1-z)^{2}}} = \ sum _ {n \ geq 0} {(n+1) z^{n}}}$

${\ displaystyle s_ {n} = \ sum _ {k = 1}^{n} {{\ frac {1} {k}} (n+1-k)} = (n+1) H_ {n}- n \ ,,}$

som också kan skrivas som

${\ displaystyle \ sum _ {k = 1}^{n} {H_ {k}} = (n+1) (H_ {n+1} -1) \ ,.}$

Exempel 2: Modifierade binomialkoefficientsummor och binomialtransformationen

Som ett annat exempel på att använda genereringsfunktioner för att relatera sekvenser och manipulera summor definierar vi för en godtycklig sekvens de två summorna av summor ${\ displaystyle \ langle f_ {n} \ rangle}$

${\ displaystyle s_ {n}: = \ sum _ {m = 0}^{n} {\ binom {n} {m}} f_ {m} 3^{nm}}$

${\ displaystyle {\ widetilde {s}} _ {n}: = \ sum _ {m = 0}^{n} {\ binom {n} {m}} (m+1) (m+2) (m +3) f_ {m} 3^{nm},}$

för alla , och försök att uttrycka de andra summorna i termer av den första. Vi föreslår ett tillvägagångssätt genom att generera funktioner. ${\ displaystyle n \ geq 0}$

Först använder vi binomialtransformen för att skriva genereringsfunktionen för den första summan som

${\ displaystyle S (z) = {\ frac {1} {(1-3z)}} F \ vänster ({\ frac {z} {1-3z}} \ höger).}$

Eftersom genereringsfunktionen för sekvensen ges av , kan vi skriva genereringsfunktionen för den andra summan definierad ovan i formen ${\ displaystyle \ langle (n+1) (n+2) (n+3) f_ {n} \ rangle}$${\ displaystyle 6F (z)+18zF^{\ prime} (z)+9z^{2} F^{\ prime \ prime} (z)+z^{3} F^{(3)} (z) }$

${\ displaystyle {\ widetilde {S}} (z) = {\ frac {6} {(1-3z)}} F \ vänster ({\ frac {z} {1-3z}} \ höger)+{\ frac {18z} {(1-3z)^{2}}} F^{\ prime} \ vänster ({\ frac {z} {1-3z}} \ höger)+{\ frac {9z^{2} } {(1-3z)^{3}}} F^{\ prime \ prime} \ vänster ({\ frac {z} {1-3z}} \ höger)+{\ frac {z^{3}} {(1-3z)^{4}}} F^{(3)} \ vänster ({\ frac {z} {1-3z}} \ höger).}$

I synnerhet kan vi skriva denna modifierade summanererande funktion i form av

${\ displaystyle a (z) \ cdot S (z)+b (z) \ cdot zS^{\ prime} (z)+c (z) \ cdot z^{2} S^{\ prime \ prime} ( z)+d (z) \ cdot z^{3} S^{(3)} (z),}$

för , , och där . ${\ displaystyle a (z) = 6 (1-3z)^{3}}$${\ displaystyle b (z) = 18 (1-3z)^{3}}$${\ displaystyle c (z) = 9 (1-3z)^{3}}$${\ displaystyle d (z) = (1-3z)^{3}}$${\ displaystyle (1-3z)^{3} = 1-9z+27z^{2} -27z^{3}}$

Slutligen följer att vi kan uttrycka de andra summorna genom de första summorna i följande form:

${\ displaystyle {\ begin {align} {\ widetilde {s}} _ {n} & = [z^{n}] \ left (6 (1-3z)^{3} \ sum _ {n \ geq 0 } s_ {n} z^{n} +18 (1-3z)^{3} \ sum _ {n \ geq 0} ns_ {n} z^{n} +9 (1-3z)^{3} \ sum _ {n \ geq 0} n (n-1) s_ {n} z^{n}+(1-3z)^{3} \ sum _ {n \ geq 0} n (n-1) ( n-2) s_ {n} z^{n} \ höger) \\ & = (n+1) (n+2) (n+3) s_ {n} -9n (n+1) (n+2 ) s_ {n-1} +27 (n-1) n (n+1) s_ {n-2}-(n-2) (n-1) ns_ {n-3}. \ end {align}} }$

Exempel 3: Generering av funktioner för ömsesidigt rekursiva sekvenser

I det här exemplet omformulerar vi ett exempel på generering av funktioner som ges i avsnitt 7.3 i betongmatematik (se även avsnitt 7.1 i samma referens för vackra bilder av generering av funktionsserier). Anta i synnerhet att vi söker det totala antalet sätt (betecknade ) att kakla en rektangel med omärkta domino -bitar. Låt hjälpsekvensen,, definieras som antalet sätt att täcka en rektangel-minus-hörnsektion av hela rektangeln. Vi försöker använda dessa definitioner för att ge en sluten formel för utan att bryta ner denna definition för att hantera fall av vertikal kontra horisontella dominoer. Lägg märke till att de vanliga genereringsfunktionerna för våra två sekvenser motsvarar serien ${\ displaystyle U_ {n}}$${\ displaystyle 3 \ times n}$${\ displaystyle 2 \ times 1}$${\ displaystyle V_ {n}}$${\ displaystyle 3 \ times n}$${\ displaystyle U_ {n}}$

${\ displaystyle U (z) = 1+3z^{2}+11z^{4}+41z^{6}+\ cdots}$

${\ displaystyle V (z) = z+4z^{3}+15z^{5}+56z^{7}+\ cdots.}$

Om vi betraktar de möjliga konfigurationer som kan ges från och med den vänstra kanten av rektangeln, har vi möjlighet att uttrycka följande ömsesidigt beroende, eller ömsesidigt rekursiva , återfall relationer till våra två sekvenser när definieras som ovan där , , och : ${\ displaystyle 3 \ times n}$${\ displaystyle n \ geq 2}$${\ displaystyle U_ {0} = 1}$${\ displaystyle U_ {1} = 0}$${\ displaystyle V_ {0} = 0}$${\ displaystyle V_ {1} = 1}$

${\ displaystyle {\ begin {align} U_ {n} & = 2V_ {n-1}+U_ {n-2} \\ V_ {n} & = U_ {n-1}+V_ {n-2}. \ end {align}}}$

Eftersom vi har att för alla heltal , de indexförskjutna genereringsfunktionerna uppfyller (för övrigt har vi också en motsvarande formel när den ges av ), kan vi använda de ursprungliga villkoren som anges ovan och de två föregående återkommande relationerna för att se att vi har nästa två ekvationer avseende genereringsfunktionerna för dessa sekvenser som ges av ${\ displaystyle m \ geq 0}$${\ textstil z^{m} G (z) = \ sum _ {n \ geq m} g_ {nm} z^{n}}$${\ displaystyle m <0}$${\ displaystyle \ sum _ {n \ geq 0} g_ {n+m} z^{n} = {\ frac {G (z) -g_ {0} -g_ {1} z- \ cdots -g_ {m -1} z^{m-1}} {z^{m}}}}$

${\ displaystyle {\ begin {align} U (z) & = 2zV (z)+z^{2} U (z) +1 \\ V (z) & = zU (z)+z^{2} V (z) \\ & = {\ frac {z} {1-z^{2}}} U (z), \ end {align}}}$

vilket sedan innebär genom att lösa ekvationssystemet (och detta är det speciella tricket till vår metod här) att

${\ displaystyle U (z) = {\ frac {1-z^{2}} {1-4z^{2}+z^{4}}} = {\ frac {1} {3-{\ sqrt { 3}}}} \ cdot {\ frac {1} {1- (2+{\ sqrt {3}}) z^{2}}}+{\ frac {1} {3+{\ sqrt {3} }}} \ cdot {\ frac {1} {1- (2-{\ sqrt {3}}) z^{2}}}.}$

Således genom att utföra algebraiska förenklingar av sekvensen som härrör från de andra delfraktionernas expansioner av den genererande funktionen i den föregående ekvationen, finner vi att och det ${\ displaystyle U_ {2n+1} \ equiv 0}$

${\ displaystyle U_ {2n} = \ left \ lceil {\ frac {(2+{\ sqrt {3}})^{n}} {3-{\ sqrt {3}}}} \ right \ rceil,}$

för alla heltal . Vi noterar också att samma skiftade genereringsfunktionsteknik som tillämpas på andra ordningens återkommande för Fibonacci-talen är det prototypiska exemplet på att använda genereringsfunktioner för att lösa återkommande relationer i en variabel som redan omfattas, eller åtminstone antyds, i underavsnittet om rationella funktioner som ges ovan. ${\ displaystyle n \ geq 0}$

Convolution (Cauchy -produkter)

En diskret konvolvering av termerna i två formella kraftserier förvandlar en produkt av genererande funktioner till en genereringsfunktion som räknar upp en sammanfogad summa av de ursprungliga sekvenstermerna (se Cauchy -produkten ).

1. Tänk på att A ( z ) och B ( z ) är vanliga genereringsfunktioner.

   ${\ displaystyle C (z) = A (z) B (z) \ Vänsterhögerpil [z^{n}] C (z) = \ sum _ {k = 0}^{n} {a_ {k} b_ {nk }}}$

2. Tänk på att A ( z ) och B ( z ) är exponentiell genererande funktioner.

   ${\ displaystyle C (z) = A (z) B (z) \ Vänsterhögerpil [z^{n}/n!] C (z) = \ sum _ {k = 0}^{n} {\ binom {n } {k}} a_ {k} b_ {nk}}$

3. Tänk på den tredubbla sekvensen som följer av produkten från tre vanliga genereringsfunktioner

   ${\ displaystyle C (z) = F (z) G (z) H (z) \ Vänsterhögerpil [z^{n}] C (z) = \ sum _ {j+k+\ ell = n} f_ {j} g_ {k} h _ {\ ell}}$

4. Tänk på den -faldiga konvolutionen av en sekvens med sig själv för ett positivt heltal (se exemplet nedan för en applikation) ${\ displaystyle m}$${\ displaystyle m \ geq 1}$

   ${\ displaystyle C (z) = G (z)^{m} \ Vänsterhögerpil [z^{n}] C (z) = \ sum _ {k_ {1}+k_ {2}+\ cdots+k_ {m } = n} g_ {k_ {1}} g_ {k_ {2}} \ cdots g_ {k_ {m}}}$

Multiplikation av genereringsfunktioner, eller sammankoppling av deras underliggande sekvenser, kan motsvara en uppfattning om oberoende händelser i vissa räknings- och sannolikhetsscenarier. Om vi ​​till exempel antar den konventionella konventionen att sannolikhetsgenererande funktion , eller pgf , för en slumpmässig variabel betecknas med , så kan vi visa att för två slumpmässiga variabler ${\ displaystyle Z}$${\ displaystyle G_ {Z} (z)}$

${\ displaystyle G_ {X+Y} (z) = G_ {X} (z) G_ {Y} (z),}$

om och är oberoende. På samma sätt genereras antalet sätt att betala cent i myntvärden i värdet i uppsättningen (dvs i öre, nickel, dime, kvartal respektive halva dollar) av produkten ${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle n \ geq 0}$${\ displaystyle \ {1,5,10,25,50 \}}$

${\ displaystyle C (z) = {\ frac {1} {1-z}} {\ frac {1} {1-z^{5}}} {\ frac {1} {1-z^{10} }} {\ frac {1} {1-z^{25}}} {\ frac {1} {1-z^{50}}},}$

och dessutom, om vi tillåter centen att betalas i mynt av alla positiva heltalsbeteckningar, kommer vi fram till genereringen för antalet sådana kombinationer av förändringar som genereras av den partitionsfunktionsgenererande funktion som expanderas av den oändliga q-Pochhammer-symbolprodukten för . ${\ displaystyle n}$${\ textstyle \ prod _ {n \ geq 1} \ vänster (1-z^{n} \ höger)^{-1}}$

Exempel: Genereringsfunktionen för de katalanska talen

Ett exempel där varv av genererande funktioner är användbara tillåter oss att lösa för en specifik slutna formen funktion som representerar det vanliga genererande funktionen för Catalantal , . I synnerhet har denna sekvens den kombinatoriska tolkningen som antalet sätt att infoga parenteser i produkten så att multiplikationsordningen är fullständigt specificerad. Till exempel, vilket motsvarar de två uttrycken och . Det följer att sekvensen uppfyller en återkommande relation som ges av ${\ displaystyle C_ {n}}$${\ displaystyle x_ {0} \ cdot x_ {1} \ cdots x_ {n}}$${\ displaystyle C_ {2} = 2}$${\ displaystyle x_ {0} \ cdot (x_ {1} \ cdot x_ {2})}$${\ displaystyle (x_ {0} \ cdot x_ {1}) \ cdot x_ {2}}$

${\ displaystyle C_ {n} = \ sum _ {k = 0}^{n-1} C_ {k} C_ {n-1-k}+\ delta _ {n, 0} = C_ {0} C_ { n-1}+C_ {1} C_ {n-2}+\ cdots+C_ {n-1} C_ {0}+\ delta _ {n, 0}, \ n \ geq 0,}$

och så har en motsvarande invecklad genereringsfunktion, tillfredsställande ${\ displaystyle C (z)}$

${\ displaystyle C (z) = z \ cdot C (z)^{2} +1.}$

Sedan kommer vi fram till en formel för denna genereringsfunktion som ges av ${\ displaystyle C (0) = 1 \ neq \ infty}$

${\ displaystyle {\ begin {align} C (z) & = {\ frac {1-{\ sqrt {1-4z}}} {2z}} \\ & = \ sum _ {n \ geq 0} {\ frac {1} {n+1}} {\ binom {2n} {n}} z^{n}. \ end {align}}}$

Observera att den första ekvationen som implicit definierar ovan innebär att ${\ displaystyle C (z)}$

${\ displaystyle C (z) = {\ frac {1} {1-z \ cdot C (z)}},}$

vilket sedan leder till ytterligare en "enkel" (som i form) fortsatt fraktionsutvidgning av denna genererande funktion.

Exempel: Spanningsträd av fläktar och konvolutionsvolymer

En ordningsfläkt${\ displaystyle n}$ definieras som en graf på hörnen med kanter anslutna enligt följande regler: Vertex är ansluten med en enda kant till var och en av de andra hörnen, och hörnet är anslutet med en enda kant till nästa hörn för alla . Det finns en fan av ordning en, tre fans av ordning två, åtta fans av ordning tre, och så vidare. Ett spanträd är en undergraf av en graf som innehåller alla de ursprungliga hörnen och som innehåller tillräckligt med kanter för att göra denna undergraf ansluten, men inte så många kanter att det finns en cykel i undergrafen. Vi frågar hur många spännande träd av ett fan av ordning som är möjliga för varje . ${\ displaystyle \ {0,1, \ ldots, n \}}$${\ displaystyle 2n-1}$${\ displaystyle 0}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle k+1}$${\ displaystyle 1 \ leq k <n}$${\ displaystyle f_ {n}}$${\ displaystyle n}$${\ displaystyle n \ geq 1}$

Som en observation kan vi närma oss frågan genom att räkna antalet sätt att ansluta intilliggande uppsättningar hörn. Till exempel när , vi har det , vilket är en summa över sekvensvolymerna för sekvensen för . Mer allmänt kan vi skriva en formel för denna sekvens som ${\ displaystyle n = 4}$${\ displaystyle f_ {4} = 4+3 \ cdot 1+2 \ cdot 2+1 \ cdot 3+2 \ cdot 1 \ cdot 1+1 \ cdot 2 \ cdot 1+1 \ cdot 1 \ cdot 2+1 \ cdot 1 \ cdot 1 \ cdot 1 \ cdot 1 = 21}$${\ displaystyle m}$${\ displaystyle g_ {n} = n = [z^{n}] z/(1-z)^{2}}$${\ displaystyle m: = 1,2,3,4}$

${\ displaystyle f_ {n} = \ sum _ {m> 0} \ sum _ {\ scriptstyle k_ {1}+k_ {2}+\ cdots+k_ {m} = n \ atop \ scriptstyle k_ {1}, k_ {2}, \ ldots, k_ {m}> 0} g_ {k_ {1}} g_ {k_ {2}} \ cdots g_ {k_ {m}},}$

från vilken vi ser att den vanliga genereringsfunktionen för denna sekvens ges av nästa summa av konvolutions som

${\ displaystyle {\ begin {align} F (z) & = G (z)+G (z)^{2}+G (z)^{3}+\ cdots \\ [6pt] & = {\ frac {G (z)} {1-G (z)}} \\ [6pt] & = {\ frac {z} {(1-z)^{2} -z}} = {\ frac {z} { 1-3z+z^{2}}}, \ end {align}}}$

från vilken vi kan extrahera en exakt formel för sekvensen genom att ta delfraktionsexpansionen av den sista genererande funktionen.

Implicit genererande funktioner och Lagrange -inversionsformeln

Presentation av en gratis parameter (ormoljemetod)

Ibland är summan komplicerad, och det är inte alltid lätt att utvärdera. Metoden "Free Parameter" är en annan metod (kallad "ormolja" av H. Wilf) för att utvärdera dessa summor. ${\ displaystyle s_ {n}}$

Båda metoderna som diskuterats hittills har en gräns i summeringen. När n inte visas uttryckligen i summeringen kan vi betrakta som en "fri" parameter och behandla som en koefficient av , ändra ordningen på summeringarna på och och försöka beräkna den inre summan. ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle s_ {n}}$${\ textstil F (z) = \ summa {s_ {n} z^{n}}}$${\ displaystyle n}$${\ displaystyle k}$

Till exempel om vi vill beräkna

${\ displaystyle s_ {n} = \ sum _ {k \ geq 0} {{\ binom {n+k} {m+2k}} {\ binom {2k} {k}} {\ frac {(-1) ^{k}} {k+1}}} \ quad (m, n \ in \ mathbb {N} _ {0})}$

vi kan behandla som en "gratis" parameter och ställa in ${\ displaystyle n}$

${\ displaystyle F (z) = \ sum _ {n \ geq 0} {\ left [\ sum _ {k \ geq 0} {{\ binom {n+k} {m+2k}} {\ binom {2k } {k}} {\ frac {(-1)^{k}} {k+1}}} \ höger]} z^{n}}$

Utbytande summering ("ormolja") ger

${\ displaystyle F (z) = \ sum _ {k \ geq 0} {{\ binom {2k} {k}} {\ frac {(-1)^{k}} {k+1}} z^{ -k}} \ sum _ {n \ geq 0} {{\ binom {n+k} {m+2k}} z^{n+k}}}$

Nu är den inre summan . Således ${\ displaystyle {\ frac {z^{m+2k}} {(1-z)^{m+2k+1}}}}}$

${\ displaystyle {\ begin {align} F (z) & = {\ frac {z^{m}} {(1-z)^{m+1}}} \ sum _ {k \ geq 0} {{ \ frac {1} {k+1}} {\ binom {2k} {k}} ({\ frac {-z} {(1-z)^{2}}})^{k}} \\ & = {\ frac {z^{m}} {(1-z)^{m+1}}} \ sum _ {k \ geq 0} {C_ {k} ({\ frac {-z} {(1 -z)^{2}}})^{k}} \ quad {\ text {(där}} C_ {k} = k^{\ text {th}} {\ text {katalanskt nummer)}} \\ & = {\ frac {z^{m}} {(1-z)^{m+1}}} {\ frac {1-{\ sqrt {1+{\ frac {4z} {(1-z) ^{2}}}}}} {\ frac {-2z} {(1-z)^{2}}}} \\ & = {\ frac {-z^{m-1}} {2 (1 -z)^{m-1}}} (1-{\ frac {1+z} {1-z}}) \\ & = {\ frac {z^{m}} {(1-z)^ {m}}} = z {\ frac {z^{m-1}} {(1-z)^{m}}}. \ end {align}}}$

Då får vi

${\ displaystyle s_ {n} = {\ binom {n-1} {m-1}} \ quad {\ text {för}} \ quad m \ geq 1 \ quad, \ quad s_ {n} = [n = 0] \ quad {\ text {för}} \ quad m = 0.}$

Att generera funktioner bevisar kongruenser

Vi säger att två genereringsfunktioner (effektserier) är kongruenta modulo , skrivna om deras koefficienter är kongruenta modulo för alla , dvs för alla relevanta fall av heltal (observera att vi inte behöver anta att det är ett heltal här - det kan mycket väl vara polynomvärderade i vissa obestämda , till exempel). Om den " enklare " höger-genererande funktionen,, är en rationell funktion av , så antyder formen av dessa sekvenser att sekvensen så småningom periodiskt modulo fixeras särskilda fall av heltal-värderade . Till exempel kan vi bevisa att Euler nummer , uppfylla följande kongruens modulo : ${\ displaystyle m}$${\ displaystyle A (z) \ equiv B (z) {\ pmod {m}}}$${\ displaystyle m}$${\ displaystyle n \ geq 0}$${\ displaystyle a_ {n} \ equiv b_ {n} {\ pmod {m}}}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle x}$${\ displaystyle B (z)}$${\ displaystyle z}$${\ displaystyle m \ geq 2}$${\ displaystyle \ langle E_ {n} \ rangle = \ langle 1,1,5,61,1385, \ ldots \ rangle \ longmapsto \ langle 1,1,2,1,2,1,2, \ ldots \ rangle {\ pmod {3}}}$${\ displaystyle 3}$

${\ displaystyle \ sum _ {n \ geq 0} E_ {n} z^{n} = {\ frac {1-z^{2}} {1+z^{2}}} {\ pmod {3} }.}$

En av de mest användbara, om inte direkt kraftfulla, metoderna för att erhålla kongruenser för sekvenser som räknas upp med speciella generationsfunktioner modulo alla heltal (dvs inte bara primkrafter ) ges i avsnittet om fortsatta fraktionsrepresentationer av (även icke-konvergerande) vanliga generera funktioner med J-fraktioner ovan. Vi citerar ett särskilt resultat relaterat till att generera serier utökade genom en representation med fortsatt fraktion från Landos föreläsningar om generering av funktioner enligt följande: ${\ displaystyle p^{k}}$

Sats: (Congruences for Series Generated by Expansions of Continued Fractions) Antag att genereringsfunktionen representeras av en oändlig fortsatt del av formen${\ displaystyle A (z)}$

${\ displaystyle A (z) = {\ frac {1} {1-c_ {1} z}} {\ frac {p_ {1} z^{2}} {1-c_ {2} z}} {\ frac {p_ {2} z^{2}} {1-c_ {3} z}} \ cdots,}$

och det betecknar konvergensen till denna fortsatta fraktionsexpansion definierad så att för alla . Sedan 1) är funktionen rationell för alla där vi antar att ett av delbarhetskriterierna uppfylls, dvs för vissa ; och 2) Om heltalet delar produkten så har vi det .${\ displaystyle A_ {p} (z)}$${\ displaystyle p^{th}}$${\ displaystyle a_ {n} = [z^{n}] A_ {p} (z)}$${\ displaystyle 0 \ leq n <2p}$${\ displaystyle A_ {p} (z)}$${\ displaystyle p \ geq 2}$${\ displaystyle p | p_ {1}, p_ {1} p_ {2}, p_ {1} p_ {2} p_ {3} \ cdots}$${\ displaystyle p | p_ {1} p_ {2} \ cdots p_ {k}}$${\ displaystyle k \ geq 1}$${\ displaystyle p}$${\ displaystyle p_ {1} p_ {2} \ cdots p_ {k}}$${\ displaystyle A (z) \ equiv A_ {k} (z) {\ pmod {p}}}$

Att generera funktioner har också andra användningsområden för att bevisa kongruenser för deras koefficienter. Vi citerar de två följande specifika exemplen som härleder specialfallskongruenser för Stirling -nummer av den första sorten och för partitionsfunktionen (matematik) som visar mångsidigheten att generera funktioner för att hantera problem som involverar heltalssekvenser . ${\ displaystyle p (n)}$

Stirlingtalen modulerar små heltal

Den huvudartikeln på Stirling numren genereras av ändliga produkter

${\ displaystyle S_ {n} (x): = \ sum _ {k = 0}^{n} \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right] x^{k } = x (x+1) (x+2) \ cdots (x+n-1), \ n \ geq 1,}$

ger en översikt över kongruenserna för dessa nummer som härrör helt och hållet från egenskaperna hos deras genereringsfunktion som i avsnitt 4.6 i Wilfs lagerreferens Generatingfunctionology . Vi upprepar det grundläggande argumentet och märker att när de minskar modulo uppfyller dessa ändliga produktgenererande funktioner var och en ${\ displaystyle 2}$

${\ displaystyle S_ {n} (x) = [x (x+1)] \ cdot [x (x+1)] \ cdots = x^{\ lceil n/2 \ rceil} (x+1)^{ \ lgolv n/2 \ rgolv},}$

vilket innebär att pariteten för dessa Stirling -nummer matchar binomkoefficientens

${\ displaystyle \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right] \ equiv {\ binom {\ lfloor n/2 \ rfloor} {k- \ lceil n/2 \ rceil} } {\ pmod {2}},}$

och visar följaktligen att det är till och med när som helst . ${\ displaystyle \ left [{\ begin {matrix} n \\ k \ end {matrix}} \ right]}$${\ displaystyle k <\ left \ lceil {\ frac {n} {2}} \ right \ rceil}$

På samma sätt kan vi minska produkterna på höger sida som definierar Stirling-talgenererande funktioner modulo för att få lite mer komplicerade uttryck förutsatt att ${\ displaystyle 3}$

${\ displaystyle {\ begin {align} \ left [{\ begin {matrix} n \\ m \ end {matrix}} \ right] & \ equiv [x^{m}] \ left (x^{\ lceil n /3 \ rceil} (x+1)^{\ lceil (n-1)/3 \ rceil} (x+2)^{\ lfloor n/3 \ rfloor} \ right) && {\ pmod {3}} \\ & \ equiv \ sum _ {k = 0}^{m} {\ binom {\ lceil (n-1)/3 \ rceil} {k}} {\ binom {\ lfloor n/3 \ rfloor} { mk- \ lceil n/3 \ rceil}} \ gånger 2^{\ lceil n/3 \ rceil +\ lfloor n/3 \ rfloor -(mk)} && {\ pmod {3}}. \ end {align} }}$

Grattis till partitionsfunktionen

I detta exempel drar vi in ​​några av maskinerna för oändliga produkter vars kraftserieutvidgningar genererar expansioner av många specialfunktioner och räknar upp partitionsfunktioner. I synnerhet, minns vi att den partitionsfunktionen genereras av den reciproka oändlig Q-Pochhammersymbolen produkt (eller z-Pochhammer produkt som fallet kan vara) som ges av ${\ displaystyle p (n)}$

${\ displaystyle {\ begin {align} \ sum _ {n \ geq 1} p (n) z^{n} & = {\ frac {1} {(1-z) (1-z^{2}) (1-z^{3}) \ cdots}} \\ [4pt] & = 1+z+2z^{2}+3z^{3}+5z^{4}+7z^{5}+11z^ {6}+\ cdots. \ End {align}}}$

Denna partitionsfunktion uppfyller många kända kongruensegenskaper , som särskilt inkluderar följande resultat, även om det fortfarande finns många öppna frågor om formerna för relaterade heltalskongruenser för funktionen:

${\ displaystyle {\ begin {align} p (5m+4) & \ equiv 0 {\ pmod {5}} \\ p (7m+5) & \ equiv 0 {\ pmod {7}} \\ p (11m +6) & \ equiv 0 {\ pmod {11}} \\ p (25m+24) & \ equiv 0 {\ pmod {5^{2}}}. \ End {align}}}$

Vi visar hur man använder genereringsfunktioner och manipulationer av kongruenser för formella maktserier för att ge ett mycket elementärt bevis på den första av dessa kongruenser som anges ovan.

Först observerar vi att den binomiala koefficientgenererande funktionen, tillfredsställer att var och en av dess koefficienter är delbara med undantag för de som motsvarar krafterna hos , som alla annars har en återstod av modulo . Så kan vi skriva ${\ displaystyle 1/(1-z)^{5}}$${\ displaystyle 5}$${\ displaystyle 1, z^{5}, z^{10}, \ ldots}$${\ displaystyle 1}$${\ displaystyle 5}$

${\ displaystyle {\ frac {1} {(1-z)^{5}}} \ equiv {\ frac {1} {1-z^{5}}} {\ pmod {5}} \ qquad \ iff \ qquad {\ frac {1-z^{5}} {(1-z)^{5}}} \ equiv 1 {\ pmod {5}},}$

vilket i synnerhet visar oss det

${\ displaystyle {\ frac {(1-z^{5}) (1-z^{10}) (1-z^{15}) \ cdots} {\ left \ {(1-z) (1- z^{2}) (1-z^{3}) \ cdots \ right \}^{5}}} \ equiv 1 {\ pmod {5}}.}$

Därför ser vi lätt att delar varje koefficient av i de oändliga produktutökningarna av ${\ displaystyle 5}$${\ displaystyle z^{5m+1}}$

${\ displaystyle z \ cdot {\ frac {(1-z^{5}) (1-z^{10}) \ cdots} {(1-z) (1-z^{2}) \ cdots}} = z \ cdot \ left \ {(1-z) (1-z^{2}) \ cdots \ right \}^{4} \ times {\ frac {(1-z^{5}) (1- z^{10}) \ cdots} {\ left \ {(1-z) (1-z^{2}) \ cdots \ right \}^{5}}}.}$

Slutligen, eftersom vi kan skriva genereringsfunktionen för partitionsfunktionen som

${\ displaystyle {\ begin {align} & {\ frac {z} {(1-z) (1-z^{2}) \ cdots}} \\ [5pt] = {} & z \ cdot {\ frac { (1-z^{5}) (1-z^{10}) \ cdots} {(1-z) (1-z^{2}) \ cdots}} \ gånger (1+z^{5} +z^{10}+\ cdots) (1+z^{10}+z^{20}+\ cdots) \ cdots \\ [5pt] = {} & z+\ sum _ {n \ geq 2} p ( n-1) z^{n}, \ end {align}}}$

vi kan jämställa koefficienterna i de tidigare ekvationerna för att bevisa vårt önskade kongruensresultat, nämligen det för alla . ${\ displaystyle z^{5m+5}}$${\ displaystyle p (5m+4) \ equiv 0 {\ pmod {5}}}$${\ displaystyle m \ geq 0}$

Transformationer av genererande funktioner

Det finns ett antal transformationer av genereringsfunktioner som tillhandahåller andra applikationer (se huvudartikeln ). En transformation av en sekvens vanliga genereringsfunktion (OGF) tillhandahåller ett förfarande för att omvandla genereringsfunktionen för en sekvens till en genererande funktion som räknar upp en annan. Dessa transformationer involverar vanligtvis integrala formler som involverar en sekvens OGF (se integrala transformationer ) eller viktade summor över de högre ordningens derivat av dessa funktioner (se derivattransformationer ).

Generering av funktionstransformationer kan spela in när vi försöker uttrycka en genererande funktion för summorna

${\ displaystyle s_ {n}: = \ sum _ {m = 0}^{n} {\ binom {n} {m}} C_ {n, m} a_ {m},}$

i form av att involvera den ursprungliga sekvensgenererande funktionen. Till exempel, om summorna , då genereras funktionen för de modifierade summanuttrycken av (se även binomial transform och Stirling transform ). ${\ displaystyle S (z) = g (z) A (f (z))}$${\ displaystyle s_ {n}: = \ sum _ {k \ geq 0} {\ binom {n+k} {m+2k}} a_ {k}}$${\ displaystyle S (z) = {\ frac {z^{m}} {(1-z)^{m+1}}} A \ vänster ({\ frac {z} {(1-z)^{ 2}}} \ höger)}$

exercise 5.71

Det finns också integrerade formler för att konvertera mellan en sekvens OGF, och dess exponentiella genereringsfunktion, eller EGF , och vice versa som ges av ${\ displaystyle F (z)}$${\ displaystyle {\ widehat {F}} (z)}$

${\ displaystyle F (z) = \ int _ {0}^{\ infty} {\ widehat {F}} (tz) e^{-t} \, dt}$

${\ displaystyle {\ widehat {F}} (z) = {\ frac {1} {2 \ pi}} \ int _ {-\ pi}^{\ pi} F \ left (ze^{-\ imath \ vartheta} \ right) e^{e^{\ imath \ vartheta}} \, d \ vartheta,}$

förutsatt att dessa integraler konvergerar för lämpliga värden på . ${\ displaystyle z}$

Andra applikationer

Genereringsfunktioner används för att:

• Hitta en sluten formel för en sekvens som ges i en återkommande relation. Tänk till exempel på Fibonacci -tal .
• Hitta återkommande relationer för sekvenser - formen av en genererande funktion kan föreslå en återkommande formel.
• Hitta samband mellan sekvenser - om genereringsfunktionerna för två sekvenser har en liknande form kan sekvenserna i sig vara relaterade.
• Utforska sekvensernas asymptotiska beteende.
• Bevisa identiteter som involverar sekvenser.
• Lös uppräkningsproblem i kombinatorik och kodning av deras lösningar. Rookpolynom är ett exempel på en applikation i kombinatorik.
• Utvärdera oändliga summor.

Andra genereringsfunktioner

Exempel

Exempel på polynomsekvenser som genereras av mer komplexa genereringsfunktioner inkluderar:

• Appell polynom
• Chebyshev polynom
• Skillnadspolynom
• Generaliserade Appell -polynom
• Q-skillnadspolynom

Andra sekvenser som genereras av mer komplexa genereringsfunktioner:

• Dubbla exponentiella genereringsfunktioner. Till exempel: Aitkens Array: Triangle of Numbers
• Hadamard -produkter för genereringsfunktioner / diagonala genereringsfunktioner och deras motsvarande integrala transformationer

Konvolutionspolynom

Knuths artikel med titeln " Convolution Polynomials " definierar en generaliserad klass av konvolutionspolynomsekvenser genom deras speciella genererande funktioner i formen

${\ displaystyle F (z)^{x} = \ exp \ left (x \ log F (z) \ right) = \ sum _ {n \ geq 0} f_ {n} (x) z^{n}, }$

för någon analytisk funktion med en power series -expansion så att . Vi säger att en familj av polynom,, bildar en konvolutionsfamilj om och om följande konvolutionsvillkor gäller för alla och för alla : ${\ displaystyle F}$${\ displaystyle F (0) = 1}$${\ displaystyle f_ {0}, f_ {1}, f_ {2}, \ ldots}$${\ displaystyle \ deg \ {f_ {n} \} \ leq n}$${\ displaystyle x, y}$${\ displaystyle n \ geq 0}$

${\ displaystyle f_ {n} (x+y) = f_ {n} (x) f_ {0} (y)+f_ {n-1} (x) f_ {1} (y)+\ cdots+f_ { 1} (x) f_ {n-1} (y)+f_ {0} (x) f_ {n} (y).}$

Vi ser att för icke-identiskt noll konvolutionsfamiljer är denna definition ekvivalent med att kräva att sekvensen har en vanlig genererande funktion av den första formen som ges ovan.

En sekvens av konvolutionspolynom definierade i notationen ovan har följande egenskaper:

• Sekvensen är av binomial typ${\ displaystyle n! \ cdot f_ {n} (x)}$
• Speciella värden för sekvensen inkluderar och och${\ displaystyle f_ {n} (1) = [z^{n}] F (z)}$${\ displaystyle f_ {n} (0) = \ delta _ {n, 0}}$
• För godtyckliga (fasta) uppfyller dessa polynom konvolutionsformler för formen${\ displaystyle x, y, t \ in \ mathbb {C}}$

${\ displaystyle {\ begin {align} f_ {n} (x+y) & = \ sum _ {k = 0}^{n} f_ {k} (x) f_ {nk} (y) \\ f_ { n} (2x) & = \ sum _ {k = 0}^{n} f_ {k} (x) f_ {nk} (x) \\ xnf_ {n} (x+y) & = (x+y ) \ sum _ {k = 0}^{n} kf_ {k} (x) f_ {nk} (y) \\ {\ frac {(x+y) f_ {n} (x+y+tn)} {x+y+tn}} & = \ sum _ {k = 0}^{n} {\ frac {xf_ {k} (x+tk)} {x+tk}} {\ frac {yf_ {nk} (y+t (nk))} {y+t (nk)}}. \ end {align}}}$

För en fast icke-noll parameter har vi modifierade genereringsfunktioner för dessa konvolutionspolynomsekvenser som ges av ${\ displaystyle t \ in \ mathbb {C}}$

${\ displaystyle {\ frac {zF_ {n} (x+tn)} {(x+tn)}} = [z^{n}] {\ mathcal {F}} _ {t} (z)^{x },}$

där definieras implicit av en funktionell ekvation av formen . Dessutom kan vi använda matrismetoder (som i referensen) för att bevisa att med två konvolutionspolynomiska sekvenser, och med respektive motsvarande genereringsfunktioner, och för godtycklig har vi identiteten ${\ displaystyle {\ mathcal {F}} _ {t} (z)}$${\ displaystyle {\ mathcal {F}} _ {t} (z) = F \ left (x {\ mathcal {F}} _ {t} (z)^{t} \ right)}$${\ displaystyle \ langle f_ {n} (x) \ rangle}$${\ displaystyle \ langle g_ {n} (x) \ rangle}$${\ displaystyle F (z)^{x}}$${\ displaystyle G (z)^{x}}$${\ displaystyle t}$

${\ displaystyle [z^{n}] \ left (G (z) F \ left (zG (z)^{t} \ right) \ right)^{x} = \ sum _ {k = 0}^{ n} F_ {k} (x) G_ {nk} (x+tk).}$

Exempel på utbuktning polynom sekvenser innefattar den binomiala potensserie , så-kallade träd polynom , de Bell numren , de Laguerre polynom , och de Stirling faltning polynom . ${\ displaystyle {\ mathcal {B}} _ {t} (z) = 1+z {\ mathcal {B}} _ {t} (z)^{t}}$${\ displaystyle B (n)}$

Tabeller med speciella genereringsfunktioner

En första lista över speciella matematiska serier hittar du här . Ett antal användbara och speciella sekvensgenererande funktioner finns i avsnitt 5.4 och 7.4 i betongmatematik och i avsnitt 2.5 i Wilfs genereringsfunktion . Andra speciella genereringsfunktioner i noten inkluderar posterna i nästa tabell, som inte är komplett.

Formell kraftserie	Genereringsfunktionsformel	Anteckningar
${\ displaystyle \ sum _ {n \ geq 0} {\ binom {m+n} {n}} \ vänster (H_ {n+m} -H_ {m} \ höger) z^{n}}$	${\ displaystyle {\ frac {1} {(1-z)^{m+1}}} \ ln {\ frac {1} {1-z}}}$	${\ displaystyle H_ {n}}$är ett harmoniskt nummer av första ordningen
${\ displaystyle \ sum _ {n \ geq 0} B_ {n} {\ frac {z^{n}} {n!}}}$	${\ displaystyle {\ frac {z} {e^{z} -1}}}$	${\ displaystyle B_ {n}}$är ett Bernoulli -nummer
${\ displaystyle \ sum _ {n \ geq 0} F_ {mn} z^{n}}$	${\ displaystyle {\ frac {F_ {m} z} {1- (F_ {m-1}+F_ {m+1}) z+(-1)^{m} z^{2}}}}$	${\ displaystyle F_ {n}}$är ett Fibonacci -nummer och${\ displaystyle m \ in \ mathbb {Z} ^{+}}$
${\ displaystyle \ sum _ {n \ geq 0} \ left \ {{\ begin {matrix} n \\ m \ end {matrix}} \ right \} z^{n}}$	${\ displaystyle (z^{-1})^{\ overline {-m}} = {\ frac {z^{m}} {(1-z) (1-2z) \ cdots (1-mz)} }}$	${\ displaystyle x^{\ overline {n}}}$betecknar den stigande factorial- eller Pochhammer -symbolen och något heltal${\ displaystyle m \ geq 0}$
${\ displaystyle \ sum _ {n \ geq 0} \ left [{\ begin {matrix} n \\ m \ end {matrix}} \ right] z^{n}}$	${\ displaystyle z^{\ overline {m}} = z (z+1) \ cdots (z+m-1)}$
${\ displaystyle \ sum _ {n \ geq 1} {\ frac {(-1)^{n-1} 4^{n} (4^{n} -2) B_ {2n} z^{2n}} {(2n) \ cdot (2n)!}}}$	${\ displaystyle \ ln {\ frac {\ tan (z)} {z}}}$
${\ displaystyle \ sum _ {n \ geq 0} {\ frac {(1/2)^{\ overline {n}} z^{2n}} {(2n+1) \ cdot n!}}}$	${\ displaystyle z^{-1} \ arcsin (z)}$
${\ displaystyle \ sum _ {n \ geq 0} H_ {n}^{(s)} z^{n}}$	${\ displaystyle {\ frac {\ operatorname {Li} _ {s} (z)} {1-z}}}$	${\ displaystyle \ operatorname {Li} _ {s} (z)}$är polylogaritmfunktionen och är ett generaliserat harmoniskt tal för${\ displaystyle H_ {n}^{(s)}}$${\ displaystyle \ Re (s)> 1}$
${\ displaystyle \ sum _ {n \ geq 0} n^{m} z^{n}}$	${\ displaystyle \ sum _ {0 \ leq j \ leq m} \ left \ {{\ begin {matrix} m \\ j \ end {matrix}} \ right \} {\ frac {j! \ cdot z^{ j}} {(1-z)^{j+1}}}}$	${\ displaystyle \ left \ {{\ begin {matrix} n \\ m \ end {matrix}} \ right \}}$är ett Stirling -nummer av det andra slaget och där de enskilda termerna i expansionen uppfyller${\ displaystyle {\ frac {z^{i}} {(1-z)^{i+1}}} = \ sum _ {k = 0}^{i} {\ binom {i} {k}} {\ frac {(-1)^{ki}} {(1-z)^{k+1}}}}}$
${\ displaystyle \ sum _ {k <n} {\ binom {nk} {k}} {\ frac {n} {nk}} z^{k}}$	${\ displaystyle \ left ({\ frac {1+{\ sqrt {1+4z}}} {2}} \ right)^{n}+\ left ({\ frac {1-{\ sqrt {1+4z }}} {2}} \ höger)^{n}}$
${\ displaystyle \ sum _ {n_ {1}, \ ldots, n_ {m} \ geq 0} \ min (n_ {1}, \ ldots, n_ {m}) z_ {1}^{n_ {1}} \ cdots z_ {m}^{n_ {m}}}$	${\ displaystyle {\ frac {z_ {1} \ cdots z_ {m}} {(1-z_ {1}) \ cdots (1-z_ {m}) (1-z_ {1} \ cdots z_ {m} )}}}}$	Fallet med två variabler ges av ${\ displaystyle M (w, z): = \ sum _ {m, n \ geq 0} \ min (m, n) w^{m} z^{n} = {\ frac {wz} {(1- w) (1-z) (1-wz)}}}$
${\ displaystyle \ sum _ {n \ geq 0} {\ binom {s} {n}} z^{n}}$	${\ displaystyle (1+z)^{s}}$	${\ displaystyle s \ in \ mathbb {C}}$
${\ displaystyle \ sum _ {n \ geq 0} {\ binom {n} {k}} z^{n}}$	${\ displaystyle {\ frac {z^{k}} {(1-z)^{k+1}}}}}$	${\ displaystyle k \ in \ mathbb {N}}$
${\ displaystyle \ sum _ {n \ geq 1} \ log {(n)} z^{n}}$	${\ displaystyle -{\ partiell \ över \ partiell s} \ operatornamn {{Li} _ {s} (z)} | _ {s = 0}}$

Historia

George Pólya skriver i matematik och rimliga resonemang :

Namnet "genereringsfunktion" beror på Laplace . Men utan att ge det ett namn använde Euler enheten för att generera funktioner långt före Laplace [..]. Han tillämpade det här matematiska verktyget på flera problem i kombinationsanalys och talteori .

Se även

• Momentgenererande funktion
• Sannolikhetsgenererande funktion
• Generera funktionstransformation
• Stanleys ömsesidighetsteorem
• Applications to Partition (nummerteori)
• Kombinerande principer
• Cyklisk siktning
• Z-transform

Anteckningar

Referenser

• Aigner, Martin (2007). En kurs i uppräkning . Examen i matematik. 238 . Springer. ISBN 978-3-540-39035-0.
• Doubilet, Peter; Rota, Gian-Carlo ; Stanley, Richard (1972). "På grundvalarna för kombinatorisk teori. VI. Idén om att generera funktion" . Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability . 2 : 267–318. Zbl  0267.05002 . Omtryckt i Rota, Gian-Carlo (1975). "3. Idén att generera funktion". Slutlig operatörsberäkning . Med samarbete av P. Doubilet, C. Greene, D. Kahaner, A. Odlyzko och R. Stanley . Academic Press. s. 83–134. ISBN 0-12-596650-4. Zbl  0328.05007 .
• Flajolet, Philippe ; Sedgewick, Robert (2009). Analytic Combinatorics . Cambridge University Press. ISBN 978-0-521-89806-5. Zbl  1165.05001 .
• Goulden, Ian P .; Jackson, David M. (2004). Kombinerande uppräkning . Dover Publications . ISBN 978-0486435978.
• Graham, Ronald L .; Knuth, Donald E .; Patashnik, Oren (1994). "Kapitel 7: Generera funktioner". Betongmatematik. En grund för datavetenskap (2: a uppl.). Addison-Wesley. s. 320–380. ISBN 0-201-55802-5. Zbl  0836.00001 .
• Lando, Sergei K. (2003). Föreläsningar om generering av funktioner . American Mathematical Society. ISBN 978-0-8218-3481-7.
• Wilf, Herbert S. (1994). Generatingfunctionology (2: a upplagan). Academic Press. ISBN 0-12-751956-4. Zbl  0831.05001 .

externa länkar

• "Introduction to Ordinary Generating Functions" av Mike Zabrocki, York University, Mathematics and Statistics
• "Generating function" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Generera funktioner, kraftindex och myntbyte vid knivstopp
• "Generating Functions" av Ed Pegg Jr. , Wolfram Demonstrations Project , 2007.