Article de reference

Fonction génératrice

Une fonction génératrice est comme une corde à linge sur laquelle on suspend une séquence de nombres pour l'afficher. — Herbert Wilf , Générer la fonction (1994) Convergence Con...

Worldlex WikiFrancaisLecture gratuite

Une fonction génératrice est comme une corde à linge sur laquelle on suspend une séquence de nombres pour l'afficher.

— Herbert Wilf , Générer la fonction (1994)

Convergence

Contrairement à une série ordinaire, la convergence d'une série formelle n'est pas requise : en effet, la fonction génératrice n'est pas considérée comme une fonction à proprement parler , et la « variable » demeure une indéterminée . On peut généraliser ce concept aux séries formelles à plusieurs indéterminées, afin de représenter des informations sur des tableaux multidimensionnels infinis de nombres. Ainsi, les fonctions génératrices ne sont pas des fonctions au sens formel d'une application d'un domaine vers un codomaine .

Ces expressions en fonction de l'indéterminée et la composition (c'est-à-dire la substitution) avec d'autres fonctions génératrices. Puisque ces opérations sont également définies pour les fonctions, le résultat ressemble à une fonction de développement en série est la série formelle ; ceci explique la désignation de « fonctions génératrices ». Cependant, une telle interprétation n'est pas nécessairement possible, car les séries formelles ne sont pas tenues de converger lorsqu'une valeur numérique non nulle est substituée à n'ont pas de sens en tant qu'expressions désignant des séries formelles ; par exemple, les puissances négatives et fractionnaires de Fonction génératrice ordinaire (FGO)

Lorsque le terme « fonction génératrice » est employé sans précision, il désigne généralement une fonction génératrice ordinaire. La fonction génératrice ordinaire d'une suite est : ${\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}. <semantics><mrow><mstyle><mi>G</mi><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>.</mo></mstyle></mrow><annotation>{\displaystyle G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.}</annotation></semantics></math><img src=$

Fonction génératrice exponentielle (EGF)

La fonction génératrice exponentielle d'une suite est ${\displaystyle \operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}. <semantics><mrow><mstyle><mi>EG</mi><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mrow><mfrac><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {EG} (a_{n};x)=\sum _{n=0}^{\infty }a_{n}{\frac {x^{n}}{n!}}.}</annotation></semantics></math><img src=$

Les fonctions génératrices exponentielles sont généralement plus pratiques que les fonctions génératrices ordinaires pour les problèmes d'énumération combinatoire impliquant des objets étiquetés.

Un autre avantage des fonctions génératrices exponentielles est leur utilité pour transposer les relations de récurrence linéaire au domaine des équations différentielles . Par exemple, considérons la suite de Fibonacci qui satisfait la relation de récurrence linéaire . La fonction génératrice exponentielle correspondante a la forme suivante : ${\displaystyle \operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n <semantics><mrow><mstyle><mi>EF</mi><mo>⁡</mo><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \operatorname {EF} (x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}}</annotation></semantics></math><img src=$

et ses dérivées satisfont aisément l'équation différentielle ( x ) + EF( x ) , analogue directe de la relation de récurrence ci-dessus. Dans cette perspective, le terme factoriel n'est qu'un contre-terme servant à normaliser l'opérateur de dérivée agissant sur .

fonction génératrice de Poisson

La fonction génératrice de Poisson d'une suite est ${\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). <semantics><mrow><mstyle><mi>PG</mi><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><msup><mi>e</mi><mrow><mo>−</mo><mi>x</mi></mrow></msup><mrow><mfrac><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow><mo>=</mo><msup><mi>e</mi><mrow><mo>−</mo><mi>x</mi></mrow></msup><mspace></mspace><mi>EG</mi><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>)</mo><mo>.</mo></mstyle></mrow><annotation>{\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).}</annotation></semantics></math><img src=$

Série Lambert

est

{\displaystyle \operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}. <semantics><mrow><mstyle><mi>LG</mi><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mrow><mfrac><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mrow><mn>1</mn><mo>−</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {LG} (a_{n};x)=\sum _{n=1}^{\infty }a_{n}{\frac {x^{n}}{1-x^{n}}}.}</annotation></semantics></math></span><img src=

{\displaystyle b_{n}:=[x^{n}]\operatorname {LG} (a_{n};x) </span referrerpolicy=

Les entiers sont liés par la somme des diviseurs

{\displaystyle b_{n}=\sum _{d|n}a_{d}. <semantics><mrow><mstyle><msub><mi>b</mi><mrow><mi>n</mi></mrow></msub><mo>=</mo><munder><mo>∑</mo><mrow><mi>d</mi><mrow><mo>|</mo></mrow><mi>n</mi></mrow></munder><msub><mi>un</mi><mrow><mi>d</mi></mrow></msub><mo>.</mo></mstyle></mrow><annotation>{\displaystyle b_{n}=\sum _{d|n}a_{d}.}</annotation></semantics></math></span><img src=

x | , | xq | < 1, nous avons

{\displaystyle \sum _{n=1}^{\infty }{\frac {q^{n}x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {q^{n}x^{n^{2}}}{1-qx^{n}}}+\sum _{n=1}^{\infty }{\frac {q^{n}x^{n(n+1)}}{1-x^{n}}}, <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><mrow><msup><mi>q</mi><mrow><mi>n</mi></mrow></msup><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mrow><mrow><mn>1</mn><mo>−</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mrow></mfrac></mrow><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><mrow><msup><mi>q</mi><mrow><mi>n</mi></mrow></msup><msup><mi>x</mi><mrow><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup></mrow></msup></mrow><mrow><mn>1</mn><mo>−</mo><mi>q</mi><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mrow></mfrac></mrow><mo>+</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><mrow><msup><mi>q</mi><mrow><mi>n</mi></mrow></msup><msup><mi>x</mi><mrow><mi>n</mi><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow></msup></mrow><mrow><mn>1</mn><mo>−</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mrow></mfrac></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n=1}^{\infty }{\frac {q^{n}x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {q^{n}x^{n^{2}}}{1-qx^{n}}}+\sum _{n=1}^{\infty }{\frac {q^{n}x^{n(n+1)}}{1-x^{n}}},}</annotation></semantics></math></span><img src=

où nous avons l'identité du cas particulier pour la fonction génératrice de la fonction diviseuse , , donnée par ${\displaystyle \sum _{n=1}^{\infty }{\frac {x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {x^{n^{2}}\left(1+x^{n} ight)}{1-x^{n}}}. <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mrow><mn>1</mn><mo>−</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mrow></mfrac></mrow><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><mrow><msup><mi>x</mi><mrow><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup></mrow></msup><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mrow><mo>)</mo></mrow></mrow><mrow><mn>1</mn><mo>−</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n=1}^{\infty }{\frac {x^{n}}{1-x^{n}}}=\sum _{n=1}^{\infty }{\frac {x^{n^{2}}\left(1+x^{n} ight)}{1-x^{n}}}.}</annotation></semantics></math><img src=$

Série Bell

La série de Bell d'une séquence est une expression en termes à la fois d'un et est donnée par : ${\displaystyle \operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}. <semantics><mrow><mstyle><msub><mi>BG</mi><mrow><mi>p</mi></mrow></msub><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>un</mi><mrow><msup><mi>p</mi><mrow><mi>n</mi></mrow></msup></mrow></msub><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {BG} _{p}(a_{n};x)=\sum _{n=0}^{\infty }a_{p^{n}}x^{n}.}</annotation></semantics></math><img src=$

fonctions génératrices de séries de Dirichlet (DGF)

Les séries de Dirichlet formelles sont souvent classées comme des fonctions génératrices, bien qu'elles ne soient pas strictement des séries de puissances formelles. La fonction génératrice de la série de Dirichlet d'une suite est : ${\displaystyle \operatorname {DG} (a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}. <semantics><mrow><mstyle><mi>DG</mi><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>s</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><msup><mi>n</mi><mrow><mi>s</mi></mrow></msup></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {DG} (a_{n};s)=\sum _{n=1}^{\infty }{\frac {a_{n}}{n^{s}}}.}</annotation></semantics></math><img src=$

la série de Dirichlet est particulièrement utile lorsque est une fonction multiplicative , auquel cas elle a une expression de produit d'Euler en termes de la série de Bell de la fonction : ${\displaystyle \operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,. <semantics><mrow><mstyle><mi>DG</mi><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>s</mi><mo>)</mo><mo>=</mo><munder><mo>∏</mo><mrow><mi>p</mi></mrow></munder><msub><mi>BG</mi><mrow><mi>p</mi></mrow></msub><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><msup><mi>p</mi><mrow><mo>−</mo><mi>s</mi></mrow></msup><mo>)</mo><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {DG} (a_{n};s)=\prod _{p}\operatorname {BG} _{p}(a_{n};p^{-s})\,.}</annotation></semantics></math><img src=$

Si est un caractère de Dirichlet , sa fonction génératrice de série de Dirichlet est appelée série . Nous avons également une relation entre les paires de coefficients des développements en série de Lambert ci-dessus et leurs fonctions génératrices de série de Dirichlet. Plus précisément, nous pouvons démontrer que : ${\displaystyle [x^{n}]\operatorname {LG} (a_{n};x)=b_{n <semantics><mrow><mstyle><mo>[</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo><mi>LG</mi><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>)</mo><mo>=</mo><msub><mi>b</mi><mrow><mi>n</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle [x^{n}]\operatorname {LG} (a_{n};x)=b_{n}}</annotation></semantics></math><img src=$ ${\displaystyle \operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s), <semantics><mrow><mstyle><mi>DG</mi><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>s</mi><mo>)</mo><mi>ζ</mi><mo>(</mo><mi>s</mi><mo>)</mo><mo>=</mo><mi>DG</mi><mo>⁡</mo><mo>(</mo><msub><mi>b</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>s</mi><mo>)</mo><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {DG} (a_{n};s)\zeta (s)=\operatorname {DG} (b_{n};s),}</annotation></semantics></math><img src=$

La séquence générée par une fonction génératrice de séries de Dirichlet (DGF) correspondant à : ${\displaystyle \operatorname {DG} (a_{k};s)=\zeta (s)^{m <semantics><mrow><mstyle><mi>DG</mi><mo>⁡</mo><mo>(</mo><msub><mi>un</mi><mrow><mi>k</mi></mrow></msub><mo>;</mo><mi>s</mi><mo>)</mo><mo>=</mo><mi>ζ</mi><mo>(</mo><mi>s</mi><msup><mo>)</mo><mrow><mi>m</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \operatorname {DG} (a_{k};s)=\zeta (s)^{m}}</annotation></semantics></math><img src=$ ${\displaystyle \sum _{k=1}^{k=n}a_{k}x^{k}=x+{\binom {m}{1}}\sum _{2\leq a\leq n}x^{a}+{\binom {m}{2}}{\underset {ab\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }}}x^{ab}+{\binom {m}{3}}{\underset {abc\leq n}{\sum _{a=2}^{\infty }\sum _{c=2}^{\infty }\sum _{b=2}^{\infty }}}x^{abc}+{\binom {m}{4}}{\underset {abcd\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }}}x^{abcd}+\cdots <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>k</mi><mo>=</mo><mi>n</mi></mrow></munderover><msub><mi>un</mi><mrow><mi>k</mi></mrow></msub><msup><mi>x</mi><mrow><mi>k</mi></mrow></msup><mo>=</mo><mi>x</mi><mo>+</mo><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>m</mi><mn>1</mn></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><munder><mo>∑</mo><mrow><mn>2</mn><mo>≤</mo><mi>un</mi><mo>≤</mo><mi>n</mi></mrow></munder><msup><mi>x</mi><mrow><mi>un</mi></mrow></msup><mo>+</mo><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>m</mi><mn>2</mn></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><munder><mrow><munderover><mo>∑</mo><mrow><mi>un</mi><mo>=</mo><mn>2</mn></mrow><mrow><mi>∞</mi></mrow></munderover><munderover><mo>∑</mo><mrow><mi>b</mi><mo>=</mo><mn>2</mn></mrow><mrow><mi>∞</mi></mrow></munderover></mrow><mrow><mi>un</mi><mi>b</mi><mo>≤</mo><mi>n</mi></mrow></munder></mrow><msup><mi>x</mi><mrow><mi>un</mi><mi>b</mi></mrow></msup><mo>+</mo><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>m</mi><mn>3</mn></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><munder><mrow><munderover><mo>∑</mo><mrow><mi>un</mi><mo>=</mo><mn>2</mn></mrow><mrow><mi>∞</mi></mrow></munderover><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>2</mn></mrow><mrow><mi>∞</mi></mrow></munderover><munderover><mo>∑</mo><mrow><mi>b</mi><mo>=</mo><mn>2</mn></mrow><mrow><mi>∞</mi></mrow></munderover></mrow><mrow><mi>un</mi><mi>b</mi><mi>c</mi><mo>≤</mo><mi>n</mi></mrow></munder></mrow><msup><mi>x</mi><mrow><mi>un</mi><mi>b</mi><mi>c</mi></mrow></msup><mo>+</mo><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>m</mi><mn>4</mn></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><munder><mrow><munderover><mo>∑</mo><mrow><mi>un</mi><mo>=</mo><mn>2</mn></mrow><mrow><mi>∞</mi></mrow></munderover><munderover><mo>∑</mo><mrow><mi>b</mi><mo>=</mo><mn>2</mn></mrow><mrow><mi>∞</mi></mrow></munderover><munderover><mo>∑</mo><mrow><mi>c</mi><mo>=</mo><mn>2</mn></mrow><mrow><mi>∞</mi></mrow></munderover><munderover><mo>∑</mo><mrow><mi>d</mi><mo>=</mo><mn>2</mn></mrow><mrow><mi>∞</mi></mrow></munderover></mrow><mrow><mi>un</mi><mi>b</mi><mi>c</mi><mi>d</mi><mo>≤</mo><mi>n</mi></mrow></munder></mrow><msup><mi>x</mi><mrow><mi>un</mi><mi>b</mi><mi>c</mi><mi>d</mi></mrow></msup><mo>+</mo><mo>⋯</mo></mstyle></mrow><annotation>{\displaystyle \sum _{k=1}^{k=n}a_{k}x^{k}=x+{\binom {m}{1}}\sum _{2\leq a\leq n}x^{a}+{\binom {m}{2}}{\underset {ab\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }}}x^{ab}+{\binom {m}{3}}{\underset {abc\leq n}{\sum _{a=2}^{\infty }\sum _{c=2}^{\infty }\sum _{b=2}^{\infty }}}x^{abc}+{\binom {m}{4}}{\underset {abcd\leq n}{\sum _{a=2}^{\infty }\sum _{b=2}^{\infty }\sum _{c=2}^{\infty }\sum _{d=2}^{\infty }}}x^{abcd}+\cdots }</annotation></semantics></math><img src=$

fonctions génératrices de suites polynomiales

L'idée de fonctions génératrices peut être étendue aux suites d'autres objets. Ainsi, par exemple, les suites polynomiales de type binomial sont générées par : ${\displaystyle e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n <semantics><mrow><mstyle><msup><mi>e</mi><mrow><mi>x</mi><mi>f</mi><mo>(</mo><mi>t</mi><mo>)</mo></mrow></msup><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><mrow><msub><mi>p</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow><msup><mi>t</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle e^{xf(t)}=\sum _{n=0}^{\infty }{\frac {p_{n}(x)}{n!}}t^{n}}</annotation></semantics></math><img src=$

Voici quelques exemples de suites polynomiales générées par des fonctions génératrices plus complexes :

Autres fonctions génératrices

D'autres séquences générées par des fonctions génératrices plus complexes comprennent :

Fonctions génératrices exponentielles doubles
Produits de Hadamard des fonctions génératrices et des fonctions génératrices diagonales, et leurs transformations intégrales correspondantes

Polynômes de convolution

L'article de Knuth intitulé « Polynômes de convolution » définit une classe généralisée de suites de polynômes de convolution par leurs fonctions génératrices particulières de la forme ${\displaystyle F(z)^{x}=\exp {\bigl (}x\log F(z){\bigr )}=\sum _{n=0}^{\infty }f_{n}(x)z^{n}, <semantics><mrow><mstyle><mi>F</mi><mo>(</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>x</mi></mrow></msup><mo>=</mo><mi>exp</mi><mo>⁡</mo><mrow><mrow><mo>(</mo></mrow></mrow><mi>x</mi><mi>enregistrer</mi><mo>⁡</mo><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo><mrow><mrow><mo>)</mo></mrow></mrow><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>,</mo></mstyle></mrow><annotation>{\displaystyle F(z)^{x}=\exp {\bigl (}x\log F(z){\bigr )}=\sum _{n=0}^{\infty }f_{n}(x)z^{n},}</annotation></semantics></math><img src=$

On dit qu'une famille de polynômes, , forme une famille de convolution si et si la condition de convolution suivante est vérifiée pour tous et pour tout : ${\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). <semantics><mrow><mstyle><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>+</mo><mi>y</mi><mo>)</mo><mo>=</mo><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><msub><mi>f</mi><mrow><mn>0</mn></mrow></msub><mo>(</mo><mi>y</mi><mo>)</mo><mo>+</mo><msub><mi>f</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><msub><mi>f</mi><mrow><mn>1</mn></mrow></msub><mo>(</mo><mi>y</mi><mo>)</mo><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>f</mi><mrow><mn>1</mn></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><msub><mi>f</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>(</mo><mi>y</mi><mo>)</mo><mo>+</mo><msub><mi>f</mi><mrow><mn>0</mn></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>y</mi><mo>)</mo><mo>.</mo></mstyle></mrow><annotation>{\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).}</annotation></semantics></math><img src=$

Nous constatons que pour les familles de convolution non identiquement nulles, cette définition est équivalente à exiger que la séquence ait une fonction génératrice ordinaire de la première forme donnée ci-dessus.

Une suite de polynômes de convolution définie dans la notation ci-dessus possède les propriétés suivantes :

La suite est de type binomial
Les valeurs particulières de la séquence incluent et , et
Pour arbitraire (fixe) ${\displaystyle x,y,t\in \mathbb {C} <semantics><mrow><mstyle><mi>x</mi><mo>,</mo><mi>y</mi><mo>,</mo><mi>t</mi><mo>∈</mo><mrow><mi>C</mi></mrow></mstyle></mrow><annotation>{\displaystyle x,y,t\in \mathbb {C} }</annotation></semantics></math><img src=$

${\displaystyle {\begin{aligned}f_{n}(x+y)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(y)\\f_{n}(2x)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(x)\\xnf_{n}(x+y)&=(x+y)\sum _{k=0}^{n}kf_{k}(x)f_{n-k}(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_{n-k}(y+t(n-k))}{y+t(n-k)}}.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>+</mo><mi>y</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>f</mi><mrow><mi>k</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><msub><mi>f</mi><mrow><mi>n</mi><mo>−</mo><mi>k</mi></mrow></msub><mo>(</mo><mi>y</mi><mo>)</mo></mtd></mtr><mtr><mtd><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mn>2</mn><mi>x</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>f</mi><mrow><mi>k</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><msub><mi>f</mi><mrow><mi>n</mi><mo>−</mo><mi>k</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo></mtd></mtr><mtr><mtd><mi>x</mi><mi>n</mi><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>+</mo><mi>y</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mi>x</mi><mo>+</mo><mi>y</mi><mo>)</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><mi>k</mi><msub><mi>f</mi><mrow><mi>k</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><msub><mi>f</mi><mrow><mi>n</mi><mo>−</mo><mi>k</mi></mrow></msub><mo>(</mo><mi>y</mi><mo>)</mo></mtd></mtr><mtr><mtd><mrow><mfrac><mrow><mo>(</mo><mi>x</mi><mo>+</mo><mi>y</mi><mo>)</mo><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>+</mo><mi>y</mi><mo>+</mo><mi>t</mi><mi>n</mi><mo>)</mo></mrow><mrow><mi>x</mi><mo>+</mo><mi>y</mi><mo>+</mo><mi>t</mi><mi>n</mi></mrow></mfrac></mrow></mtd><mtd><mi></mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><mfrac><mrow><mi>x</mi><msub><mi>f</mi><mrow><mi>k</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>+</mo><mi>t</mi><mi>k</mi><mo>)</mo></mrow><mrow><mi>x</mi><mo>+</mo><mi>t</mi><mi>k</mi></mrow></mfrac></mrow><mrow><mfrac><mrow><mi>y</mi><msub><mi>f</mi><mrow><mi>n</mi><mo>−</mo><mi>k</mi></mrow></msub><mo>(</mo><mi>y</mi><mo>+</mo><mi>t</mi><mo>(</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>)</mo><mo>)</mo></mrow><mrow><mi>y</mi><mo>+</mo><mi>t</mi><mo>(</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>)</mo></mrow></mfrac></mrow><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}f_{n}(x+y)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(y)\\f_{n}(2x)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(x)\\xnf_{n}(x+y)&=(x+y)\sum _{k=0}^{n}kf_{k}(x)f_{n-k}(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_{n-k}(y+t(n-k))}{y+t(n-k)}}.\end{aligned}}}</annotation></semantics></math><img src=$

