Worldlex Wiki Il existe différents types de fonctions génératrices, notamment les fonctions génératrices ordinaires , les fonctions génératrices exponentielles , les séries de Lambert , les séries de Bell et les séries de Dirichlet . En principe, toute suite possède une fonction génératrice de chaque type (à l'exception des séries de Lambert et de Dirichlet, pour lesquelles les indices commencent à 1 et non à 0), mais leur manipulation peut varier considérablement. La fonction génératrice la plus utile, le cas échéant, dépendra de la nature de la suite et des spécificités du problème considéré.
Les fonctions génératrices sont parfois appelées séries génératrices , dans la mesure où une série de termes peut être considérée comme le générateur de sa séquence de coefficients de termes.
Abraham de Moivre en 1730, afin de résoudre le problème général de récurrence linéaire.George Pólya écrit dans Mathématiques et raisonnement plausible :
Le terme « fonction génératrice » est dû à Laplace . Cependant, sans le nommer, Euler utilisa l'outil des fonctions génératrices bien avant Laplace. Il l'appliqua à plusieurs problèmes d'analyse combinatoire et de théorie des nombres .
Définition
Herbert Wilf , Générer la fonction (1994)Une fonction génératrice est un dispositif comparable à un sac. Au lieu de transporter plusieurs petits objets séparément, ce qui pourrait être gênant, on les met tous dans un sac, et on n'a alors qu'un seul objet à transporter : le sac.
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 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 à fonction de masse de probabilité d'une variable aléatoire discrète , alors sa fonction génératrice ordinaire est appelée fonction génératrice de probabilité .
Fonction génératrice exponentielle (EGF)
La fonction génératrice exponentielle d'une suite
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
et ses dérivées satisfont aisément l'équation différentielle
Série Lambert
Série Bell
La série de Bell d'une séquence
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
fonction multiplicative , auquel cas elle a une expression de produit d'Euler en termes de la série de Bell de la fonction :
Si caractère de Dirichlet, alors sa fonction génératrice de série de Dirichlet est appelée série de Dirichletsé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 : si et seulement si où fonction zêta de Riemann .
La suite de série de Dirichlet (DGF) correspondant à : a pour fonction génératrice ordinaire :
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 : où Les suites de Sheffer sont générées de manière similaire. Pour plus d'informations, voir l'article principal sur les polynômes d'Appell généralisés .
Voici quelques exemples de suites polynomiales générées par des fonctions génératrices plus complexes :
- Polynômes d'Appell
- polynômes de Tchebychev
- Polynômes de différence
- Polynômes d'Appell généralisés
- transformations intégrales correspondantes
Polynômes de convolution
L'article de Knuth intitulé « Convolution Polynomials » définit une classe généralisée de suites de polynômes de convolution par leurs fonctions génératrices spéciales de la forme pour une certaine fonction analytique
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 type binomial
- Les valeurs particulières de la séquence incluent
Pour un paramètre non nul fixé , nous avons modifié les fonctions génératrices de ces suites de polynômes de convolution, données par où équation fonctionnelle de la forme
Des exemples de suites de polynômes de convolution incluent la série de puissance binomiale , nombres de Bell , 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 série géométrique
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 inverse multiplicatif de suite géométrique
(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,
On peut également introduire des intervalles réguliers dans la suite en remplaçant
En élevant au carré la fonction génératrice initiale, ou en calculant la dérivée des deux membres par rapport à
et la troisième puissance a pour coefficients les nombres triangulaires coefficient binomial
Plus généralement, pour tout entier non négatif
Depuis
on peut trouver la fonction génératrice ordinaire de la suite nombres carrés par combinaison linéaire de suites génératrices à coefficients binomiaux :
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 :
Par récurrence, nous pouvons montrer de même pour les entiers positifs
où nombres de Stirling de seconde espèce et où la fonction génératrice
afin de pouvoir former les fonctions génératrices analogues sur les puissances entières
nous pouvons appliquer une identité de somme finie bien connue impliquant les nombres de Stirling pour obtenir que
Fonctions rationnelles
Nous remarquons également que la classe des fonctions génératrices rationnelles correspond précisément aux fonctions génératrices qui énumèrent les suites quasi-polynomiales de la forme
où les racines réciproques, , sont des scalaires fixes et où
est une fonction génératrice rationnelle bivariée, alors sa fonction génératrice diagonale correspondante ,
est algébrique . Par exemple, si nous posons
La fonction génératrice des coefficients diagonaux de cette fonction génératrice est alors donnée par la formule OGF bien connue.
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
Indices de séquence décalés
Pour les entiers
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 :
L'opération de dérivation-multiplication de la seconde identité peut être répétée factorielle décroissante .
En utilisant les nombres de Stirling de seconde espèce , on peut transformer cela en une autre formule de multiplication comme suit (voir l'article principal sur les transformations de fonctions génératrices ) :
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 article principal sur les transformations ). Pour parties paires et impaires (c'est-à-dire, puissances paires et impaires) :
Plus généralement, supposons que racine primitive de l'unité. Alors, comme application de latransformée de Fourier discrète, nous avons la formule
Pour les entiers
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}}\,, 
1