Pour un paramètre non nul fixé ${\displaystyle t\in \mathbb {C} <semantics><mrow><mstyle><mi>t</mi><mo>∈</mo><mrow><mi>C</mi></mrow></mstyle></mrow><annotation>{\displaystyle t\in \mathbb {C} }</annotation></semantics></math><img src=$ ${\displaystyle {\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n} ight]{\mathcal {F}}_{t}(z)^{x}, <semantics><mrow><mstyle><mrow><mfrac><mrow><mi>z</mi><msub><mi>F</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>+</mo><mi>t</mi><mi>n</mi><mo>)</mo></mrow><mrow><mo>(</mo><mi>x</mi><mo>+</mo><mi>t</mi><mi>n</mi><mo>)</mo></mrow></mfrac></mrow><mo>=</mo><mrow><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo></mrow><msub><mrow><mrow><mi>F</mi></mrow></mrow><mrow><mi>t</mi></mrow></msub><mo>(</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>x</mi></mrow></msup><mo>,</mo></mstyle></mrow><annotation>{\displaystyle {\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n} ight]{\mathcal {F}}_{t}(z)^{x},}</annotation></semantics></math><img src=$ ${\displaystyle \left[z^{n} ight]\left(G(z)F\left(zG(z)^{t} ight) ight)^{x}=\sum _{k=0}^{n}F_{k}(x)G_{nk}(x+tk). </span referrerpolicy=$

Des exemples de suites de polynômes de convolution incluent la série de puissance binomiale , , les polynômes dits d'arbre , les nombres de Bell , , les polynômes de Laguerre et les polynômes de convolution de Stirling .

Fonctions génératrices ordinaires

Exemples de séquences simples

Les polynômes sont un cas particulier de fonctions génératrices ordinaires, correspondant à des suites finies, ou de manière équivalente à des suites qui s'annulent après un certain point. Ils sont importants car de nombreuses suites finies peuvent être utilement interprétées comme des fonctions génératrices, telles que le polynôme de Poincaré et d'autres.

Une fonction génératrice fondamentale est celle de la suite constante ${\displaystyle \sum _{n=0}^{\infty }x^{n}={\frac {1}{1-x}}. </span referrerpolicy=$

Le membre de gauche correspond au développement en série de Maclaurin du membre de droite. On peut également justifier l'égalité en multipliant la série entière de gauche par et en vérifiant que le résultat est la série entière constante 1 (autrement dit, que tous les coefficients, sauf celui de sont égaux à 0). De plus, aucune autre série entière ne peut posséder cette propriété. Le membre de gauche désigne donc l' inverse multiplicatif de dans l'anneau des séries entières.

Les expressions de la fonction génératrice ordinaire d'autres suites se déduisent facilement de celle-ci. Par exemple, la substitution donne la fonction génératrice de la suite géométrique pour toute constante ${\displaystyle \sum _{n=0}^{\infty }(ax)^{n}={\frac {1}{1-ax}}. </span referrerpolicy=$

(L'égalité découle également directement du fait que le membre de gauche est le développement en série de Maclaurin du membre de droite.) En particulier, ${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}x^{n}={\frac {1}{1+x}}. <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>+</mo><mi>x</mi></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n=0}^{\infty }(-1)^{n}x^{n}={\frac {1}{1+x}}.}</annotation></semantics></math><img src=$

On peut également introduire des intervalles réguliers dans la suite en remplaçant ; par exemple, pour la suite on obtient la fonction génératrice ${\displaystyle \sum _{n=0}^{\infty }x^{2n}={\frac {1}{1-x^{2}}}. <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msup><mi>x</mi><mrow><mn>2</mn><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><msup><mi>x</mi><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n=0}^{\infty }x^{2n}={\frac {1}{1-x^{2}}}.}</annotation></semantics></math><img src=$

En élevant au carré la fonction génératrice initiale, ou en calculant la dérivée des deux membres par rapport à , on constate que les coefficients forment la suite ${\displaystyle \sum _{n=0}^{\infty }(n+1)x^{n}={\frac {1}{(1-x)^{2}}}, </span referrerpolicy=$

et la troisième puissance a pour coefficients les nombres triangulaires est le coefficient binomial ^{n +}_2² ) , de sorte que ${\displaystyle \sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{n}={\frac {1}{(1-x)^{3}}}. <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow><mn>2</mn></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>x</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n=0}^{\infty }{\binom {n+2}{2}}x^{n}={\frac {1}{(1-x)^{3}}}.}</annotation></semantics></math><img src=$

Plus généralement, pour tout entier non négatif , il est vrai que ${\displaystyle \sum _{n=0}^{\infty }a^{n}{\binom {n+k}{k}}x^{n}={\frac {1}{(1-ax)^{k+1}}}\,. <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msup><mi>un</mi><mrow><mi>n</mi></mrow></msup><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mi>k</mi></mrow><mi>k</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>un</mi><mi>x</mi><msup><mo>)</mo><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></msup></mrow></mfrac></mrow><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n=0}^{\infty }a^{n}{\binom {n+k}{k}}x^{n}={\frac {1}{(1-ax)^{k+1}}}\,.}</annotation></semantics></math><img src=$

Depuis ${\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}, <semantics><mrow><mstyle><mn>2</mn><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow><mn>2</mn></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mo>−</mo><mn>3</mn><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mn>1</mn></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mo>+</mo><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>n</mi><mn>0</mn></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mo>=</mo><mn>2</mn><mrow><mfrac><mrow><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>(</mo><mi>n</mi><mo>+</mo><mn>2</mn><mo>)</mo></mrow><mn>2</mn></mfrac></mrow><mo>−</mo><mn>3</mn><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>+</mo><mn>1</mn><mo>=</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>,</mo></mstyle></mrow><annotation>{\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},}</annotation></semantics></math><img src=$

on peut trouver la fonction génératrice ordinaire de la suite ${\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}}}. </span referrerpolicy=$

On peut également développer alternativement pour générer cette même suite de carrés comme une somme de dérivées de la série géométrique sous la forme suivante : ${\displaystyle {\begin{aligned}G(n^{2};x)&=\sum _{n=0}^{\infty }n^{2}x^{n}\\[4px]&=\sum _{n=0}^{\infty }n(n-1)x^{n}+\sum _{n=0}^{\infty }nx^{n}\\[4px]&=x^{2}D^{2}\left[{\frac {1}{1-x}} ight]+xD\left[{\frac {1}{1-x}} ight]\\[4px]&={\frac {2x^{2}}{(1-x)^{3}}}+{\frac {x}{(1-x)^{2}}}={\frac {x(x+1)}{(1-x)^{3}}}.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>G</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>;</mo><mi>x</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>n</mi><mo>(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>)</mo><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup><mo>+</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>n</mi><msup><mi>x</mi><mrow><mi>n</mi></mrow></msup></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><msup><mi>x</mi><mrow><mn>2</mn></mrow></msup><msup><mi>D</mi><mrow><mn>2</mn></mrow></msup><mrow><mo>[</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mi>x</mi></mrow></mfrac></mrow><mo>]</mo></mrow><mo>+</mo><mi>x</mi><mi>D</mi><mrow><mo>[</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mi>x</mi></mrow></mfrac></mrow><mo>]</mo></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><mrow><mn>2</mn><msup><mi>x</mi><mrow><mn>2</mn></mrow></msup></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>x</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup></mrow></mfrac></mrow><mo>+</mo><mrow><mfrac><mi>x</mi><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>x</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mo>=</mo><mrow><mfrac><mrow><mi>x</mi><mo>(</mo><mi>x</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>x</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup></mrow></mfrac></mrow><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}G(n^{2};x)&=\sum _{n=0}^{\infty }n^{2}x^{n}\\[4px]&=\sum _{n=0}^{\infty }n(n-1)x^{n}+\sum _{n=0}^{\infty }nx^{n}\\[4px]&=x^{2}D^{2}\left[{\frac {1}{1-x}} ight]+xD\left[{\frac {1}{1-x}} ight]\\[4px]&={\frac {2x^{2}}{(1-x)^{3}}}+{\frac {x}{(1-x)^{2}}}={\frac {x(x+1)}{(1-x)^{3}}}.\end{aligned}}}</annotation></semantics></math><img src=$

Par récurrence, nous pouvons montrer de même pour les entiers positifs que ${\displaystyle n^{m}=\sum _{j=0}^{m}{\begin{Bmatrix}m\\j\end{Bmatrix}}{\frac {n!}{(n-j)!}}, <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mi>m</mi></mrow></msup><mo>=</mo><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi></mrow></munderover><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mi>m</mi></mtd></mtr><mtr><mtd><mi>j</mi></mtd></mtr></mtable><mo>}</mo></mrow></mrow><mrow><mfrac><mrow><mi>n</mi><mo>!</mo></mrow><mrow><mo>(</mo><mi>n</mi><mo>−</mo><mi>j</mi><mo>)</mo><mo>!</mo></mrow></mfrac></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle n^{m}=\sum _{j=0}^{m}{\begin{Bmatrix}m\\j\end{Bmatrix}}{\frac {n!}{(n-j)!}},}</annotation></semantics></math><img src=$

où ⁿ_k } désignent les nombres de Stirling de seconde espèce et où la fonction génératrice ${\displaystyle \sum _{n=0}^{\infty }{\frac {n!}{(n-j)!}}\,z^{n}={\frac {j!\cdot z^{j}}{(1-z)^{j+1}}}, <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><mrow><mi>n</mi><mo>!</mo></mrow><mrow><mo>(</mo><mi>n</mi><mo>−</mo><mi>j</mi><mo>)</mo><mo>!</mo></mrow></mfrac></mrow><mspace></mspace><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mrow><mi>j</mi><mo>!</mo><mo>⋅</mo><msup><mi>z</mi><mrow><mi>j</mi></mrow></msup></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>j</mi><mo>+</mo><mn>1</mn></mrow></msup></mrow></mfrac></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n=0}^{\infty }{\frac {n!}{(n-j)!}}\,z^{n}={\frac {j!\cdot z^{j}}{(1-z)^{j+1}}},}</annotation></semantics></math><img src=$

afin de pouvoir former les fonctions génératrices analogues sur les puissances entières ${\displaystyle {\frac {z^{k}}{(1-z)^{k+1}}}=\sum _{i=0}^{k}{\binom {k}{i}}{\frac {(-1)^{ki}}{(1-z)^{i+1}}}, </span referrerpolicy=$

nous pouvons appliquer une identité de somme finie bien connue impliquant les nombres de Stirling pour obtenir que ${\displaystyle \sum _{n=0}^{\infty }n^{m}z^{n}=\sum _{j=0}^{m}{\begin{Bmatrix}m+1\\j+1\end{Bmatrix}}{\frac {(-1)^{m-j}j!}{(1-z)^{j+1}}}. <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msup><mi>n</mi><mrow><mi>m</mi></mrow></msup><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi></mrow></munderover><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mi>m</mi><mo>+</mo><mn>1</mn></mtd></mtr><mtr><mtd><mi>j</mi><mo>+</mo><mn>1</mn></mtd></mtr></mtable><mo>}</mo></mrow></mrow><mrow><mfrac><mrow><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>m</mi><mo>−</mo><mi>j</mi></mrow></msup><mi>j</mi><mo>!</mo></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>j</mi><mo>+</mo><mn>1</mn></mrow></msup></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n=0}^{\infty }n^{m}z^{n}=\sum _{j=0}^{m}{\begin{Bmatrix}m+1\\j+1\end{Bmatrix}}{\frac {(-1)^{m-j}j!}{(1-z)^{j+1}}}.}</annotation></semantics></math><img src=$

Fonctions rationnelles

{\displaystyle f_{n}=p_{1}(n) ho _{1}^{n}+\cdots +p_{\ell }(n) ho _{\ell }^{n}, </span referrerpolicy=

où les racines réciproques, ${\displaystyle ho _{i}\in \mathbb {C} <semantics><mrow><mstyle><msub><mi>ρ</mi><mrow><mi>je</mi></mrow></msub><mo>∈</mo><mrow><mi>C</mi></mrow></mstyle></mrow><annotation>{\displaystyle ho _{i}\in \mathbb {C} }</annotation></semantics></math><img src=$

En général, les produits de Hadamard de fonctions rationnelles produisent des fonctions génératrices rationnelles. De même, si ${\displaystyle F(s,t):=\sum _{m,n\geq 0}f(m,n)w^{m}z^{n <semantics><mrow><mstyle><mi>F</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>t</mi><mo>)</mo><mo>:=</mo><munder><mo>∑</mo><mrow><mi>m</mi><mo>,</mo><mi>n</mi><mo>≥</mo><mn>0</mn></mrow></munder><mi>f</mi><mo>(</mo><mi>m</mi><mo>,</mo><mi>n</mi><mo>)</mo><msup><mi>w</mi><mrow><mi>m</mi></mrow></msup><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle F(s,t):=\sum _{m,n\geq 0}f(m,n)w^{m}z^{n}}</annotation></semantics></math><img src=$

est une fonction génératrice rationnelle bivariée, alors sa fonction génératrice diagonale correspondante , ${\displaystyle \operatorname {diag} (F):=\sum _{n=0}^{\infty }f(n,n)z^{n}, <semantics><mrow><mstyle><mi>diagnostic</mi><mo>⁡</mo><mo>(</mo><mi>F</mi><mo>)</mo><mo>:=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>f</mi><mo>(</mo><mi>n</mi><mo>,</mo><mi>n</mi><mo>)</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {diag} (F):=\sum _{n=0}^{\infty }f(n,n)z^{n},}</annotation></semantics></math><img src=$

est algébrique . Par exemple, si nous posons ${\displaystyle F(s,t):=\sum _{i,j\geq 0}{\binom {i+j}{i}}s^{i}t^{j}={\frac {1}{1-s-t}}, <semantics><mrow><mstyle><mi>F</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>t</mi><mo>)</mo><mo>:=</mo><munder><mo>∑</mo><mrow><mi>je</mi><mo>,</mo><mi>j</mi><mo>≥</mo><mn>0</mn></mrow></munder><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>je</mi><mo>+</mo><mi>j</mi></mrow><mi>je</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>s</mi><mrow><mi>je</mi></mrow></msup><msup><mi>t</mi><mrow><mi>j</mi></mrow></msup><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mi>s</mi><mo>−</mo><mi>t</mi></mrow></mfrac></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle F(s,t):=\sum _{i,j\geq 0}{\binom {i+j}{i}}s^{i}t^{j}={\frac {1}{1-s-t}},}</annotation></semantics></math><img src=$

La fonction génératrice des coefficients diagonaux de cette fonction génératrice est alors donnée par la formule OGF bien connue. ${\displaystyle \operatorname {diag} (F)=\sum _{n=0}^{\infty }{\binom {2n}{n}}z^{n}={\frac {1}{\sqrt {1-4z}}}. <semantics><mrow><mstyle><mi>diagnostic</mi><mo>⁡</mo><mo>(</mo><mi>F</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mn>2</mn><mi>n</mi></mrow><mi>n</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mn>1</mn><msqrt><mn>1</mn><mo>−</mo><mn>4</mn><mi>z</mi></msqrt></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \operatorname {diag} (F)=\sum _{n=0}^{\infty }{\binom {2n}{n}}z^{n}={\frac {1}{\sqrt {1-4z}}}.}</annotation></semantics></math><img src=$

Ce résultat est calculé de nombreuses manières, notamment par la formule intégrale de Cauchy ou l'intégration de contour , en prenant des résidus complexes , ou par des manipulations directes de séries de puissances formelles à deux variables.

Opérations sur les fonctions génératrices

La multiplication donne la convolution

{\displaystyle (a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots ) </span referrerpolicy=

d'une suite dont la fonction génératrice ordinaire est a pour fonction génératrice

{\displaystyle G(a_{n};x)\cdot {\frac {1}{1-x <semantics><mrow><mstyle><mi>G</mi><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>)</mo><mo>⋅</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mi>x</mi></mrow></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle G(a_{n};x)\cdot {\frac {1}{1-x}}}</annotation></semantics></math></span><img src=

/ ( 1 − x ) est la fonction génératrice ordinaire de la suite , nous avons les deux identités analogues suivantes pour les fonctions génératrices modifiées énumérant les variantes de séquence décalées de et , respectivement :

{\displaystyle {\begin{aligned}&z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\\[4px]&{\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}=\sum _{n=0}^{\infty }g_{n+m}z^{n}.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd></mtd><mtd><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mi>m</mi></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>g</mi><mrow><mi>n</mi><mo>−</mo><mi>m</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mtd></mtr><mtr><mtd></mtd><mtd><mrow><mfrac><mrow><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>−</mo><msub><mi>g</mi><mrow><mn>0</mn></mrow></msub><mo>−</mo><msub><mi>g</mi><mrow><mn>1</mn></mrow></msub><mi>z</mi><mo>−</mo><mo>⋯</mo><mo>−</mo><msub><mi>g</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msub><msup><mi>z</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup></mfrac></mrow><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>g</mi><mrow><mi>n</mi><mo>+</mo><mi>m</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}&z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\\[4px]&{\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}=\sum _{n=0}^{\infty }g_{n+m}z^{n}.\end{aligned}}}</annotation></semantics></math></span><img src=

Différenciation et intégration des fonctions génératrices

Nous avons les développements en série de puissances suivants pour la dérivée première d'une fonction génératrice et son intégrale : ${\displaystyle {\begin{aligned}G'(z)&=\sum _{n=0}^{\infty }(n+1)g_{n+1}z^{n}\\[4px]z\cdot G'(z)&=\sum _{n=0}^{\infty }ng_{n}z^{n}\\[4px]\int _{0}^{z}G(t)\,dt&=\sum _{n=1}^{\infty }{\frac {g_{n-1}}{n}}z^{n}.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msup><mi>G</mi><mo>′</mo></msup><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><msub><mi>g</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mtd></mtr><mtr><mtd><mi>z</mi><mo>⋅</mo><msup><mi>G</mi><mo>′</mo></msup><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>n</mi><msub><mi>g</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mtd></mtr><mtr><mtd><msubsup><mo>∫</mo><mrow><mn>0</mn></mrow><mrow><mi>z</mi></mrow></msubsup><mi>G</mi><mo>(</mo><mi>t</mi><mo>)</mo><mspace></mspace><mi>d</mi><mi>t</mi></mtd><mtd><mi></mi><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><msub><mi>g</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mi>n</mi></mfrac></mrow><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}G'(z)&=\sum _{n=0}^{\infty }(n+1)g_{n+1}z^{n}\\[4px]z\cdot G'(z)&=\sum _{n=0}^{\infty }ng_{n}z^{n}\\[4px]\int _{0}^{z}G(t)\,dt&=\sum _{n=1}^{\infty }{\frac {g_{n-1}}{n}}z^{n}.\end{aligned}}}</annotation></semantics></math><img src=$

L'opération de dérivation-multiplication de la seconde identité peut être répétée , mais cela nécessite d'alterner entre dérivation et multiplication. Si, au lieu de cela, on effectue e factorielle décroissante . ${\displaystyle z^{k}G^{(k)}(z)=\sum _{n=0}^{\infty }n^{\underline {k}}g_{n}z^{n}=\sum _{n=0}^{\infty }n(n-1)\dotsb (n-k+1)g_{n}z^{n}\quad { ext{for all }}k\in \mathbb {N} . <semantics><mrow><mstyle><msup><mi>z</mi><mrow><mi>k</mi></mrow></msup><msup><mi>G</mi><mrow><mo>(</mo><mi>k</mi><mo>)</mo></mrow></msup><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msup><mi>n</mi><mrow><munder><mi>k</mi><mo>_</mo></munder></mrow></msup><msub><mi>g</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>n</mi><mo>(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>)</mo><mo>⋯</mo><mo>(</mo><mi>n</mi><mo>−</mo><mi>k</mi><mo>+</mo><mn>1</mn><mo>)</mo><msub><mi>g</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mspace></mspace><mrow><mtext>pour tous </mtext></mrow><mi>k</mi><mo>∈</mo><mrow><mi>N</mi></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle z^{k}G^{(k)}(z)=\sum _{n=0}^{\infty }n^{\underline {k}}g_{n}z^{n}=\sum _{n=0}^{\infty }n(n-1)\dotsb (n-k+1)g_{n}z^{n}\quad { ext{for all }}k\in \mathbb {N} .}</annotation></semantics></math><img src=$

En utilisant les nombres de Stirling de seconde espèce , on peut transformer cela en une autre formule pour multiplier par ${\displaystyle n^{k <semantics><mrow><mstyle><msup><mi>n</mi><mrow><mi>k</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle n^{k}}</annotation></semantics></math><img src=$ ${\displaystyle \sum _{j=0}^{k}{\begin{Bmatrix}k\\j\end{Bmatrix}}z^{j}F^{(j)}(z)=\sum _{n=0}^{\infty }n^{k}f_{n}z^{n}\quad { ext{for all }}k\in \mathbb {N} . <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>k</mi></mrow></munderover><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mi>k</mi></mtd></mtr><mtr><mtd><mi>j</mi></mtd></mtr></mtable><mo>}</mo></mrow></mrow><msup><mi>z</mi><mrow><mi>j</mi></mrow></msup><msup><mi>F</mi><mrow><mo>(</mo><mi>j</mi><mo>)</mo></mrow></msup><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msup><mi>n</mi><mrow><mi>k</mi></mrow></msup><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mspace></mspace><mrow><mtext>pour tous </mtext></mrow><mi>k</mi><mo>∈</mo><mrow><mi>N</mi></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{j=0}^{k}{\begin{Bmatrix}k\\j\end{Bmatrix}}z^{j}F^{(j)}(z)=\sum _{n=0}^{\infty }n^{k}f_{n}z^{n}\quad { ext{for all }}k\in \mathbb {N} .}</annotation></semantics></math><img src=$

L'inversion d'ordre négatif de cette formule des puissances de la suite, correspondant à l'opération d'intégration répétée, est définie par la transformation de la série zêta et ses généralisations, définies comme une transformation dérivée des fonctions génératrices , ou encore, terme à terme, par une transformation intégrale de la fonction génératrice de la suite. Les opérations connexes d' intégration fractionnaire sur une fonction génératrice de la suite sont abordées ici .

Énumération des progressions arithmétiques de suites

Dans cette section, nous donnons des formules pour les fonctions génératrices énumérant la suite étant donné une fonction génératrice ordinaire , où , , et et sont des entiers (voir l' article principal sur les transformations ). Pour , il s'agit simplement de la décomposition usuelle d'une fonction en parties paires et impaires (c'est-à-dire, puissances paires et impaires) : ${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }f_{2n}z^{2n}&={\frac {F(z)+F(-z)}{2}}\\[4px]\sum _{n=0}^{\infty }f_{2n+1}z^{2n+1}&={\frac {F(z)-F(-z)}{2}}.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>f</mi><mrow><mn>2</mn><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mn>2</mn><mi>n</mi></mrow></msup></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><mrow><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mi>F</mi><mo>(</mo><mo>−</mo><mi>z</mi><mo>)</mo></mrow><mn>2</mn></mfrac></mrow></mtd></mtr><mtr><mtd><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>f</mi><mrow><mn>2</mn><mi>n</mi><mo>+</mo><mn>1</mn></mrow></msub><msup><mi>z</mi><mrow><mn>2</mn><mi>n</mi><mo>+</mo><mn>1</mn></mrow></msup></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><mrow><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>−</mo><mi>F</mi><mo>(</mo><mo>−</mo><mi>z</mi><mo>)</mo></mrow><mn>2</mn></mfrac></mrow><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }f_{2n}z^{2n}&={\frac {F(z)+F(-z)}{2}}\\[4px]\sum _{n=0}^{\infty }f_{2n+1}z^{2n+1}&={\frac {F(z)-F(-z)}{2}}.\end{aligned}}}</annotation></semantics></math><img src=$

Plus généralement, supposons que et que 2 πi / a ⁠ désigne la ${\displaystyle \sum _{n=0}^{\infty }f_{an+b}z^{an+b}={\frac {1}{a}}\sum _{m=0}^{a-1}\omega _{a}^{-mb}F\left(\omega _{a}^{m}z ight). </span referrerpolicy=$

Pour les entiers , une autre formule utile fournissant des progressions arithmétiques arrondies à l'entier inférieur quelque peu inversées — répétant effectivement chaque coefficient ${\displaystyle \sum _{n=0}^{\infty }f_{\left\lfloor {\frac {n}{m}} ight floor }z^{n}={\frac {1-z^{m}}{1-z}}F(z^{m})=\left(1+z+\cdots +z^{m-2}+z^{m-1} ight)F(z^{m}). </span referrerpolicy=$

-récursives et fonctions génératrices holonomes

Définitions

Une série de puissances formelle (ou fonction) est dite holonome si elle satisfait une équation différentielle linéaire de la forme ${\displaystyle c_{0}(z)F^{(r)}(z)+c_{1}(z)F^{(r-1)}(z)+\cdots +c_{r}(z)F(z)=0, <semantics><mrow><mstyle><msub><mi>c</mi><mrow><mn>0</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><msup><mi>F</mi><mrow><mo>(</mo><mi>r</mi><mo>)</mo></mrow></msup><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><msub><mi>c</mi><mrow><mn>1</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><msup><mi>F</mi><mrow><mo>(</mo><mi>r</mi><mo>−</mo><mn>1</mn><mo>)</mo></mrow></msup><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>c</mi><mrow><mi>r</mi></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mn>0</mn><mo>,</mo></mstyle></mrow><annotation>{\displaystyle c_{0}(z)F^{(r)}(z)+c_{1}(z)F^{(r-1)}(z)+\cdots +c_{r}(z)F(z)=0,}</annotation></semantics></math><img src=$

où les coefficients appartiennent au domaine des fonctions rationnelles, ${\displaystyle \mathbb {C} (z) <semantics><mrow><mstyle><mrow><mi>C</mi></mrow><mo>(</mo><mi>z</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {C} (z)}</annotation></semantics></math><img src=$ ${\displaystyle F(z) <semantics><mrow><mstyle><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle F(z)}</annotation></semantics></math><img src=$ ${\displaystyle \mathbb {C} (z) <semantics><mrow><mstyle><mrow><mi>C</mi></mrow><mo>(</mo><mi>z</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle \mathbb {C} (z)}</annotation></semantics></math><img src=$

Puisque l'on peut simplifier les dénominateurs si nécessaire dans l'équation précédente, on peut supposer que les fonctions sont des polynômes en -récurrence de la forme suivante : ${\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, <semantics><mrow><mstyle><msub><mrow><mrow><mover><mi>c</mi><mo>^</mo></mover></mrow></mrow><mrow><mi>s</mi></mrow></msub><mo>(</mo><mi>n</mi><mo>)</mo><msub><mi>f</mi><mrow><mi>n</mi><mo>+</mo><mi>s</mi></mrow></msub><mo>+</mo><msub><mrow><mrow><mover><mi>c</mi><mo>^</mo></mover></mrow></mrow><mrow><mi>s</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>(</mo><mi>n</mi><mo>)</mo><msub><mi>f</mi><mrow><mi>n</mi><mo>+</mo><mi>s</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mrow><mrow><mover><mi>c</mi><mo>^</mo></mover></mrow></mrow><mrow><mn>0</mn></mrow></msub><mo>(</mo><mi>n</mi><mo>)</mo><msub><mi>f</mi><mrow><mi>n</mi></mrow></msub><mo>=</mo><mn>0</mn><mo>,</mo></mstyle></mrow><annotation>{\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,}</annotation></semantics></math><img src=$

Pour tout et où les degré fini fixés en récursive et possède une fonction génératrice holonome sont . Les fonctions holonomes sont stables par l' opération de produit de Hadamard , , , , ${\displaystyle {\sqrt {1+z <semantics><mrow><mstyle><mrow><msqrt><mn>1</mn><mo>+</mo><mi>z</mi></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle {\sqrt {1+z}}}</annotation></semantics></math><img src=$ ${\displaystyle \sum _{n=0}^{\infty }{\frac {z^{n}}{(n!)^{2 <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mrow><mo>(</mo><mi>n</mi><mo>!</mo><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle \sum _{n=0}^{\infty }{\frac {z^{n}}{(n!)^{2}}}}</annotation></semantics></math><img src=$

et le non-convergent ${\displaystyle \sum _{n=0}^{\infty }n!\cdot z^{n <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>n</mi><mo>!</mo><mo>⋅</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle \sum _{n=0}^{\infty }n!\cdot z^{n}}</annotation></semantics></math><img src=$

Des exemples de avec des fonctions génératrices holonomes incluent / n + 1 ( 2 ⁿⁿ₎ et f où des séquences telles que ${\displaystyle {\sqrt {n <semantics><mrow><mstyle><mrow><msqrt><mi>n</mi></msqrt></mrow></mstyle></mrow><annotation>{\displaystyle {\sqrt {n}}}</annotation></semantics></math><img src=$ pas , et ne sont pas holonomes.

Logiciel pour la manipulation de séquences -récursives dans Mathematica comprennent les logiciels disponibles pour un usage non commercial sur le site du groupe de combinatoire RISC . Bien que majoritairement propriétaires, ces logiciels offrent des outils particulièrement puissants : un `Guess`module pour la prédiction des -récurrences impliquant des nombres harmoniques généralisés . D'autres modules disponibles sur ce site RISC sont spécifiquement dédiés à la manipulation des fonctions génératrices holonomes .

Relation avec la transformée de Fourier à temps discret

${\displaystyle G\left(a_{n};e^{-i\omega } ight)=\sum _{n=0}^{\infty }a_{n}e^{-i\omega n </span referrerpolicy=$ est la transformée de Fourier à temps discret de la séquence .

Croissance asymptotique d'une séquence

En calcul différentiel et intégral, le taux de croissance des coefficients d'une série entière permet souvent de déduire le rayon de convergence de cette série. L'inverse est également vrai : le rayon de convergence d'une fonction génératrice permet souvent de déduire la croissance asymptotique de la suite sous-jacente.

Par exemple, si une fonction génératrice ordinaire qui possède un rayon de convergence fini ${\displaystyle G(a_{n};x)={\frac {A(x)+B(x)\left(1-{\frac {x}{r}} ight)^{-\beta }}{x^{\alpha </span referrerpolicy=$

où et sont chacune des fonctions analytiques à un rayon de convergence supérieur à alors ${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}} ight)^{n}\sim {\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}} ight)^{n}={\frac {B(r)}{r^{\alpha }}}\left(\!\!{\binom {\beta }{n}}\!\! ight)\left({\frac {1}{r}} ight)^{n}\,, <semantics><mrow><mstyle><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>∼</mo><mrow><mfrac><mrow><mi>B</mi><mo>(</mo><mi>r</mi><mo>)</mo></mrow><mrow><msup><mi>r</mi><mrow><mi>α</mi></mrow></msup><mi>Γ</mi><mo>(</mo><mi>β</mi><mo>)</mo></mrow></mfrac></mrow><mspace></mspace><msup><mi>n</mi><mrow><mi>β</mi><mo>−</mo><mn>1</mn></mrow></msup><msup><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mi>r</mi></mfrac></mrow><mo>)</mo></mrow><mrow><mi>n</mi></mrow></msup><mo>∼</mo><mrow><mfrac><mrow><mi>B</mi><mo>(</mo><mi>r</mi><mo>)</mo></mrow><msup><mi>r</mi><mrow><mi>α</mi></mrow></msup></mfrac></mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mi>β</mi><mo>−</mo><mn>1</mn></mrow><mi>n</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mi>r</mi></mfrac></mrow><mo>)</mo></mrow><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mrow><mi>B</mi><mo>(</mo><mi>r</mi><mo>)</mo></mrow><msup><mi>r</mi><mrow><mi>α</mi></mrow></msup></mfrac></mrow><mrow><mo>(</mo><mrow><mspace></mspace><mspace></mspace><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>β</mi><mi>n</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mspace></mspace><mspace></mspace></mrow><mo>)</mo></mrow><msup><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mi>r</mi></mfrac></mrow><mo>)</mo></mrow><mrow><mi>n</mi></mrow></msup><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}} ight)^{n}\sim {\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}} ight)^{n}={\frac {B(r)}{r^{\alpha }}}\left(\!\!{\binom {\beta }{n}}\!\! ight)\left({\frac {1}{r}} ight)^{n}\,,}</annotation></semantics></math><img src=$

Cette approche peut souvent être itérée pour générer plusieurs termes dans une série asymptotique pour . En particulier, ${\displaystyle G\left(a_{n}-{\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}} ight)^{n};x ight)=G(a_{n};x)-{\frac {B(r)}{r^{\alpha }}}\left(1-{\frac {x}{r}} ight)^{-\beta }\,. <semantics><mrow><mstyle><mi>G</mi><mrow><mo>(</mo><mrow><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>−</mo><mrow><mfrac><mrow><mi>B</mi><mo>(</mo><mi>r</mi><mo>)</mo></mrow><msup><mi>r</mi><mrow><mi>α</mi></mrow></msup></mfrac></mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mi>β</mi><mo>−</mo><mn>1</mn></mrow><mi>n</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mi>r</mi></mfrac></mrow><mo>)</mo></mrow><mrow><mi>n</mi></mrow></msup><mo>;</mo><mi>x</mi></mrow><mo>)</mo></mrow><mo>=</mo><mi>G</mi><mo>(</mo><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>)</mo><mo>−</mo><mrow><mfrac><mrow><mi>B</mi><mo>(</mo><mi>r</mi><mo>)</mo></mrow><msup><mi>r</mi><mrow><mi>α</mi></mrow></msup></mfrac></mrow><msup><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><mrow><mfrac><mi>x</mi><mi>r</mi></mfrac></mrow></mrow><mo>)</mo></mrow><mrow><mo>−</mo><mi>β</mi></mrow></msup><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle G\left(a_{n}-{\frac {B(r)}{r^{\alpha }}}{\binom {n+\beta -1}{n}}\left({\frac {1}{r}} ight)^{n};x ight)=G(a_{n};x)-{\frac {B(r)}{r^{\alpha }}}\left(1-{\frac {x}{r}} ight)^{-\beta }\,.}</annotation></semantics></math><img src=$

La croissance asymptotique des coefficients de cette fonction génératrice peut alors être recherchée via la recherche de , et croît selon ces formules asymptotiques. Généralement, si la différence entre la fonction génératrice d'une suite et celle d'une seconde suite a un rayon de convergence supérieur au rayon de convergence des fonctions génératrices individuelles, alors les deux suites ont la même croissance asymptotique.

Croissance asymptotique de la suite des carrés

Comme indiqué ci-dessus, la fonction génératrice ordinaire de la suite des carrés est : ${\displaystyle G(n^{2};x)={\frac {x(x+1)}{(1-x)^{3}}}. <semantics><mrow><mstyle><mi>G</mi><mo>(</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>;</mo><mi>x</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mrow><mi>x</mi><mo>(</mo><mi>x</mi><mo>+</mo><mn>1</mn><mo>)</mo></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>x</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle G(n^{2};x)={\frac {x(x+1)}{(1-x)^{3}}}.}</annotation></semantics></math><img src=$

Avec , , , , et , nous pouvons vérifier que les carrés croissent comme prévu, comme les carrés : ${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}} ight)^{n}={\frac {1+1}{1^{-1}\,\Gamma (3)}}\,n^{3-1}\left({\frac {1}{1}} ight)^{n}=n^{2}. <semantics><mrow><mstyle><msub><mi>un</mi><mrow><mi>n</mi></mrow></msub><mo>∼</mo><mrow><mfrac><mrow><mi>B</mi><mo>(</mo><mi>r</mi><mo>)</mo></mrow><mrow><msup><mi>r</mi><mrow><mi>α</mi></mrow></msup><mi>Γ</mi><mo>(</mo><mi>β</mi><mo>)</mo></mrow></mfrac></mrow><mspace></mspace><msup><mi>n</mi><mrow><mi>β</mi><mo>−</mo><mn>1</mn></mrow></msup><msup><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mi>r</mi></mfrac></mrow><mo>)</mo></mrow><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mrow><mn>1</mn><mo>+</mo><mn>1</mn></mrow><mrow><msup><mn>1</mn><mrow><mo>−</mo><mn>1</mn></mrow></msup><mspace></mspace><mi>Γ</mi><mo>(</mo><mn>3</mn><mo>)</mo></mrow></mfrac></mrow><mspace></mspace><msup><mi>n</mi><mrow><mn>3</mn><mo>−</mo><mn>1</mn></mrow></msup><msup><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mn>1</mn></mfrac></mrow><mo>)</mo></mrow><mrow><mi>n</mi></mrow></msup><mo>=</mo><msup><mi>n</mi><mrow><mn>2</mn></mrow></msup><mo>.</mo></mstyle></mrow><annotation>{\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}} ight)^{n}={\frac {1+1}{1^{-1}\,\Gamma (3)}}\,n^{3-1}\left({\frac {1}{1}} ight)^{n}=n^{2}.}</annotation></semantics></math><img src=$

Croissance asymptotique des nombres catalans

${\displaystyle G(C_{n};x)={\frac {1-{\sqrt {1-4x}}}{2x}}. </span referrerpolicy=$
Avec , = , et conclure ${\displaystyle C_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}} ight)^{n}={\frac {-{\frac {1}{2}}}{\left({\frac {1}{4}} ight)^{1}\Gamma \left(-{\frac {1}{2}} ight)}}\,n^{-{\frac {1}{2}}-1}\left({\frac {1}{\,{\frac {1}{4}}\,}} ight)^{n}={\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}. <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mi>n</mi></mrow></msub><mo>∼</mo><mrow><mfrac><mrow><mi>B</mi><mo>(</mo><mi>r</mi><mo>)</mo></mrow><mrow><msup><mi>r</mi><mrow><mi>α</mi></mrow></msup><mi>Γ</mi><mo>(</mo><mi>β</mi><mo>)</mo></mrow></mfrac></mrow><mspace></mspace><msup><mi>n</mi><mrow><mi>β</mi><mo>−</mo><mn>1</mn></mrow></msup><msup><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mi>r</mi></mfrac></mrow><mo>)</mo></mrow><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mrow><mo>−</mo><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></mrow><mrow><msup><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mn>4</mn></mfrac></mrow><mo>)</mo></mrow><mrow><mn>1</mn></mrow></msup><mi>Γ</mi><mrow><mo>(</mo><mrow><mo>−</mo><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow></mrow><mo>)</mo></mrow></mrow></mfrac></mrow><mspace></mspace><msup><mi>n</mi><mrow><mo>−</mo><mrow><mfrac><mn>1</mn><mn>2</mn></mfrac></mrow><mo>−</mo><mn>1</mn></mrow></msup><msup><mrow><mo>(</mo><mrow><mfrac><mn>1</mn><mrow><mspace></mspace><mrow><mfrac><mn>1</mn><mn>4</mn></mfrac></mrow><mspace></mspace></mrow></mfrac></mrow><mo>)</mo></mrow><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><msup><mn>4</mn><mrow><mi>n</mi></mrow></msup><mrow><msup><mi>n</mi><mrow><mfrac><mn>3</mn><mn>2</mn></mfrac></mrow></msup><mrow><msqrt><mi>π</mi></msqrt></mrow></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle C_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}} ight)^{n}={\frac {-{\frac {1}{2}}}{\left({\frac {1}{4}} ight)^{1}\Gamma \left(-{\frac {1}{2}} ight)}}\,n^{-{\frac {1}{2}}-1}\left({\frac {1}{\,{\frac {1}{4}}\,}} ight)^{n}={\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}.}</annotation></semantics></math><img src=$

Fonctions génératrices bivariées et multivariées

La fonction génératrice à plusieurs variables peut être généralisée aux tableaux à indices multiples. Ces exemples de double somme non polynomiale sont appelés fonctions génératrices multivariées , ou super-fonctions génératrices . Pour deux variables, on les appelle souvent fonctions génératrices bivariées .

Cas bivarié

La fonction génératrice ordinaire d'un tableau bidimensionnel (où sont des nombres naturels) est : ${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}. <semantics><mrow><mstyle><mi>G</mi><mo>(</mo><msub><mi>un</mi><mrow><mi>m</mi><mo>,</mo><mi>n</mi></mrow></msub><mo>;</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>m</mi><mo>,</mo><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>un</mi><mrow><mi>m</mi><mo>,</mo><mi>n</mi></mrow></msub><msup><mi>x</mi><mrow><mi>m</mi></mrow></msup><msup><mi>y</mi><mrow><mi>n</mi></mrow></msup><mo>.</mo></mstyle></mrow><annotation>{\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.}</annotation></semantics></math><img src=$ binomiaux pour un ^nₖ₎ pour tous . Pour ce faire, on considère comme une suite dans dont les coefficients sont les valeurs de cette suite. La fonction génératrice pour est : ${\displaystyle {\frac {1}{1-ay}}, <semantics><mrow><mstyle><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mi>un</mi><mi>y</mi></mrow></mfrac></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle {\frac {1}{1-ay}},}</annotation></semantics></math><img src=$ ${\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-(1+x)y}}={\frac {1}{1-y-xy}}. <semantics><mrow><mstyle><munder><mo>∑</mo><mrow><mi>n</mi><mo>,</mo><mi>k</mi></mrow></munder><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>n</mi><mi>k</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>x</mi><mrow><mi>k</mi></mrow></msup><msup><mi>y</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mo>(</mo><mn>1</mn><mo>+</mo><mi>x</mi><mo>)</mo><mi>y</mi></mrow></mfrac></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mi>y</mi><mo>−</mo><mi>x</mi><mi>y</mi></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-(1+x)y}}={\frac {1}{1-y-xy}}.}</annotation></semantics></math><img src=$ et désignent les deux variables : ${\displaystyle {\begin{aligned}e^{z+wz}&=\sum _{m,n\geq 0}{\binom {n}{m}}w^{m}{\frac {z^{n}}{n!}}\\[4px]e^{w(e^{z}-1)}&=\sum _{m,n\geq 0}{\begin{Bmatrix}n\\m\end{Bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1}{(1-z)^{w}}}&=\sum _{m,n\geq 0}{\begin{bmatrix}n\\m\end{bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1-w}{e^{(w-1)z}-w}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}n\\m\end{matrix}} ight angle w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {e^{w}-e^{z}}{we^{z}-ze^{w}}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}m+n+1\\m\end{matrix}} ight angle {\frac {w^{m}z^{n}}{(m+n+1)!}}.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msup><mi>e</mi><mrow><mi>z</mi><mo>+</mo><mi>w</mi><mi>z</mi></mrow></msup></mtd><mtd><mi></mi><mo>=</mo><munder><mo>∑</mo><mrow><mi>m</mi><mo>,</mo><mi>n</mi><mo>≥</mo><mn>0</mn></mrow></munder><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>n</mi><mi>m</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>w</mi><mrow><mi>m</mi></mrow></msup><mrow><mfrac><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow></mtd></mtr><mtr><mtd><msup><mi>e</mi><mrow><mi>w</mi><mo>(</mo><msup><mi>e</mi><mrow><mi>z</mi></mrow></msup><mo>−</mo><mn>1</mn><mo>)</mo></mrow></msup></mtd><mtd><mi></mi><mo>=</mo><munder><mo>∑</mo><mrow><mi>m</mi><mo>,</mo><mi>n</mi><mo>≥</mo><mn>0</mn></mrow></munder><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mi>n</mi></mtd></mtr><mtr><mtd><mi>m</mi></mtd></mtr></mtable><mo>}</mo></mrow></mrow><msup><mi>w</mi><mrow><mi>m</mi></mrow></msup><mrow><mfrac><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow></mtd></mtr><mtr><mtd><mrow><mfrac><mn>1</mn><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>w</mi></mrow></msup></mrow></mfrac></mrow></mtd><mtd><mi></mi><mo>=</mo><munder><mo>∑</mo><mrow><mi>m</mi><mo>,</mo><mi>n</mi><mo>≥</mo><mn>0</mn></mrow></munder><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>n</mi></mtd></mtr><mtr><mtd><mi>m</mi></mtd></mtr></mtable><mo>]</mo></mrow></mrow><msup><mi>w</mi><mrow><mi>m</mi></mrow></msup><mrow><mfrac><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow></mtd></mtr><mtr><mtd><mrow><mfrac><mrow><mn>1</mn><mo>−</mo><mi>w</mi></mrow><mrow><msup><mi>e</mi><mrow><mo>(</mo><mi>w</mi><mo>−</mo><mn>1</mn><mo>)</mo><mi>z</mi></mrow></msup><mo>−</mo><mi>w</mi></mrow></mfrac></mrow></mtd><mtd><mi></mi><mo>=</mo><munder><mo>∑</mo><mrow><mi>m</mi><mo>,</mo><mi>n</mi><mo>≥</mo><mn>0</mn></mrow></munder><mrow><mo>⟨</mo><mrow><mtable><mtr><mtd><mi>n</mi></mtd></mtr><mtr><mtd><mi>m</mi></mtd></mtr></mtable></mrow><mo>⟩</mo></mrow><msup><mi>w</mi><mrow><mi>m</mi></mrow></msup><mrow><mfrac><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow></mtd></mtr><mtr><mtd><mrow><mfrac><mrow><msup><mi>e</mi><mrow><mi>w</mi></mrow></msup><mo>−</mo><msup><mi>e</mi><mrow><mi>z</mi></mrow></msup></mrow><mrow><mi>w</mi><msup><mi>e</mi><mrow><mi>z</mi></mrow></msup><mo>−</mo><mi>z</mi><msup><mi>e</mi><mrow><mi>w</mi></mrow></msup></mrow></mfrac></mrow></mtd><mtd><mi></mi><mo>=</mo><munder><mo>∑</mo><mrow><mi>m</mi><mo>,</mo><mi>n</mi><mo>≥</mo><mn>0</mn></mrow></munder><mrow><mo>⟨</mo><mrow><mtable><mtr><mtd><mi>m</mi><mo>+</mo><mi>n</mi><mo>+</mo><mn>1</mn></mtd></mtr><mtr><mtd><mi>m</mi></mtd></mtr></mtable></mrow><mo>⟩</mo></mrow><mrow><mfrac><mrow><msup><mi>w</mi><mrow><mi>m</mi></mrow></msup><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mrow><mrow><mo>(</mo><mi>m</mi><mo>+</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>!</mo></mrow></mfrac></mrow><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}e^{z+wz}&=\sum _{m,n\geq 0}{\binom {n}{m}}w^{m}{\frac {z^{n}}{n!}}\\[4px]e^{w(e^{z}-1)}&=\sum _{m,n\geq 0}{\begin{Bmatrix}n\\m\end{Bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1}{(1-z)^{w}}}&=\sum _{m,n\geq 0}{\begin{bmatrix}n\\m\end{bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1-w}{e^{(w-1)z}-w}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}n\\m\end{matrix}} ight angle w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {e^{w}-e^{z}}{we^{z}-ze^{w}}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}m+n+1\\m\end{matrix}} ight angle {\frac {w^{m}z^{n}}{(m+n+1)!}}.\end{aligned}}}</annotation></semantics></math><img src=$

Cas multivarié

calcul du nombre de tableaux de contingence entiers non négatifs avec des totaux de lignes et de colonnes spécifiés. Supposons que le tableau comporte ; les sommes des lignes sont colonnes sont Alors, selon I.J. Good [ le nombre de tels tableaux est le coefficient de : ${\displaystyle x_{1}^{t_{1}}\cdots x_{r}^{t_{r}}y_{1}^{s_{1}}\cdots y_{c}^{s_{c <semantics><mrow><mstyle><msubsup><mi>x</mi><mrow><mn>1</mn></mrow><mrow><msub><mi>t</mi><mrow><mn>1</mn></mrow></msub></mrow></msubsup><mo>⋯</mo><msubsup><mi>x</mi><mrow><mi>r</mi></mrow><mrow><msub><mi>t</mi><mrow><mi>r</mi></mrow></msub></mrow></msubsup><msubsup><mi>y</mi><mrow><mn>1</mn></mrow><mrow><msub><mi>s</mi><mrow><mn>1</mn></mrow></msub></mrow></msubsup><mo>⋯</mo><msubsup><mi>y</mi><mrow><mi>c</mi></mrow><mrow><msub><mi>s</mi><mrow><mi>c</mi></mrow></msub></mrow></msubsup></mstyle></mrow><annotation>{\displaystyle x_{1}^{t_{1}}\cdots x_{r}^{t_{r}}y_{1}^{s_{1}}\cdots y_{c}^{s_{c}}}</annotation></semantics></math><img src=$ ${\displaystyle \prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}. <semantics><mrow><mstyle><munderover><mo>∏</mo><mrow><mi>je</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>r</mi></mrow></munderover><munderover><mo>∏</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>c</mi></mrow></munderover><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><msub><mi>x</mi><mrow><mi>je</mi></mrow></msub><msub><mi>y</mi><mrow><mi>j</mi></mrow></msub></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}.}</annotation></semantics></math><img src=$

Représentation par des fractions continues (fractions de type Jacobi et fractions précises à ) est développée comme dans l'équation suivante et admet les développements en séries de puissances correspondants en fonction de et , où

Propriétés des (bien qu'en pratique lorsque ), nous pouvons définir les -fraction infinie, , développée par : ${\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=2h}^{\infty }{\widetilde {j}}_{h,n}z^{n <semantics><mrow><mstyle><msub><mi>Conv</mi><mrow><mi>h</mi></mrow></msub><mo>⁡</mo><mo>(</mo><mi>z</mi><mo>)</mo><mo>:=</mo><mrow><mfrac><mrow><msub><mi>P</mi><mrow><mi>h</mi></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo></mrow><mrow><msub><mi>Q</mi><mrow><mi>h</mi></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo></mrow></mfrac></mrow><mo>=</mo><msub><mi>j</mi><mrow><mn>0</mn></mrow></msub><mo>+</mo><msub><mi>j</mi><mrow><mn>1</mn></mrow></msub><mi>z</mi><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>j</mi><mrow><mn>2</mn><mi>h</mi><mo>−</mo><mn>1</mn></mrow></msub><msup><mi>z</mi><mrow><mn>2</mn><mi>h</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>+</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>2</mn><mi>h</mi></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mrow><mrow><mover><mi>j</mi><mo>~</mo></mover></mrow></mrow><mrow><mi>h</mi><mo>,</mo><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\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=2h}^{\infty }{\widetilde {j}}_{h,n}z^{n}}</annotation></semantics></math><img src=$
composante par composante à travers les séquences, et , définies récursivement par : ${\displaystyle {\begin{aligned}P_{h}(z)&=(1-c_{h}z)P_{h-1}(z)-{ ext{ab}}_{h}z^{2}P_{h-2}(z)+\delta _{h,1}\\Q_{h}(z)&=(1-c_{h}z)Q_{h-1}(z)-{ ext{ab}}_{h}z^{2}Q_{h-2}(z)+(1-c_{1}z)\delta _{h,1}+\delta _{0,1}.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msub><mi>P</mi><mrow><mi>h</mi></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mn>1</mn><mo>−</mo><msub><mi>c</mi><mrow><mi>h</mi></mrow></msub><mi>z</mi><mo>)</mo><msub><mi>P</mi><mrow><mi>h</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>−</mo><msub><mrow><mtext>ab</mtext></mrow><mrow><mi>h</mi></mrow></msub><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><msub><mi>P</mi><mrow><mi>h</mi><mo>−</mo><mn>2</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><msub><mi>δ</mi><mrow><mi>h</mi><mo>,</mo><mn>1</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>Q</mi><mrow><mi>h</mi></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mn>1</mn><mo>−</mo><msub><mi>c</mi><mrow><mi>h</mi></mrow></msub><mi>z</mi><mo>)</mo><msub><mi>Q</mi><mrow><mi>h</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>−</mo><msub><mrow><mtext>ab</mtext></mrow><mrow><mi>h</mi></mrow></msub><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><msub><mi>Q</mi><mrow><mi>h</mi><mo>−</mo><mn>2</mn></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mo>(</mo><mn>1</mn><mo>−</mo><msub><mi>c</mi><mrow><mn>1</mn></mrow></msub><mi>z</mi><mo>)</mo><msub><mi>δ</mi><mrow><mi>h</mi><mo>,</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>δ</mi><mrow><mn>0</mn><mo>,</mo><mn>1</mn></mrow></msub><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}P_{h}(z)&=(1-c_{h}z)P_{h-1}(z)-{ ext{ab}}_{h}z^{2}P_{h-2}(z)+\delta _{h,1}\\Q_{h}(z)&=(1-c_{h}z)Q_{h-1}(z)-{ ext{ab}}_{h}z^{2}Q_{h-2}(z)+(1-c_{1}z)\delta _{h,1}+\delta _{0,1}.\end{aligned}}}</annotation></semantics></math><img src=$
De plus, la rationalité de la fonction convergente pour tout implique des équations aux différences finies supplémentaires et des propriétés de congruence satisfaites par la suite de , et pour si alors nous avons la congruence ${\displaystyle j_{n}\equiv [z^{n}]\operatorname {Conv} _{h}(z){\pmod {h}}, <semantics><mrow><mstyle><msub><mi>j</mi><mrow><mi>n</mi></mrow></msub><mo>≡</mo><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo><msub><mi>Conv</mi><mrow><mi>h</mi></mrow></msub><mo>⁡</mo><mo>(</mo><mi>z</mi><mo>)</mo><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mi>h</mi><mo>)</mo></mrow><mo>,</mo></mstyle></mrow><annotation>{\displaystyle j_{n}\equiv [z^{n}]\operatorname {Conv} _{h}(z){\pmod {h}},}</annotation></semantics></math><img src=$
pour des choix non symboliques et déterminés des séquences de paramètres et lorsque , c'est-à-dire lorsque ces séquences ne dépendent pas implicitement d'un paramètre auxiliaire tel que ou , générées par les développements généraux des a | , | b | , | q | < 1 et les paramètres ${\displaystyle R,\alpha \in \mathbb {Z} ^{+ <semantics><mrow><mstyle><mi>R</mi><mo>,</mo><mi>α</mi><mo>∈</mo><msup><mrow><mi>Z</mi></mrow><mrow><mo>+</mo></mrow></msup></mstyle></mrow><annotation>{\displaystyle R,\alpha \in \mathbb {Z} ^{+}}</annotation></semantics></math><img src=$

nombres carrés sont :

où est la fonction zêta de Riemann .

Applications

Les fonctions génératrices servent à :

Find a closed formula for a sequence given in a recurrence relation, for example, Fibonacci numbers.
Find recurrence relations for sequences—the form of a generating function may suggest a recurrence formula.
Find relationships between sequences—if the generating functions of two sequences have a similar form, then the sequences themselves may be related.
Explore the asymptotic behaviour of sequences.
Prove identities involving sequences.
Solve enumeration problems in combinatorics and encoding their solutions. Rook polynomials are an example of an application in combinatorics.
Evaluate infinite sums.

Various techniques: Evaluating sums and tackling other problems with generating functions

Example 1: Formula for sums of harmonic numbers

Generating functions give us several methods to manipulate sums and to establish identities between sums.

The simplest case occurs when a_k. We then know that A(z)/1 − z⁠ for the corresponding ordinary generating functions.

For example, we can manipulate ${\displaystyle s_{n}=\sum _{k=1}^{n}H_{k}\,, <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><msub><mi>H</mi><mrow><mi>k</mi></mrow></msub><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle s_{n}=\sum _{k=1}^{n}H_{k}\,,}</annotation></semantics></math><img src=$ 1/2⁠ + ⋯ + ⁠1/k⁠ are the harmonic numbers. Let ${\displaystyle H(z)=\sum _{n=1}^{\infty }{H_{n}z^{n <semantics><mrow><mstyle><mi>H</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><msub><mi>H</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mrow></mstyle></mrow><annotation>{\displaystyle H(z)=\sum _{n=1}^{\infty }{H_{n}z^{n}}}</annotation></semantics></math><img src=$ ${\displaystyle H(z)={\frac {1}{1-z}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,, <semantics><mrow><mstyle><mi>H</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mi>z</mi></mrow></mfrac></mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mi>n</mi></mfrac></mrow><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle H(z)={\frac {1}{1-z}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,,}</annotation></semantics></math><img src=$ ${\displaystyle S(z)=\sum _{n=1}^{\infty }{s_{n}z^{n}}={\frac {1}{(1-z)^{2}}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,. <semantics><mrow><mstyle><mi>S</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mi>n</mi></mfrac></mrow><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle S(z)=\sum _{n=1}^{\infty }{s_{n}z^{n}}={\frac {1}{(1-z)^{2}}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,.}</annotation></semantics></math><img src=$

Using ${\displaystyle {\frac {1}{(1-z)^{2}}}=\sum _{n=0}^{\infty }(n+1)z^{n}\,, <semantics><mrow><mstyle><mrow><mfrac><mn>1</mn><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle {\frac {1}{(1-z)^{2}}}=\sum _{n=0}^{\infty }(n+1)z^{n}\,,}</annotation></semantics></math><img src=$ ${\displaystyle s_{n}=\sum _{k=1}^{n}{\frac {n+1-k}{k}}=(n+1)H_{n}-n\,, <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mn>1</mn><mo>−</mo><mi>k</mi></mrow><mi>k</mi></mfrac></mrow><mo>=</mo><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><msub><mi>H</mi><mrow><mi>n</mi></mrow></msub><mo>−</mo><mi>n</mi><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle s_{n}=\sum _{k=1}^{n}{\frac {n+1-k}{k}}=(n+1)H_{n}-n\,,}</annotation></semantics></math><img src=$ ${\displaystyle \sum _{k=1}^{n}{H_{k}}=(n+1)(H_{n+1}-1)\,. <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><msub><mi>H</mi><mrow><mi>k</mi></mrow></msub></mrow><mo>=</mo><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>(</mo><msub><mi>H</mi><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>−</mo><mn>1</mn><mo>)</mo><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{k=1}^{n}{H_{k}}=(n+1)(H_{n+1}-1)\,.}</annotation></semantics></math><img src=$

Example 2: Modified binomial coefficient sums and the binomial transform

As another example of using generating functions to relate sequences and manipulate sums, for an arbitrary sequence we define the two sequences of sums ${\displaystyle {\begin{aligned}s_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}f_{m}3^{n-m}\\[4px]{ ilde {s}}_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}(m+1)(m+2)(m+3)f_{m}3^{n-m}\,,\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub></mtd><mtd><mi></mi><mo>:=</mo><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>n</mi><mi>m</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msub><mi>f</mi><mrow><mi>m</mi></mrow></msub><msup><mn>3</mn><mrow><mi>n</mi><mo>−</mo><mi>m</mi></mrow></msup></mtd></mtr><mtr><mtd><msub><mrow><mrow><mover><mi>s</mi><mo>~</mo></mover></mrow></mrow><mrow><mi>n</mi></mrow></msub></mtd><mtd><mi></mi><mo>:=</mo><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>n</mi><mi>m</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mo>(</mo><mi>m</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>(</mo><mi>m</mi><mo>+</mo><mn>2</mn><mo>)</mo><mo>(</mo><mi>m</mi><mo>+</mo><mn>3</mn><mo>)</mo><msub><mi>f</mi><mrow><mi>m</mi></mrow></msub><msup><mn>3</mn><mrow><mi>n</mi><mo>−</mo><mi>m</mi></mrow></msup><mspace></mspace><mo>,</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}s_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}f_{m}3^{n-m}\\[4px]{ ilde {s}}_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}(m+1)(m+2)(m+3)f_{m}3^{n-m}\,,\end{aligned}}}</annotation></semantics></math><img src=$

First, we use the binomial transform to write the generating function for the first sum as ${\displaystyle S(z)={\frac {1}{1-3z}}F\left({\frac {z}{1-3z}} ight). <semantics><mrow><mstyle><mi>S</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi></mrow></mfrac></mrow><mi>F</mi><mrow><mo>(</mo><mrow><mfrac><mi>z</mi><mrow><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi></mrow></mfrac></mrow><mo>)</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle S(z)={\frac {1}{1-3z}}F\left({\frac {z}{1-3z}} ight).}</annotation></semantics></math><img src=$

Since the generating function for the sequence is given by ${\displaystyle 6F(z)+18zF'(z)+9z^{2}F''(z)+z^{3}F'''(z) <semantics><mrow><mstyle><mn>6</mn><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mn>18</mn><mi>z</mi><msup><mi>F</mi><mo>′</mo></msup><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mn>9</mn><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><msup><mi>F</mi><mo>″</mo></msup><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><msup><mi>z</mi><mrow><mn>3</mn></mrow></msup><msup><mi>F</mi><mo>‴</mo></msup><mo>(</mo><mi>z</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle 6F(z)+18zF'(z)+9z^{2}F''(z)+z^{3}F'''(z)}</annotation></semantics></math><img src=$ ${\displaystyle { ilde {S}}(z)={\frac {6}{(1-3z)}}F\left({\frac {z}{1-3z}} ight)+{\frac {18z}{(1-3z)^{2}}}F'\left({\frac {z}{1-3z}} ight)+{\frac {9z^{2}}{(1-3z)^{3}}}F''\left({\frac {z}{1-3z}} ight)+{\frac {z^{3}}{(1-3z)^{4}}}F'''\left({\frac {z}{1-3z}} ight). <semantics><mrow><mstyle><mrow><mrow><mover><mi>S</mi><mo>~</mo></mover></mrow></mrow><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mn>6</mn><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi><mo>)</mo></mrow></mfrac></mrow><mi>F</mi><mrow><mo>(</mo><mrow><mfrac><mi>z</mi><mrow><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi></mrow></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><mrow><mfrac><mrow><mn>18</mn><mi>z</mi></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><msup><mi>F</mi><mo>′</mo></msup><mrow><mo>(</mo><mrow><mfrac><mi>z</mi><mrow><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi></mrow></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><mrow><mfrac><mrow><mn>9</mn><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup></mrow></mfrac></mrow><msup><mi>F</mi><mo>″</mo></msup><mrow><mo>(</mo><mrow><mfrac><mi>z</mi><mrow><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi></mrow></mfrac></mrow><mo>)</mo></mrow><mo>+</mo><mrow><mfrac><msup><mi>z</mi><mrow><mn>3</mn></mrow></msup><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi><msup><mo>)</mo><mrow><mn>4</mn></mrow></msup></mrow></mfrac></mrow><msup><mi>F</mi><mo>‴</mo></msup><mrow><mo>(</mo><mrow><mfrac><mi>z</mi><mrow><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi></mrow></mfrac></mrow><mo>)</mo></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle { ilde {S}}(z)={\frac {6}{(1-3z)}}F\left({\frac {z}{1-3z}} ight)+{\frac {18z}{(1-3z)^{2}}}F'\left({\frac {z}{1-3z}} ight)+{\frac {9z^{2}}{(1-3z)^{3}}}F''\left({\frac {z}{1-3z}} ight)+{\frac {z^{3}}{(1-3z)^{4}}}F'''\left({\frac {z}{1-3z}} ight).}</annotation></semantics></math><img src=$

In particular, we may write this modified sum generating function in the form of ${\displaystyle a(z)\cdot S(z)+b(z)\cdot zS'(z)+c(z)\cdot z^{2}S''(z)+d(z)\cdot z^{3}S'''(z), <semantics><mrow><mstyle><mi>a</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>⋅</mo><mi>S</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mi>b</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>⋅</mo><mi>z</mi><msup><mi>S</mi><mo>′</mo></msup><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mi>c</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>⋅</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><msup><mi>S</mi><mo>″</mo></msup><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mi>d</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>⋅</mo><msup><mi>z</mi><mrow><mn>3</mn></mrow></msup><msup><mi>S</mi><mo>‴</mo></msup><mo>(</mo><mi>z</mi><mo>)</mo><mo>,</mo></mstyle></mrow><annotation>{\displaystyle a(z)\cdot S(z)+b(z)\cdot zS'(z)+c(z)\cdot z^{2}S''(z)+d(z)\cdot z^{3}S'''(z),}</annotation></semantics></math><img src=$

Finalement, il s'ensuit que nous pouvons exprimer les secondes sommes à l'aide des premières sommes sous la forme suivante : ${\displaystyle {\begin{aligned}{ ilde {s}}_{n}&=[z^{n}]\left(6(1-3z)^{3}\sum _{n=0}^{\infty }s_{n}z^{n}+18(1-3z)^{3}\sum _{n=0}^{\infty }ns_{n}z^{n}+9(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)s_{n}z^{n}+(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)(n-2)s_{n}z^{n} ight)\\[4px]&=(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{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msub><mrow><mrow><mover><mi>s</mi><mo>~</mo></mover></mrow></mrow><mrow><mi>n</mi></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo><mrow><mo>(</mo><mrow><mn>6</mn><mo>(</mo><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>+</mo><mn>18</mn><mo>(</mo><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>n</mi><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>+</mo><mn>9</mn><mo>(</mo><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>n</mi><mo>(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>)</mo><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>+</mo><mo>(</mo><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>n</mi><mo>(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>)</mo><mo>(</mo><mi>n</mi><mo>−</mo><mn>2</mn><mo>)</mo><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>(</mo><mi>n</mi><mo>+</mo><mn>2</mn><mo>)</mo><mo>(</mo><mi>n</mi><mo>+</mo><mn>3</mn><mo>)</mo><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><mo>−</mo><mn>9</mn><mi>n</mi><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>(</mo><mi>n</mi><mo>+</mo><mn>2</mn><mo>)</mo><msub><mi>s</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>+</mo><mn>27</mn><mo>(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>)</mo><mi>n</mi><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><msub><mi>s</mi><mrow><mi>n</mi><mo>−</mo><mn>2</mn></mrow></msub><mo>−</mo><mo>(</mo><mi>n</mi><mo>−</mo><mn>2</mn><mo>)</mo><mo>(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>)</mo><mi>n</mi><msub><mi>s</mi><mrow><mi>n</mi><mo>−</mo><mn>3</mn></mrow></msub><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}{ ilde {s}}_{n}&=[z^{n}]\left(6(1-3z)^{3}\sum _{n=0}^{\infty }s_{n}z^{n}+18(1-3z)^{3}\sum _{n=0}^{\infty }ns_{n}z^{n}+9(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)s_{n}z^{n}+(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)(n-2)s_{n}z^{n} ight)\\[4px]&=(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{aligned}}}</annotation></semantics></math><img src=$

Exemple 3 : Fonctions génératrices pour les séquences mutuellement récursives

Dans cet exemple, nous reformulons un exemple de fonction génératrice présenté dans la section 7.3 de *Concrete Mathematics* (voir également la section 7.1 du même ouvrage pour des illustrations de séries de fonctions génératrices). Supposons en particulier que nous cherchions le nombre total de façons (noté ) de paver un rectangle 3× définie comme le nombre de façons de recouvrir une portion du rectangle complet (rectangle 3× sans avoir à la décomposer davantage pour traiter les cas des dominos verticaux et horizontaux. Remarquons que les fonctions génératrices ordinaires de nos deux suites correspondent aux séries suivantes : ${\displaystyle {\begin{aligned}U(z)=1+3z^{2}+11z^{4}+41z^{6}+\cdots ,\\V(z)=z+4z^{3}+15z^{5}+56z^{7}+\cdots .\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>U</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mn>1</mn><mo>+</mo><mn>3</mn><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><mo>+</mo><mn>11</mn><msup><mi>z</mi><mrow><mn>4</mn></mrow></msup><mo>+</mo><mn>41</mn><msup><mi>z</mi><mrow><mn>6</mn></mrow></msup><mo>+</mo><mo>⋯</mo><mo>,</mo></mtd></mtr><mtr><mtd><mi>V</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>z</mi><mo>+</mo><mn>4</mn><msup><mi>z</mi><mrow><mn>3</mn></mrow></msup><mo>+</mo><mn>15</mn><msup><mi>z</mi><mrow><mn>5</mn></mrow></msup><mo>+</mo><mn>56</mn><msup><mi>z</mi><mrow><mn>7</mn></mrow></msup><mo>+</mo><mo>⋯</mo><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}U(z)=1+3z^{2}+11z^{4}+41z^{6}+\cdots ,\\V(z)=z+4z^{3}+15z^{5}+56z^{7}+\cdots .\end{aligned}}}</annotation></semantics></math><img src=$

Si l'on considère les configurations possibles qui peuvent être données en partant du bord gauche du rectangle 3 par définies comme ci-dessus où , , et : ${\displaystyle {\begin{aligned}U_{n}&=2V_{n-1}+U_{n-2}\\V_{n}&=U_{n-1}+V_{n-2}.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><msub><mi>U</mi><mrow><mi>n</mi></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><mn>2</mn><msub><mi>V</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>U</mi><mrow><mi>n</mi><mo>−</mo><mn>2</mn></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>V</mi><mrow><mi>n</mi></mrow></msub></mtd><mtd><mi></mi><mo>=</mo><msub><mi>U</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>V</mi><mrow><mi>n</mi><mo>−</mo><mn>2</mn></mrow></msub><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}U_{n}&=2V_{n-1}+U_{n-2}\\V_{n}&=U_{n-1}+V_{n-2}.\end{aligned}}}</annotation></semantics></math><img src=$

Puisque nous avons que pour tous les entiers , les fonctions génératrices décalées en index satisfont ${\displaystyle z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\,, <semantics><mrow><mstyle><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mi>m</mi></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>g</mi><mrow><mi>n</mi><mo>−</mo><mi>m</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\,,}</annotation></semantics></math><img src=$ ${\displaystyle {\begin{aligned}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{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>U</mi><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mn>2</mn><mi>z</mi><mi>V</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><mi>U</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mn>1</mn></mtd></mtr><mtr><mtd><mi>V</mi><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mi>z</mi><mi>U</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><mi>V</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mi>z</mi><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mi>U</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>,</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}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{aligned}}}</annotation></semantics></math><img src=$ ${\displaystyle U(z)={\frac {1-z^{2}}{1-4z^{2}+z^{4}}}={\frac {1}{3-{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2+{\sqrt {3}} ight)z^{2}}}+{\frac {1}{3+{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2-{\sqrt {3}} ight)z^{2}}}. <semantics><mrow><mstyle><mi>U</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow><mrow><mn>1</mn><mo>−</mo><mn>4</mn><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><mo>+</mo><msup><mi>z</mi><mrow><mn>4</mn></mrow></msup></mrow></mfrac></mrow><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>3</mn><mo>−</mo><mrow><msqrt><mn>3</mn></msqrt></mrow></mrow></mfrac></mrow><mo>⋅</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mrow><mo>(</mo><mrow><mn>2</mn><mo>+</mo><mrow><msqrt><mn>3</mn></msqrt></mrow></mrow><mo>)</mo></mrow><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mo>+</mo><mrow><mfrac><mn>1</mn><mrow><mn>3</mn><mo>+</mo><mrow><msqrt><mn>3</mn></msqrt></mrow></mrow></mfrac></mrow><mo>⋅</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mrow><mo>(</mo><mrow><mn>2</mn><mo>−</mo><mrow><msqrt><mn>3</mn></msqrt></mrow></mrow><mo>)</mo></mrow><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mo>.</mo></mstyle></mrow><annotation>{\displaystyle U(z)={\frac {1-z^{2}}{1-4z^{2}+z^{4}}}={\frac {1}{3-{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2+{\sqrt {3}} ight)z^{2}}}+{\frac {1}{3+{\sqrt {3}}}}\cdot {\frac {1}{1-\left(2-{\sqrt {3}} ight)z^{2}}}.}</annotation></semantics></math><img src=$

Ainsi, en effectuant des simplifications algébriques sur la suite résultant des développements en fractions partielles secondes de la fonction génératrice de l'équation précédente, on trouve que et que ${\displaystyle U_{2n}=\left\lceil {\frac {\left(2+{\sqrt {3}} ight)^{n}}{3-{\sqrt {3}}}} ight ceil \,, <semantics><mrow><mstyle><msub><mi>U</mi><mrow><mn>2</mn><mi>n</mi></mrow></msub><mo>=</mo><mrow><mo>⌈</mo><mrow><mfrac><msup><mrow><mo>(</mo><mrow><mn>2</mn><mo>+</mo><mrow><msqrt><mn>3</mn></msqrt></mrow></mrow><mo>)</mo></mrow><mrow><mi>n</mi></mrow></msup><mrow><mn>3</mn><mo>−</mo><mrow><msqrt><mn>3</mn></msqrt></mrow></mrow></mfrac></mrow><mo>⌉</mo></mrow><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle U_{2n}=\left\lceil {\frac {\left(2+{\sqrt {3}} ight)^{n}}{3-{\sqrt {3}}}} ight ceil \,,}</annotation></semantics></math><img src=$

Convolution (produits de Cauchy)

Une convolution discrète des termes de deux séries de puissances formelles transforme un produit de fonctions génératrices en une fonction génératrice énumérant une somme convoluée des termes de la séquence originale (voir produit de Cauchy ).

Considérons que et sont des fonctions génératrices ordinaires. ${\displaystyle C(z)=A(z)B(z)\Leftrightarrow [z^{n}]C(z)=\sum _{k=0}^{n}{a_{k}b_{n-k <semantics><mrow><mstyle><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>UN</mi><mo>(</mo><mi>z</mi><mo>)</mo><mi>B</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>⇔</mo><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><msub><mi>un</mi><mrow><mi>k</mi></mrow></msub><msub><mi>b</mi><mrow><mi>n</mi><mo>−</mo><mi>k</mi></mrow></msub></mrow></mstyle></mrow><annotation>{\displaystyle C(z)=A(z)B(z)\Leftrightarrow [z^{n}]C(z)=\sum _{k=0}^{n}{a_{k}b_{n-k}}}</annotation></semantics></math><img src=$
Considérons que et sont des fonctions génératrices exponentielles. ${\displaystyle C(z)=A(z)B(z)\Leftrightarrow \left[{\frac {z^{n}}{n!}} ight]C(z)=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}b_{n-k <semantics><mrow><mstyle><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>UN</mi><mo>(</mo><mi>z</mi><mo>)</mo><mi>B</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>⇔</mo><mrow><mo>[</mo><mrow><mfrac><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow><mo>]</mo></mrow><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>n</mi><mi>k</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msub><mi>un</mi><mrow><mi>k</mi></mrow></msub><msub><mi>b</mi><mrow><mi>n</mi><mo>−</mo><mi>k</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle C(z)=A(z)B(z)\Leftrightarrow \left[{\frac {z^{n}}{n!}} ight]C(z)=\sum _{k=0}^{n}{\binom {n}{k}}a_{k}b_{n-k}}</annotation></semantics></math><img src=$
Considérons la séquence triplement convoluée résultant du produit de trois fonctions génératrices ordinaires ${\displaystyle C(z)=F(z)G(z)H(z)\Leftrightarrow [z^{n}]C(z)=\sum _{j+k+l=n}f_{j}g_{k}h_{l <semantics><mrow><mstyle><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo><mi>H</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>⇔</mo><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munder><mo>∑</mo><mrow><mi>j</mi><mo>+</mo><mi>k</mi><mo>+</mo><mi>l</mi><mo>=</mo><mi>n</mi></mrow></munder><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><msub><mi>g</mi><mrow><mi>k</mi></mrow></msub><msub><mi>h</mi><mrow><mi>l</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle C(z)=F(z)G(z)H(z)\Leftrightarrow [z^{n}]C(z)=\sum _{j+k+l=n}f_{j}g_{k}h_{l}}</annotation></semantics></math><img src=$
Considérons la séquence triplement convoluée résultant du produit de trois fonctions génératrices exponentielles ${\displaystyle C(z)=F(z)G(z)H(z)\Leftrightarrow \left[{\frac {z^{n}}{n!}} ight]C(z)=\sum _{j+k+l=n}{\frac {n!}{j!k!l!}}f_{j}g_{k}h_{l <semantics><mrow><mstyle><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo><mi>H</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>⇔</mo><mrow><mo>[</mo><mrow><mfrac><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mrow><mi>n</mi><mo>!</mo></mrow></mfrac></mrow><mo>]</mo></mrow><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munder><mo>∑</mo><mrow><mi>j</mi><mo>+</mo><mi>k</mi><mo>+</mo><mi>l</mi><mo>=</mo><mi>n</mi></mrow></munder><mrow><mfrac><mrow><mi>n</mi><mo>!</mo></mrow><mrow><mi>j</mi><mo>!</mo><mi>k</mi><mo>!</mo><mi>l</mi><mo>!</mo></mrow></mfrac></mrow><msub><mi>f</mi><mrow><mi>j</mi></mrow></msub><msub><mi>g</mi><mrow><mi>k</mi></mrow></msub><msub><mi>h</mi><mrow><mi>l</mi></mrow></msub></mstyle></mrow><annotation>{\displaystyle C(z)=F(z)G(z)H(z)\Leftrightarrow \left[{\frac {z^{n}}{n!}} ight]C(z)=\sum _{j+k+l=n}{\frac {n!}{j!k!l!}}f_{j}g_{k}h_{l}}</annotation></semantics></math><img src=$
Considérons la convolution (voir l'exemple ci-dessous pour une application). ${\displaystyle C(z)=G(z)^{m}\Leftrightarrow [z^{n}]C(z)=\sum _{k_{1}+k_{2}+\cdots +k_{m}=n}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m <semantics><mrow><mstyle><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>G</mi><mo>(</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>m</mi></mrow></msup><mo>⇔</mo><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munder><mo>∑</mo><mrow><msub><mi>k</mi><mrow><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>k</mi><mrow><mn>2</mn></mrow></msub><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>k</mi><mrow><mi>m</mi></mrow></msub><mo>=</mo><mi>n</mi></mrow></munder><msub><mi>g</mi><mrow><msub><mi>k</mi><mrow><mn>1</mn></mrow></msub></mrow></msub><msub><mi>g</mi><mrow><msub><mi>k</mi><mrow><mn>2</mn></mrow></msub></mrow></msub><mo>⋯</mo><msub><mi>g</mi><mrow><msub><mi>k</mi><mrow><mi>m</mi></mrow></msub></mrow></msub></mstyle></mrow><annotation>{\displaystyle C(z)=G(z)^{m}\Leftrightarrow [z^{n}]C(z)=\sum _{k_{1}+k_{2}+\cdots +k_{m}=n}g_{k_{1}}g_{k_{2}}\cdots g_{k_{m}}}</annotation></semantics></math><img src=$

La multiplication des fonctions génératrices, ou la convolution de leurs séquences sous-jacentes, peut correspondre à une notion d'événements indépendants dans certains contextes de dénombrement et de probabilité. Par exemple, si l'on adopte la convention de notation selon laquelle la fonction génératrice des probabilités ( FGP ) d'une variable aléatoire , alors on peut montrer que pour toutes variables aléatoires ${\displaystyle G_{X+Y}(z)=G_{X}(z)G_{Y}(z)\,, <semantics><mrow><mstyle><msub><mi>G</mi><mrow><mi>X</mi><mo>+</mo><mi>Y</mi></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><msub><mi>G</mi><mrow><mi>X</mi></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><msub><mi>G</mi><mrow><mi>Y</mi></mrow></msub><mo>(</mo><mi>z</mi><mo>)</mo><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle G_{X+Y}(z)=G_{X}(z)G_{Y}(z)\,,}</annotation></semantics></math><img src=$

Exemple : Le problème du change de monnaie

Le nombre de façons de payer centimes en pièces de monnaie de valeurs comprises dans l'ensemble ${\displaystyle {\frac {1}{1-z}}{\frac {1}{1-z^{5}}}{\frac {1}{1-z^{10}}}{\frac {1}{1-z^{25}}}{\frac {1}{1-z^{50}}}\,. </span referrerpolicy=$ Lorsque l'on fait également une distinction en fonction de l'ordre dans lequel les pièces sont présentées (par exemple, un penny puis un nickel est différent d'un nickel puis un penny), la fonction génératrice ordinaire est ${\displaystyle {\frac {1}{1-z-z^{5}-z^{10}-z^{25}-z^{50}}}\,. <semantics><mrow><mstyle><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mi>z</mi><mo>−</mo><msup><mi>z</mi><mrow><mn>5</mn></mrow></msup><mo>−</mo><msup><mi>z</mi><mrow><mn>10</mn></mrow></msup><mo>−</mo><msup><mi>z</mi><mrow><mn>25</mn></mrow></msup><mo>−</mo><msup><mi>z</mi><mrow><mn>50</mn></mrow></msup></mrow></mfrac></mrow><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\frac {1}{1-z-z^{5}-z^{10}-z^{25}-z^{50}}}\,.}</annotation></semantics></math><img src=$

Si nous autorisons le paiement des ${\displaystyle \prod _{n=1}^{\infty }\left(1-z^{n} ight)^{-1}\,. <semantics><mrow><mstyle><munderover><mo>∏</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msup><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mrow><mo>)</mo></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msup><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \prod _{n=1}^{\infty }\left(1-z^{n} ight)^{-1}\,.}</annotation></semantics></math><img src=$ ${\displaystyle {\frac {1}{1-\sum _{n=1}^{\infty }z^{n}}}={\frac {1-z}{1-2z}}\,. <semantics><mrow><mstyle><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mrow></mfrac></mrow><mo>=</mo><mrow><mfrac><mrow><mn>1</mn><mo>−</mo><mi>z</mi></mrow><mrow><mn>1</mn><mo>−</mo><mn>2</mn><mi>z</mi></mrow></mfrac></mrow><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\frac {1}{1-\sum _{n=1}^{\infty }z^{n}}}={\frac {1-z}{1-2z}}\,.}</annotation></semantics></math><img src=$

Exemple : Fonction génératrice pour les nombres catalans

Un exemple où les convolutions de fonctions génératrices sont utiles nous permet de déterminer une fonction explicite spécifique représentant la fonction génératrice ordinaire des nombres catalans , . En particulier, cette suite a l'interprétation combinatoire suivante : elle correspond au nombre de façons d'insérer des parenthèses dans le produit de sorte que l'ordre de multiplication soit complètement spécifié. Par exemple, ce qui correspond aux deux expressions et . Il s'ensuit que la suite satisfait une relation de récurrence donnée par… ${\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}\,,\quad n\geq 0\,, <semantics><mrow><mstyle><msub><mi>C</mi><mrow><mi>n</mi></mrow></msub><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></munderover><msub><mi>C</mi><mrow><mi>k</mi></mrow></msub><msub><mi>C</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn><mo>−</mo><mi>k</mi></mrow></msub><mo>+</mo><msub><mi>δ</mi><mrow><mi>n</mi><mo>,</mo><mn>0</mn></mrow></msub><mo>=</mo><msub><mi>C</mi><mrow><mn>0</mn></mrow></msub><msub><mi>C</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>+</mo><msub><mi>C</mi><mrow><mn>1</mn></mrow></msub><msub><mi>C</mi><mrow><mi>n</mi><mo>−</mo><mn>2</mn></mrow></msub><mo>+</mo><mo>⋯</mo><mo>+</mo><msub><mi>C</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msub><msub><mi>C</mi><mrow><mn>0</mn></mrow></msub><mo>+</mo><msub><mi>δ</mi><mrow><mi>n</mi><mo>,</mo><mn>0</mn></mrow></msub><mspace></mspace><mo>,</mo><mspace></mspace><mi>n</mi><mo>≥</mo><mn>0</mn><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\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}\,,\quad n\geq 0\,,}</annotation></semantics></math><img src=$ ${\displaystyle C(z)=z\cdot C(z)^{2}+1\,. <semantics><mrow><mstyle><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>z</mi><mo>⋅</mo><mi>C</mi><mo>(</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup><mo>+</mo><mn>1</mn><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle C(z)=z\cdot C(z)^{2}+1\,.}</annotation></semantics></math><img src=$

Puisque , nous obtenons alors une formule pour cette fonction génératrice donnée par ${\displaystyle C(z)={\frac {1-{\sqrt {1-4z}}}{2z}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}z^{n}\,. <semantics><mrow><mstyle><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mrow><mn>1</mn><mo>−</mo><mrow><msqrt><mn>1</mn><mo>−</mo><mn>4</mn><mi>z</mi></msqrt></mrow></mrow><mrow><mn>2</mn><mi>z</mi></mrow></mfrac></mrow><mo>=</mo><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><mn>1</mn><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow></mfrac></mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mn>2</mn><mi>n</mi></mrow><mi>n</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle C(z)={\frac {1-{\sqrt {1-4z}}}{2z}}=\sum _{n=0}^{\infty }{\frac {1}{n+1}}{\binom {2n}{n}}z^{n}\,.}</annotation></semantics></math><img src=$

Notez que la première équation définissant implicitement ci-dessus implique que ${\displaystyle C(z)={\frac {1}{1-z\cdot C(z)}}\,, <semantics><mrow><mstyle><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><mi>z</mi><mo>⋅</mo><mi>C</mi><mo>(</mo><mi>z</mi><mo>)</mo></mrow></mfrac></mrow><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle C(z)={\frac {1}{1-z\cdot C(z)}}\,,}</annotation></semantics></math><img src=$

Exemple : Arbres couvrants d'éventails et convolutions de convolutions

Un éventail d'ordre avec connectées selon les règles suivantes : le sommet 0 est connecté par une seule arête à chacun des n autres sommets, et le sommet 1 est connecté par une seule arête à chacun des ${\displaystyle k </span referrerpolicy=$ Pour tout , chaque sommet est relié par une seule arête au sommet suivant Il existe un éventail d'ordre un, trois éventails d'ordre deux, huit éventails d'ordre trois, et ainsi de suite. Un arbre couvrant est un sous-graphe d'un graphe qui contient tous les sommets d'origine et suffisamment d'arêtes pour être connexe, sans toutefois contenir de cycle. On cherche à déterminer le nombre d'arbres couvrants d'un éventail d'ordre

À titre d'observation, on peut aborder la question en comptant le nombre de façons de joindre des ensembles de sommets adjacents. Par exemple, lorsque , on a , ce qui est une somme sur les / (1 − z ) ² pour Plus généralement, on peut écrire une formule pour cette suite comme $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}}\,, f_{n} = \sum_{m > 0} \sum_{\frac{k_{1} + k_{2} + \dots + k_{m} = n}{k_{1}, k_{2}, \dots, k_{m} > 0}} g_{k_{1}} g_{k_{2}} \dots g_{k_{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}}\,, d'où l'on constate que la fonction génératrice ordinaire de cette suite est donnée par la somme suivante de convolutions : ${\displaystyle F(z)=G(z)+G(z)^{2}+G(z)^{3}+\cdots ={\frac {G(z)}{1-G(z)}}={\frac {z}{(1-z)^{2}-z}}={\frac {z}{1-3z+z^{2}}}\,, <semantics><mrow><mstyle><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>+</mo><mi>G</mi><mo>(</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup><mo>+</mo><mi>G</mi><mo>(</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>3</mn></mrow></msup><mo>+</mo><mo>⋯</mo><mo>=</mo><mrow><mfrac><mrow><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo></mrow><mrow><mn>1</mn><mo>−</mo><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo></mrow></mfrac></mrow><mo>=</mo><mrow><mfrac><mi>z</mi><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup><mo>−</mo><mi>z</mi></mrow></mfrac></mrow><mo>=</mo><mrow><mfrac><mi>z</mi><mrow><mn>1</mn><mo>−</mo><mn>3</mn><mi>z</mi><mo>+</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle F(z)=G(z)+G(z)^{2}+G(z)^{3}+\cdots ={\frac {G(z)}{1-G(z)}}={\frac {z}{(1-z)^{2}-z}}={\frac {z}{1-3z+z^{2}}}\,,}</annotation></semantics></math><img src=$

Fonctions génératrices implicites et formule d'inversion de Lagrange

On rencontre souvent des fonctions génératrices définies par une équation fonctionnelle, plutôt que par une définition explicite. Par exemple, la fonction génératrice du nombre d'arbres binaires à nœuds (feuilles comprises) satisfait :

${\displaystyle T(z)=z\left(1+T(z)^{2} ight) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>z</mi><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><mi>T</mi><mo>(</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle T(z)=z\left(1+T(z)^{2} ight)}</annotation></semantics></math><img src=$

Le théorème d'inversion de Lagrange est un outil utilisé pour évaluer explicitement les solutions de telles équations.

Formule d'inversion de Lagrange — Soit ${ extstyle \phi (z)\in C[[z]] <semantics><mrow><mstyle><mi>ϕ</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>∈</mo><mi>C</mi><mo>[</mo><mo>[</mo><mi>z</mi><mo>]</mo><mo>]</mo></mstyle></mrow><annotation>{ extstyle \phi (z)\in C[[z]]}</annotation></semantics></math><img src=$ ${\displaystyle T(z)=z\phi (T(z)) <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mi>z</mi><mi>ϕ</mi><mo>(</mo><mi>T</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>)</mo></mstyle></mrow><annotation>{\displaystyle T(z)=z\phi (T(z))}</annotation></semantics></math><img src=$ ${ extstyle T(z)\in C[[z]] <semantics><mrow><mstyle><mi>T</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>∈</mo><mi>C</mi><mo>[</mo><mo>[</mo><mi>z</mi><mo>]</mo><mo>]</mo></mstyle></mrow><annotation>{ extstyle T(z)\in C[[z]]}</annotation></semantics></math><img src=$

${\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(\phi (z))^{n <semantics><mrow><mstyle><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo><mi>T</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>]</mo><mrow><mfrac><mn>1</mn><mi>n</mi></mfrac></mrow><mo>(</mo><mi>ϕ</mi><mo>(</mo><mi>z</mi><mo>)</mo><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(\phi (z))^{n}}</annotation></semantics></math><img src=$

où la notation ${\displaystyle [z^{n}]F(z) <semantics><mrow><mstyle><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle [z^{n}]F(z)}</annotation></semantics></math><img src=$ ${\displaystyle z^{n <semantics><mrow><mstyle><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle z^{n}}</annotation></semantics></math><img src=$ ${\displaystyle F(z) <semantics><mrow><mstyle><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo></mstyle></mrow><annotation>{\displaystyle F(z)}</annotation></semantics></math><img src=$

L'application du théorème ci-dessus à notre équation fonctionnelle donne (avec ${ extstyle \phi (z)=1+z^{2 <semantics><mrow><mstyle><mi>ϕ</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mn>1</mn><mo>+</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mstyle></mrow><annotation>{ extstyle \phi (z)=1+z^{2}}</annotation></semantics></math><img src=$

${\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n <semantics><mrow><mstyle><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>]</mo><mi>T</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>]</mo><mrow><mfrac><mn>1</mn><mi>n</mi></mfrac></mrow><mo>(</mo><mn>1</mn><mo>+</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup></mstyle></mrow><annotation>{\displaystyle [z^{n}]T(z)=[z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}}</annotation></semantics></math><img src=$

En utilisant le développement du binôme , pour pair ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle 0 <semantics><mrow><mstyle><mn>0</mn></mstyle></mrow><annotation>{\displaystyle 0}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$

${\displaystyle [z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}={\frac {1}{n}}{\dbinom {n}{\frac {n+1}{2 <semantics><mrow><mstyle><mo>[</mo><msup><mi>z</mi><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>]</mo><mrow><mfrac><mn>1</mn><mi>n</mi></mfrac></mrow><mo>(</mo><mn>1</mn><mo>+</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mn>1</mn><mi>n</mi></mfrac></mrow><mrow><mstyle><mrow><mrow><mo>(</mo></mrow><mfrac><mi>n</mi><mfrac><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mn>2</mn></mfrac></mfrac><mrow><mo>)</mo></mrow></mrow></mstyle></mrow></mstyle></mrow><annotation>{\displaystyle [z^{n-1}]{\frac {1}{n}}(1+z^{2})^{n}={\frac {1}{n}}{\dbinom {n}{\frac {n+1}{2}}}}</annotation></semantics></math><img src=$

L'expression devient beaucoup plus élégante si l'on laisse ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ${\displaystyle n <semantics><mrow><mstyle><mi>n</mi></mstyle></mrow><annotation>{\displaystyle n}</annotation></semantics></math><img src=$ ^numéro catalan.

Introduction d'un paramètre gratuit (méthode du charlatanisme)

Parfois, la somme est complexe et son calcul n'est pas toujours aisé. La méthode du « paramètre libre » est une autre méthode (qualifiée de « solution de facilité » par H. Wilf) permettant d'évaluer ces sommes.

Les deux méthodes décrites jusqu'ici utilisent un paramètre « libre » et traiter comme un coefficient de , inverser l'ordre des sommations sur , et tenter de calculer la somme interne.

Par exemple, si nous voulons calculer ${\displaystyle s_{n}=\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\,,\quad m,n\in \mathbb {N} _{0}\,, <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mi>k</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn>2</mn><mi>k</mi></mrow></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mn>2</mn><mi>k</mi></mrow><mi>k</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><mfrac><mrow><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>k</mi></mrow></msup></mrow><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></mfrac></mrow></mrow><mspace></mspace><mo>,</mo><mspace></mspace><mi>m</mi><mo>,</mo><mi>n</mi><mo>∈</mo><msub><mrow><mi>N</mi></mrow><mrow><mn>0</mn></mrow></msub><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle s_{n}=\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}}\,,\quad m,n\in \mathbb {N} _{0}\,,}</annotation></semantics></math><img src=$ ${\displaystyle F(z)=\sum _{n=0}^{\infty }{\left(\sum _{k=0}^{\infty }{{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}} ight)}z^{n}\,. </span referrerpolicy=$

L'interchange de la sommation (« huile de serpent ») donne ${\displaystyle F(z)=\sum _{k=0}^{\infty }{{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-k}}\sum _{n=0}^{\infty }{{\binom {n+k}{m+2k}}z^{n+k}}\,. <semantics><mrow><mstyle><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mn>2</mn><mi>k</mi></mrow><mi>k</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><mfrac><mrow><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>k</mi></mrow></msup></mrow><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></mfrac></mrow><msup><mi>z</mi><mrow><mo>−</mo><mi>k</mi></mrow></msup></mrow><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mi>k</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn>2</mn><mi>k</mi></mrow></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>z</mi><mrow><mi>n</mi><mo>+</mo><mi>k</mi></mrow></msup></mrow><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle F(z)=\sum _{k=0}^{\infty }{{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-k}}\sum _{n=0}^{\infty }{{\binom {n+k}{m+2k}}z^{n+k}}\,.}</annotation></semantics></math><img src=$

La somme intérieure est maintenant . ${\displaystyle {\begin{aligned}F(z)&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-z}{(1-z)^{2}}} ight)^{k}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{C_{k}\left({\frac {-z}{(1-z)^{2}}} ight)^{k}}&{ ext{where }}C_{k}=k{ ext{th Catalan number}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}{\frac {1-{\sqrt {1+{\frac {4z}{(1-z)^{2}}}}}}{\frac {-2z}{(1-z)^{2}}}}\\[4px]&={\frac {-z^{m-1}}{2(1-z)^{m-1}}}\left(1-{\frac {1+z}{1-z}} ight)\\[4px]&={\frac {z^{m}}{(1-z)^{m}}}=z{\frac {z^{m-1}}{(1-z)^{m}}}\,.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></msup></mrow></mfrac></mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mfrac><mn>1</mn><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></mfrac></mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mn>2</mn><mi>k</mi></mrow><mi>k</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mrow><mo>(</mo><mrow><mfrac><mrow><mo>−</mo><mi>z</mi></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mo>)</mo></mrow><mrow><mi>k</mi></mrow></msup></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></msup></mrow></mfrac></mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><msub><mi>C</mi><mrow><mi>k</mi></mrow></msub><msup><mrow><mo>(</mo><mrow><mfrac><mrow><mo>−</mo><mi>z</mi></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mo>)</mo></mrow><mrow><mi>k</mi></mrow></msup></mrow></mtd><mtd><mrow><mtext>où </mtext></mrow><msub><mi>C</mi><mrow><mi>k</mi></mrow></msub><mo>=</mo><mi>k</mi><mrow><mtext>numéro catalan</mtext></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></msup></mrow></mfrac></mrow><mrow><mfrac><mrow><mn>1</mn><mo>−</mo><mrow><msqrt><mn>1</mn><mo>+</mo><mrow><mfrac><mrow><mn>4</mn><mi>z</mi></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow></msqrt></mrow></mrow><mfrac><mrow><mo>−</mo><mn>2</mn><mi>z</mi></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mfrac></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><mrow><mo>−</mo><msup><mi>z</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><mrow><mn>2</mn><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow></mfrac></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><mrow><mfrac><mrow><mn>1</mn><mo>+</mo><mi>z</mi></mrow><mrow><mn>1</mn><mo>−</mo><mi>z</mi></mrow></mfrac></mrow></mrow><mo>)</mo></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>m</mi></mrow></msup></mrow></mfrac></mrow><mo>=</mo><mi>z</mi><mrow><mfrac><msup><mi>z</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msup><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>m</mi></mrow></msup></mrow></mfrac></mrow><mspace></mspace><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}F(z)&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-z}{(1-z)^{2}}} ight)^{k}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}\sum _{k=0}^{\infty }{C_{k}\left({\frac {-z}{(1-z)^{2}}} ight)^{k}}&{ ext{where }}C_{k}=k{ ext{th Catalan number}}\\[4px]&={\frac {z^{m}}{(1-z)^{m+1}}}{\frac {1-{\sqrt {1+{\frac {4z}{(1-z)^{2}}}}}}{\frac {-2z}{(1-z)^{2}}}}\\[4px]&={\frac {-z^{m-1}}{2(1-z)^{m-1}}}\left(1-{\frac {1+z}{1-z}} ight)\\[4px]&={\frac {z^{m}}{(1-z)^{m}}}=z{\frac {z^{m-1}}{(1-z)^{m}}}\,.\end{aligned}}}</annotation></semantics></math><img src=$

Nous obtenons alors ${\displaystyle s_{n}={\begin{cases}\displaystyle {\binom {n-1}{m-1}}&{ ext{for }}m\geq 1\,,\\{}[n=0]&{ ext{for }}m=0\,.\end{cases <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><mo>=</mo><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mstyle><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></mfrac><mrow><mo>)</mo></mrow></mrow></mrow></mstyle></mtd><mtd><mrow><mtext>pour </mtext></mrow><mi>m</mi><mo>≥</mo><mn>1</mn><mspace></mspace><mo>,</mo></mtd></mtr><mtr><mtd><mrow></mrow><mo>[</mo><mi>n</mi><mo>=</mo><mn>0</mn><mo>]</mo></mtd><mtd><mrow><mtext>pour </mtext></mrow><mi>m</mi><mo>=</mo><mn>0</mn><mspace></mspace><mo>.</mo></mtd></mtr></mtable><mo></mo></mrow></mrow></mstyle></mrow><annotation>{\displaystyle s_{n}={\begin{cases}\displaystyle {\binom {n-1}{m-1}}&{ ext{for }}m\geq 1\,,\\{}[n=0]&{ ext{for }}m=0\,.\end{cases}}}</annotation></semantics></math><img src=$

Il est instructif d'utiliser à nouveau la même méthode pour la somme, mais en prenant cette fois . Nous posons donc ${\displaystyle G(z)=\sum _{m=0}^{\infty }\left(\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}} ight)z^{m}\,. <semantics><mrow><mstyle><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mo>(</mo><mrow><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mi>k</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn>2</mn><mi>k</mi></mrow></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mn>2</mn><mi>k</mi></mrow><mi>k</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><mfrac><mrow><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>k</mi></mrow></msup></mrow><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></mfrac></mrow></mrow><mo>)</mo></mrow><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle G(z)=\sum _{m=0}^{\infty }\left(\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}} ight)z^{m}\,.}</annotation></semantics></math><img src=$

L'interchange de la sommation (« huile de serpent ») donne ${\displaystyle G(z)=\sum _{k=0}^{\infty }{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-2k}\sum _{m=0}^{\infty }{\binom {n+k}{m+2k}}z^{m+2k}\,. <semantics><mrow><mstyle><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mn>2</mn><mi>k</mi></mrow><mi>k</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><mfrac><mrow><mo>(</mo><mo>−</mo><mn>1</mn><msup><mo>)</mo><mrow><mi>k</mi></mrow></msup></mrow><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></mfrac></mrow><msup><mi>z</mi><mrow><mo>−</mo><mn>2</mn><mi>k</mi></mrow></msup><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mi>k</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn>2</mn><mi>k</mi></mrow></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>z</mi><mrow><mi>m</mi><mo>+</mo><mn>2</mn><mi>k</mi></mrow></msup><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle G(z)=\sum _{k=0}^{\infty }{\binom {2k}{k}}{\frac {(-1)^{k}}{k+1}}z^{-2k}\sum _{m=0}^{\infty }{\binom {n+k}{m+2k}}z^{m+2k}\,.}</annotation></semantics></math><img src=$

La somme intérieure est maintenant . ${\displaystyle {\begin{aligned}G(z)&=(1+z)^{n}\sum _{k=0}^{\infty }{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-(1+z)}{z^{2}}} ight)^{k}\\[4px]&=(1+z)^{n}\sum _{k=0}^{\infty }C_{k}\,\left({\frac {-(1+z)}{z^{2}}} ight)^{k}&{ ext{where }}C_{k}=k{ ext{th Catalan number}}\\[4px]&=(1+z)^{n}\,{\frac {1-{\sqrt {1+{\frac {4(1+z)}{z^{2}}}}}}{\frac {-2(1+z)}{z^{2}}}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z{\sqrt {z^{2}+4+4z}}}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z(z+2)}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {-2z}{-2(1+z)}}=z(1+z)^{n-1}\,.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>G</mi><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mfrac><mn>1</mn><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow></mfrac></mrow><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mn>2</mn><mi>k</mi></mrow><mi>k</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mrow><mo>(</mo><mrow><mfrac><mrow><mo>−</mo><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><mo>)</mo></mrow><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mfrac></mrow><mo>)</mo></mrow><mrow><mi>k</mi></mrow></msup></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>C</mi><mrow><mi>k</mi></mrow></msub><mspace></mspace><msup><mrow><mo>(</mo><mrow><mfrac><mrow><mo>−</mo><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><mo>)</mo></mrow><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mfrac></mrow><mo>)</mo></mrow><mrow><mi>k</mi></mrow></msup></mtd><mtd><mrow><mtext>où </mtext></mrow><msub><mi>C</mi><mrow><mi>k</mi></mrow></msub><mo>=</mo><mi>k</mi><mrow><mtext>numéro catalan</mtext></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup><mspace></mspace><mrow><mfrac><mrow><mn>1</mn><mo>−</mo><mrow><msqrt><mn>1</mn><mo>+</mo><mrow><mfrac><mrow><mn>4</mn><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><mo>)</mo></mrow><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mfrac></mrow></msqrt></mrow></mrow><mfrac><mrow><mo>−</mo><mn>2</mn><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><mo>)</mo></mrow><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mfrac></mfrac></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup><mspace></mspace><mrow><mfrac><mrow><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><mo>−</mo><mi>z</mi><mrow><msqrt><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><mo>+</mo><mn>4</mn><mo>+</mo><mn>4</mn><mi>z</mi></msqrt></mrow></mrow><mrow><mo>−</mo><mn>2</mn><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><mo>)</mo></mrow></mfrac></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup><mspace></mspace><mrow><mfrac><mrow><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><mo>−</mo><mi>z</mi><mo>(</mo><mi>z</mi><mo>+</mo><mn>2</mn><mo>)</mo></mrow><mrow><mo>−</mo><mn>2</mn><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><mo>)</mo></mrow></mfrac></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>n</mi></mrow></msup><mspace></mspace><mrow><mfrac><mrow><mo>−</mo><mn>2</mn><mi>z</mi></mrow><mrow><mo>−</mo><mn>2</mn><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><mo>)</mo></mrow></mfrac></mrow><mo>=</mo><mi>z</mi><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msup><mspace></mspace><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}G(z)&=(1+z)^{n}\sum _{k=0}^{\infty }{\frac {1}{k+1}}{\binom {2k}{k}}\left({\frac {-(1+z)}{z^{2}}} ight)^{k}\\[4px]&=(1+z)^{n}\sum _{k=0}^{\infty }C_{k}\,\left({\frac {-(1+z)}{z^{2}}} ight)^{k}&{ ext{where }}C_{k}=k{ ext{th Catalan number}}\\[4px]&=(1+z)^{n}\,{\frac {1-{\sqrt {1+{\frac {4(1+z)}{z^{2}}}}}}{\frac {-2(1+z)}{z^{2}}}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z{\sqrt {z^{2}+4+4z}}}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {z^{2}-z(z+2)}{-2(1+z)}}\\[4px]&=(1+z)^{n}\,{\frac {-2z}{-2(1+z)}}=z(1+z)^{n-1}\,.\end{aligned}}}</annotation></semantics></math><img src=$

Ainsi, nous obtenons ${\displaystyle s_{n}=\left[z^{m} ight]z(1+z)^{n-1}=\left[z^{m-1} ight](1+z)^{n-1}={\binom {n-1}{m-1}}\,, <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><mo>=</mo><mrow><mo>[</mo><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup><mo>]</mo></mrow><mi>z</mi><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>=</mo><mrow><mo>[</mo><msup><mi>z</mi><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>]</mo></mrow><mo>(</mo><mn>1</mn><mo>+</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>=</mo><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow><mrow><mi>m</mi><mo>−</mo><mn>1</mn></mrow></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle s_{n}=\left[z^{m} ight]z(1+z)^{n-1}=\left[z^{m-1} ight](1+z)^{n-1}={\binom {n-1}{m-1}}\,,}</annotation></semantics></math><img src=$

Les fonctions génératrices prouvent les congruences

On dit que deux fonctions génératrices (séries entières) sont congruentes modulo , si leurs coefficients sont congruents modulo , c'est -à-dire pour tous les entiers est un entier ici ; il peut très bien être à valeurs polynomiales en une indéterminée , est une fonction rationnelle de Par exemple, on peut démontrer que les nombres d'Euler , ${\displaystyle \langle E_{n} angle =\langle 1,1,5,61,1385,\ldots angle \longmapsto \langle 1,1,2,1,2,1,2,\ldots angle {\pmod {3}}\,, <semantics><mrow><mstyle><mo>⟨</mo><msub><mi>E</mi><mrow><mi>n</mi></mrow></msub><mo>⟩</mo><mo>=</mo><mo>⟨</mo><mn>1</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>5</mn><mo>,</mo><mn>61</mn><mo>,</mo><mn>1385</mn><mo>,</mo><mo>…</mo><mo>⟩</mo><mo>⟼</mo><mo>⟨</mo><mn>1</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>…</mo><mo>⟩</mo><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>3</mn><mo>)</mo></mrow><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle \langle E_{n} angle =\langle 1,1,5,61,1385,\ldots angle \longmapsto \langle 1,1,2,1,2,1,2,\ldots angle {\pmod {3}}\,,}</annotation></semantics></math><img src=$ ${\displaystyle \sum _{n=0}^{\infty }E_{n}z^{n}={\frac {1-z^{2}}{1+z^{2}}}{\pmod {3}}\,. <semantics><mrow><mstyle><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><msub><mi>E</mi><mrow><mi>n</mi></mrow></msub><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup><mo>=</mo><mrow><mfrac><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow><mrow><mn>1</mn><mo>+</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>3</mn><mo>)</mo></mrow><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle \sum _{n=0}^{\infty }E_{n}z^{n}={\frac {1-z^{2}}{1+z^{2}}}{\pmod {3}}\,.}</annotation></semantics></math><img src=$

Une méthode utile pour obtenir des congruences pour les suites énumérées par des fonctions génératrices particulières modulo des entiers quelconques (c'est-à-dire, pas seulement des puissances de nombres premiers ) est présentée dans la section sur les représentations en fractions continues des fonctions génératrices ordinaires (même non convergentes) par

Théorème : congruences des séries engendrées par le développement de fractions continues — Supposons que la fonction génératrice A ( z ) soit représentée par une fraction continue infinie de la forme ${\displaystyle A(z)={\cfrac {1}{1-c_{1}z-{\cfrac {p_{1}z^{2}}{1-c_{2}z-{\cfrac {p_{2}z^{2}}{1-c_{3}z-{\ddots <semantics><mrow><mstyle><mi>UN</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><mrow><mpadded><mrow></mrow></mpadded><mstyle><mrow><mn>1</mn></mrow></mstyle></mrow><mrow><mpadded><mrow></mrow></mpadded><mstyle><mrow><mn>1</mn><mo>−</mo><msub><mi>c</mi><mrow><mn>1</mn></mrow></msub><mi>z</mi><mo>−</mo><mrow><mfrac><mrow><mpadded><mrow></mrow></mpadded><mstyle><mrow><msub><mi>p</mi><mrow><mn>1</mn></mrow></msub><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow></mstyle></mrow><mrow><mpadded><mrow></mrow></mpadded><mstyle><mrow><mn>1</mn><mo>−</mo><msub><mi>c</mi><mrow><mn>2</mn></mrow></msub><mi>z</mi><mo>−</mo><mrow><mfrac><mrow><mpadded><mrow></mrow></mpadded><mstyle><mrow><msub><mi>p</mi><mrow><mn>2</mn></mrow></msub><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow></mstyle></mrow><mrow><mpadded><mrow></mrow></mpadded><mstyle><mrow><mn>1</mn><mo>−</mo><msub><mi>c</mi><mrow><mn>3</mn></mrow></msub><mi>z</mi><mo>−</mo><mrow><mo>⋱</mo></mrow></mrow></mstyle></mrow></mfrac></mrow></mrow></mstyle></mrow></mfrac></mrow></mrow></mstyle></mrow></mfrac></mrow></mstyle></mrow><annotation>{\displaystyle A(z)={\cfrac {1}{1-c_{1}z-{\cfrac {p_{1}z^{2}}{1-c_{2}z-{\cfrac {p_{2}z^{2}}{1-c_{3}z-{\ddots }}}}}}}}</annotation></semantics></math><img src=$ A _p ( z ) désigne la p ème convergente vers ce développement en fraction continue défini tel que a _n = [ z ⁿ ] A _p ( z ) pour tout 0 ≤ n < 2 p . Alors :

la fonction A _p ( z ) est rationnelle pour tout p ≥ 2 où l'on suppose que l'un des critères de divisibilité p | p ₁ , p ₁p ₂ , p ₁p ₂p ₃ est satisfait, c'est-à-dire p | p ₁p ₂ ⋯ p _k pour un certain k ≥ 1 ; et
si l'entier p divise le produit p ₁p ₂ ⋯ p _k , alors nous avons A ( z ) ≡ A _k ( z ) (mod p ) .

Les fonctions génératrices ont également d'autres applications dans la démonstration de congruences pour leurs coefficients. Nous citons les deux exemples spécifiques suivants, qui démontrent des congruences dans des cas particuliers pour les nombres de Stirling de première espèce et pour la fonction de partition et qui illustrent la polyvalence des fonctions génératrices dans la résolution de problèmes impliquant des suites d'entiers .

Les nombres de Stirling modulo les petits entiers

L' article principal sur les nombres de Stirling générés par les produits finis ${\displaystyle S_{n}(x):=\sum _{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}=x(x+1)(x+2)\cdots (x+n-1)\,,\quad n\geq 1\,, <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>:=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>n</mi></mtd></mtr><mtr><mtd><mi>k</mi></mtd></mtr></mtable><mo>]</mo></mrow></mrow><msup><mi>x</mi><mrow><mi>k</mi></mrow></msup><mo>=</mo><mi>x</mi><mo>(</mo><mi>x</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>(</mo><mi>x</mi><mo>+</mo><mn>2</mn><mo>)</mo><mo>⋯</mo><mo>(</mo><mi>x</mi><mo>+</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>)</mo><mspace></mspace><mo>,</mo><mspace></mspace><mi>n</mi><mo>≥</mo><mn>1</mn><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle S_{n}(x):=\sum _{k=0}^{n}{\begin{bmatrix}n\\k\end{bmatrix}}x^{k}=x(x+1)(x+2)\cdots (x+n-1)\,,\quad n\geq 1\,,}</annotation></semantics></math><img src=$

Cet article présente un aperçu des congruences de ces nombres, obtenues strictement à partir des propriétés de leur fonction génératrice, comme dans la section 4.6 de l'ouvrage de référence de Wilf, * Generatingfunctionology *. Nous reprenons l'argument principal et constatons que, lorsque le produit fini se réduit modulo 2, ces fonctions génératrices satisfont chacune à la condition suivante :

${\displaystyle S_{n}(x)=[x(x+1)]\cdot [x(x+1)]\cdots =x^{\left\lceil {\frac {n}{2}} ight ceil }(x+1)^{\left\lfloor {\frac {n}{2}} ight floor }\,, <semantics><mrow><mstyle><msub><mi>S</mi><mrow><mi>n</mi></mrow></msub><mo>(</mo><mi>x</mi><mo>)</mo><mo>=</mo><mo>[</mo><mi>x</mi><mo>(</mo><mi>x</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>]</mo><mo>⋅</mo><mo>[</mo><mi>x</mi><mo>(</mo><mi>x</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>]</mo><mo>⋯</mo><mo>=</mo><msup><mi>x</mi><mrow><mrow><mo>⌈</mo><mrow><mfrac><mi>n</mi><mn>2</mn></mfrac></mrow><mo>⌉</mo></mrow></mrow></msup><mo>(</mo><mi>x</mi><mo>+</mo><mn>1</mn><msup><mo>)</mo><mrow><mrow><mo>⌊</mo><mrow><mfrac><mi>n</mi><mn>2</mn></mfrac></mrow><mo>⌋</mo></mrow></mrow></msup><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle S_{n}(x)=[x(x+1)]\cdot [x(x+1)]\cdots =x^{\left\lceil {\frac {n}{2}} ight ceil }(x+1)^{\left\lfloor {\frac {n}{2}} ight floor }\,,}</annotation></semantics></math><img src=$

ce qui implique que la parité de ces nombres de Stirling correspond à celle du coefficient binomial

${\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}\equiv {\binom {\left\lfloor {\frac {n}{2}} ight floor }{k-\left\lceil {\frac {n}{2}} ight ceil }}{\pmod {2}}\,, <semantics><mrow><mstyle><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>n</mi></mtd></mtr><mtr><mtd><mi>k</mi></mtd></mtr></mtable><mo>]</mo></mrow></mrow><mo>≡</mo><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mo>⌊</mo><mrow><mfrac><mi>n</mi><mn>2</mn></mfrac></mrow><mo>⌋</mo></mrow><mrow><mi>k</mi><mo>−</mo><mrow><mo>⌈</mo><mrow><mfrac><mi>n</mi><mn>2</mn></mfrac></mrow><mo>⌉</mo></mrow></mrow></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>2</mn><mo>)</mo></mrow><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle {\begin{bmatrix}n\\k\end{bmatrix}}\equiv {\binom {\left\lfloor {\frac {n}{2}} ight floor }{k-\left\lceil {\frac {n}{2}} ight ceil }}{\pmod {2}}\,,}</annotation></semantics></math><img src=$

et montre par conséquent que ⁿ_k ] est pair chaque fois que n / 2 ⁠ ⌋ .

De même, on peut simplifier les produits des membres de droite définissant les fonctions génératrices du nombre de Stirling modulo 3 pour obtenir des expressions légèrement plus complexes, à condition que ${\displaystyle {\begin{aligned}{\begin{bmatrix}n\\m\end{bmatrix}}&\equiv [x^{m}]\left(x^{\left\lceil {\frac {n}{3}} ight ceil }(x+1)^{\left\lceil {\frac {n-1}{3}} ight ceil }(x+2)^{\left\lfloor {\frac {n}{3}} ight floor } ight)&&{\pmod {3}}\\&\equiv \sum _{k=0}^{m}{\begin{pmatrix}\left\lceil {\frac {n-1}{3}} ight ceil \\k\end{pmatrix}}{\begin{pmatrix}\left\lfloor {\frac {n}{3}} ight floor \\m-k-\left\lceil {\frac {n}{3}} ight ceil \end{pmatrix}} imes 2^{\left\lceil {\frac {n}{3}} ight ceil +\left\lfloor {\frac {n}{3}} ight floor -(m-k)}&&{\pmod {3}}\,.\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mrow><mrow><mo>[</mo><mtable><mtr><mtd><mi>n</mi></mtd></mtr><mtr><mtd><mi>m</mi></mtd></mtr></mtable><mo>]</mo></mrow></mrow></mtd><mtd><mi></mi><mo>≡</mo><mo>[</mo><msup><mi>x</mi><mrow><mi>m</mi></mrow></msup><mo>]</mo><mrow><mo>(</mo><mrow><msup><mi>x</mi><mrow><mrow><mo>⌈</mo><mrow><mfrac><mi>n</mi><mn>3</mn></mfrac></mrow><mo>⌉</mo></mrow></mrow></msup><mo>(</mo><mi>x</mi><mo>+</mo><mn>1</mn><msup><mo>)</mo><mrow><mrow><mo>⌈</mo><mrow><mfrac><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow><mn>3</mn></mfrac></mrow><mo>⌉</mo></mrow></mrow></msup><mo>(</mo><mi>x</mi><mo>+</mo><mn>2</mn><msup><mo>)</mo><mrow><mrow><mo>⌊</mo><mrow><mfrac><mi>n</mi><mn>3</mn></mfrac></mrow><mo>⌋</mo></mrow></mrow></msup></mrow><mo>)</mo></mrow></mtd><mtd></mtd><mtd><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>3</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>≡</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>m</mi></mrow></munderover><mrow><mrow><mo>(</mo><mtable><mtr><mtd><mrow><mo>⌈</mo><mrow><mfrac><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow><mn>3</mn></mfrac></mrow><mo>⌉</mo></mrow></mtd></mtr><mtr><mtd><mi>k</mi></mtd></mtr></mtable><mo>)</mo></mrow></mrow><mrow><mrow><mo>(</mo><mtable><mtr><mtd><mrow><mo>⌊</mo><mrow><mfrac><mi>n</mi><mn>3</mn></mfrac></mrow><mo>⌋</mo></mrow></mtd></mtr><mtr><mtd><mi>m</mi><mo>−</mo><mi>k</mi><mo>−</mo><mrow><mo>⌈</mo><mrow><mfrac><mi>n</mi><mn>3</mn></mfrac></mrow><mo>⌉</mo></mrow></mtd></mtr></mtable><mo>)</mo></mrow></mrow><mo>×</mo><msup><mn>2</mn><mrow><mrow><mo>⌈</mo><mrow><mfrac><mi>n</mi><mn>3</mn></mfrac></mrow><mo>⌉</mo></mrow><mo>+</mo><mrow><mo>⌊</mo><mrow><mfrac><mi>n</mi><mn>3</mn></mfrac></mrow><mo>⌋</mo></mrow><mo>−</mo><mo>(</mo><mi>m</mi><mo>−</mo><mi>k</mi><mo>)</mo></mrow></msup></mtd><mtd></mtd><mtd><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>3</mn><mo>)</mo></mrow><mspace></mspace><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}{\begin{bmatrix}n\\m\end{bmatrix}}&\equiv [x^{m}]\left(x^{\left\lceil {\frac {n}{3}} ight ceil }(x+1)^{\left\lceil {\frac {n-1}{3}} ight ceil }(x+2)^{\left\lfloor {\frac {n}{3}} ight floor } ight)&&{\pmod {3}}\\&\equiv \sum _{k=0}^{m}{\begin{pmatrix}\left\lceil {\frac {n-1}{3}} ight ceil \\k\end{pmatrix}}{\begin{pmatrix}\left\lfloor {\frac {n}{3}} ight floor \\m-k-\left\lceil {\frac {n}{3}} ight ceil \end{pmatrix}} imes 2^{\left\lceil {\frac {n}{3}} ight ceil +\left\lfloor {\frac {n}{3}} ight floor -(m-k)}&&{\pmod {3}}\,.\end{aligned}}}</annotation></semantics></math><img src=$

Congruences pour la fonction de partition

Dans cet exemple, nous utilisons certains outils des produits infinis dont les développements en série de puissances engendrent les développements de nombreuses fonctions spéciales et énumérons les fonctions de partition. En particulier, nous rappelons que la fonction de partition est engendrée par le produit réciproque infini symboles de Pochhammer, selon le cas) donné par ${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }p(n)z^{n}&={\frac {1}{\left(1-z ight)\left(1-z^{2} ight)\left(1-z^{3} ight)\cdots }}\\[4pt]&=1+z+2z^{2}+3z^{3}+5z^{4}+7z^{5}+11z^{6}+\cdots .\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><munderover><mo>∑</mo><mrow><mi>n</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mi>p</mi><mo>(</mo><mi>n</mi><mo>)</mo><msup><mi>z</mi><mrow><mi>n</mi></mrow></msup></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><mi>z</mi></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>3</mn></mrow></msup></mrow><mo>)</mo></mrow><mo>⋯</mo></mrow></mfrac></mrow></mtd></mtr><mtr><mtd></mtd><mtd><mi></mi><mo>=</mo><mn>1</mn><mo>+</mo><mi>z</mi><mo>+</mo><mn>2</mn><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup><mo>+</mo><mn>3</mn><msup><mi>z</mi><mrow><mn>3</mn></mrow></msup><mo>+</mo><mn>5</mn><msup><mi>z</mi><mrow><mn>4</mn></mrow></msup><mo>+</mo><mn>7</mn><msup><mi>z</mi><mrow><mn>5</mn></mrow></msup><mo>+</mo><mn>11</mn><msup><mi>z</mi><mrow><mn>6</mn></mrow></msup><mo>+</mo><mo>⋯</mo><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }p(n)z^{n}&={\frac {1}{\left(1-z ight)\left(1-z^{2} ight)\left(1-z^{3} ight)\cdots }}\\[4pt]&=1+z+2z^{2}+3z^{3}+5z^{4}+7z^{5}+11z^{6}+\cdots .\end{aligned}}}</annotation></semantics></math><img src=$

Cette fonction de partition satisfait de nombreuses propriétés de congruence connues , qui incluent notamment les résultats suivants, bien qu'il reste encore de nombreuses questions ouvertes sur les formes des congruences entières liées à la fonction : ${\displaystyle {\begin{aligned}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{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>p</mi><mo>(</mo><mn>5</mn><mi>m</mi><mo>+</mo><mn>4</mn><mo>)</mo></mtd><mtd><mi></mi><mo>≡</mo><mn>0</mn><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>5</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mi>p</mi><mo>(</mo><mn>7</mn><mi>m</mi><mo>+</mo><mn>5</mn><mo>)</mo></mtd><mtd><mi></mi><mo>≡</mo><mn>0</mn><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>7</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mi>p</mi><mo>(</mo><mn>11</mn><mi>m</mi><mo>+</mo><mn>6</mn><mo>)</mo></mtd><mtd><mi></mi><mo>≡</mo><mn>0</mn><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>11</mn><mo>)</mo></mrow></mtd></mtr><mtr><mtd><mi>p</mi><mo>(</mo><mn>25</mn><mi>m</mi><mo>+</mo><mn>24</mn><mo>)</mo></mtd><mtd><mi></mi><mo>≡</mo><mn>0</mn><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><msup><mn>5</mn><mrow><mn>2</mn></mrow></msup><mo>)</mo></mrow><mspace></mspace><mo>.</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}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{aligned}}}</annotation></semantics></math><img src=$

Nous montrons comment utiliser les fonctions génératrices et les manipulations de congruences pour les séries formelles afin de donner une preuve très élémentaire de la première de ces congruences énumérées ci-dessus.

Premièrement, nous observons que dans la fonction génératrice des coefficients binomiaux ${\displaystyle {\frac {1}{(1-z)^{5}}}=\sum _{i=0}^{\infty }{\binom {4+i}{4}}z^{i}\,, <semantics><mrow><mstyle><mrow><mfrac><mn>1</mn><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>5</mn></mrow></msup></mrow></mfrac></mrow><mo>=</mo><munderover><mo>∑</mo><mrow><mi>je</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mn>4</mn><mo>+</mo><mi>je</mi></mrow><mn>4</mn></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msup><mi>z</mi><mrow><mi>je</mi></mrow></msup><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle {\frac {1}{(1-z)^{5}}}=\sum _{i=0}^{\infty }{\binom {4+i}{4}}z^{i}\,,}</annotation></semantics></math><img src=$ ${\displaystyle {\frac {1}{(1-z)^{5}}}\equiv {\frac {1}{1-z^{5}}}{\pmod {5}}\,, <semantics><mrow><mstyle><mrow><mfrac><mn>1</mn><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>5</mn></mrow></msup></mrow></mfrac></mrow><mo>≡</mo><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>5</mn></mrow></msup></mrow></mfrac></mrow><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>5</mn><mo>)</mo></mrow><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle {\frac {1}{(1-z)^{5}}}\equiv {\frac {1}{1-z^{5}}}{\pmod {5}}\,,}</annotation></semantics></math><img src=$ ${\displaystyle {\frac {1-z^{5}}{(1-z)^{5}}}\equiv 1{\pmod {5}}\,. <semantics><mrow><mstyle><mrow><mfrac><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>5</mn></mrow></msup></mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>5</mn></mrow></msup></mrow></mfrac></mrow><mo>≡</mo><mn>1</mn><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>5</mn><mo>)</mo></mrow><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\frac {1-z^{5}}{(1-z)^{5}}}\equiv 1{\pmod {5}}\,.}</annotation></semantics></math><img src=$ ${\displaystyle {\frac {\left(1-z^{5} ight)\left(1-z^{10} ight)\left(1-z^{15} ight)\cdots }{\left((1-z)\left(1-z^{2} ight)\left(1-z^{3} ight)\cdots ight)^{5}}}\equiv 1{\pmod {5}}\,. <semantics><mrow><mstyle><mrow><mfrac><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>5</mn></mrow></msup></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>10</mn></mrow></msup></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>15</mn></mrow></msup></mrow><mo>)</mo></mrow><mo>⋯</mo></mrow><msup><mrow><mo>(</mo><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><mo>)</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>3</mn></mrow></msup></mrow><mo>)</mo></mrow><mo>⋯</mo></mrow><mo>)</mo></mrow><mrow><mn>5</mn></mrow></msup></mfrac></mrow><mo>≡</mo><mn>1</mn><mrow><mspace></mspace><mo>(</mo><mi>mod</mi><mspace></mspace><mn>5</mn><mo>)</mo></mrow><mspace></mspace><mo>.</mo></mstyle></mrow><annotation>{\displaystyle {\frac {\left(1-z^{5} ight)\left(1-z^{10} ight)\left(1-z^{15} ight)\cdots }{\left((1-z)\left(1-z^{2} ight)\left(1-z^{3} ight)\cdots ight)^{5}}}\equiv 1{\pmod {5}}\,.}</annotation></semantics></math><img src=$

En utilisant les développements en produits infinis de ${\displaystyle z\cdot {\frac {\left(1-z^{5} ight)\left(1-z^{10} ight)\cdots }{\left(1-z ight)\left(1-z^{2} ight)\cdots }}=z\cdot \left((1-z)\left(1-z^{2} ight)\cdots ight)^{4} imes {\frac {\left(1-z^{5} ight)\left(1-z^{10} ight)\cdots }{\left(\left(1-z ight)\left(1-z^{2} ight)\cdots ight)^{5}}}\,, <semantics><mrow><mstyle><mi>z</mi><mo>⋅</mo><mrow><mfrac><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>5</mn></mrow></msup></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>10</mn></mrow></msup></mrow><mo>)</mo></mrow><mo>⋯</mo></mrow><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><mi>z</mi></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow><mo>)</mo></mrow><mo>⋯</mo></mrow></mfrac></mrow><mo>=</mo><mi>z</mi><mo>⋅</mo><msup><mrow><mo>(</mo><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><mo>)</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow><mo>)</mo></mrow><mo>⋯</mo></mrow><mo>)</mo></mrow><mrow><mn>4</mn></mrow></msup><mo>×</mo><mrow><mfrac><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>5</mn></mrow></msup></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>10</mn></mrow></msup></mrow><mo>)</mo></mrow><mo>⋯</mo></mrow><msup><mrow><mo>(</mo><mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><mi>z</mi></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mn>1</mn><mo>−</mo><msup><mi>z</mi><mrow><mn>2</mn></mrow></msup></mrow><mo>)</mo></mrow><mo>⋯</mo></mrow><mo>)</mo></mrow><mrow><mn>5</mn></mrow></msup></mfrac></mrow><mspace></mspace><mo>,</mo></mstyle></mrow><annotation>{\displaystyle z\cdot {\frac {\left(1-z^{5} ight)\left(1-z^{10} ight)\cdots }{\left(1-z ight)\left(1-z^{2} ight)\cdots }}=z\cdot \left((1-z)\left(1-z^{2} ight)\cdots ight)^{4} imes {\frac {\left(1-z^{5} ight)\left(1-z^{10} ight)\cdots }{\left(\left(1-z ight)\left(1-z^{2} ight)\cdots ight)^{5}}}\,,}</annotation></semantics></math><img src=$ ${\displaystyle {\begin{aligned}\sum _{n=1}^{\infty }p(n-1)z^{n}&={\frac {z}{(1-z)\left(1-z^{2} ight)\cdots }}\\[6px]&=z\cdot {\frac {\left(1-z^{5} ight)\left(1-z^{10} ight)\cdots }{(1-z)\left(1-z^{2} ight)\cdots }} imes \left(1+z^{5}+z^{10}+\cdots ight)\left(1+z^{10}+z^{20}+\cdots ight)\cdots \end{aligned </span referrerpolicy=$ nous pouvons égaler les coefficients de dans les équations précédentes pour prouver notre résultat de congruence souhaité, à savoir que pour tout .

Transformations des fonctions génératrices

Il existe plusieurs transformations de fonctions génératrices offrant d'autres applications (voir l' article principal ). Une transformation de la fonction génératrice ordinaire (FGO) d'une suite permet de convertir la fonction génératrice d'une suite en une fonction génératrice d'une autre. Ces transformations font généralement intervenir des formules intégrales faisant intervenir une FGO de la suite (voir transformations intégrales ) ou des sommes pondérées sur les dérivées d'ordre supérieur de ces fonctions (voir transformations de dérivées ).

Les transformations de fonctions génératrices peuvent intervenir lorsque nous cherchons à exprimer une fonction génératrice pour les sommes. ${\displaystyle s_{n}:=\sum _{m=0}^{n}{\binom {n}{m}}C_{n,m}a_{m}, <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><mo>:=</mo><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mi>n</mi><mi>m</mi></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msub><mi>C</mi><mrow><mi>n</mi><mo>,</mo><mi>m</mi></mrow></msub><msub><mi>un</mi><mrow><mi>m</mi></mrow></msub><mo>,</mo></mstyle></mrow><annotation>{\displaystyle s_{n}:=\sum _{m=0}^{n}{\binom {n}{m}}C_{n,m}a_{m},}</annotation></semantics></math><img src=$

sous la forme impliquant la fonction génératrice de la séquence originale. Par exemple, si les sommes sont ${\displaystyle s_{n}:=\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}a_{k}\, <semantics><mrow><mstyle><msub><mi>s</mi><mrow><mi>n</mi></mrow></msub><mo>:=</mo><munderover><mo>∑</mo><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></munderover><mrow><mrow><mrow><mo>(</mo></mrow><mfrac><mrow><mi>n</mi><mo>+</mo><mi>k</mi></mrow><mrow><mi>m</mi><mo>+</mo><mn>2</mn><mi>k</mi></mrow></mfrac><mrow><mo>)</mo></mrow></mrow></mrow><msub><mi>un</mi><mrow><mi>k</mi></mrow></msub><mspace></mspace></mstyle></mrow><annotation>{\displaystyle s_{n}:=\sum _{k=0}^{\infty }{\binom {n+k}{m+2k}}a_{k}\,}</annotation></semantics></math><img src=$ ${\displaystyle S(z)={\frac {z^{m}}{(1-z)^{m+1}}}A\left({\frac {z}{(1-z)^{2}}} ight) <semantics><mrow><mstyle><mi>S</mi><mo>(</mo><mi>z</mi><mo>)</mo><mo>=</mo><mrow><mfrac><msup><mi>z</mi><mrow><mi>m</mi></mrow></msup><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></msup></mrow></mfrac></mrow><mi>UN</mi><mrow><mo>(</mo><mrow><mfrac><mi>z</mi><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>z</mi><msup><mo>)</mo><mrow><mn>2</mn></mrow></msup></mrow></mfrac></mrow><mo>)</mo></mrow></mstyle></mrow><annotation>{\displaystyle S(z)={\frac {z^{m}}{(1-z)^{m+1}}}A\left({\frac {z}{(1-z)^{2}}} ight)}</annotation></semantics></math><img src=$

Il existe également des formules intégrales pour convertir entre la fonction génératrice ordinaire (FGO) d'une séquence, , et sa fonction génératrice exponentielle (FGE), , et vice versa, données par ${\displaystyle {\begin{aligned}F(z)&=\int _{0}^{\infty }{\hat {F}}(tz)e^{-t}\,dt\,,\\[4px]{\hat {F}}(z)&={\frac {1}{2\pi }}\int _{-\pi }^{\pi }F\left(ze^{-i\vartheta } ight)e^{e^{i\vartheta }}\,d\vartheta \,,\end{aligned <semantics><mrow><mstyle><mrow><mtable><mtr><mtd><mi>F</mi><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><msubsup><mo>∫</mo><mrow><mn>0</mn></mrow><mrow><mi>∞</mi></mrow></msubsup><mrow><mrow><mover><mi>F</mi><mo>^</mo></mover></mrow></mrow><mo>(</mo><mi>t</mi><mi>z</mi><mo>)</mo><msup><mi>e</mi><mrow><mo>−</mo><mi>t</mi></mrow></msup><mspace></mspace><mi>d</mi><mi>t</mi><mspace></mspace><mo>,</mo></mtd></mtr><mtr><mtd><mrow><mrow><mover><mi>F</mi><mo>^</mo></mover></mrow></mrow><mo>(</mo><mi>z</mi><mo>)</mo></mtd><mtd><mi></mi><mo>=</mo><mrow><mfrac><mn>1</mn><mrow><mn>2</mn><mi>π</mi></mrow></mfrac></mrow><msubsup><mo>∫</mo><mrow><mo>−</mo><mi>π</mi></mrow><mrow><mi>π</mi></mrow></msubsup><mi>F</mi><mrow><mo>(</mo><mrow><mi>z</mi><msup><mi>e</mi><mrow><mo>−</mo><mi>je</mi><mi>ϑ</mi></mrow></msup></mrow><mo>)</mo></mrow><msup><mi>e</mi><mrow><msup><mi>e</mi><mrow><mi>je</mi><mi>ϑ</mi></mrow></msup></mrow></msup><mspace></mspace><mi>d</mi><mi>ϑ</mi><mspace></mspace><mo>,</mo></mtd></mtr></mtable></mrow></mstyle></mrow><annotation>{\displaystyle {\begin{aligned}F(z)&=\int _{0}^{\infty }{\hat {F}}(tz)e^{-t}\,dt\,,\\[4px]{\hat {F}}(z)&={\frac {1}{2\pi }}\int _{-\pi }^{\pi }F\left(ze^{-i\vartheta } ight)e^{e^{i\vartheta }}\,d\vartheta \,,\end{aligned}}}</annotation></semantics></math><img src=$

à condition que ces intégrales convergent pour des valeurs appropriées de

Plus d articles de Worldlex Wiki

Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Explorer l index