Les séries génératrices étudiées jusqu'à maintenant sont appelées séries génératrices ordinaires (SGO). Il est souvent utile d'introduire des séries de la forme $$ A(x) = \sum_{n\ge 0}a_n\frac{x^n}{n!},$$ dites séries génératrices exponentielles (SGE). Par exemple, $$e^x = \sum_{n\ge 0}\frac{x^n}{n!}$$ est la SGE de la suite constante $a_n=1$ alors que sa SGO est $\frac1{1-x}$.
On demande de calculer les premiers coefficients $d_n$, $b_n$, $E_n$ des SGE suivantes, et d'interroger l'encyclopédie des suites d'entiers.
Dérangements $$D(x)=\frac{e^{-x}}{1-x}=\sum_{n\ge 0}d_n \frac{x^n}{n!}$$
Nombres de Bell $$\ B(x)= e^{e^x-1}=\sum_{n\ge 0}b_n\frac{x^n}{n!}$$
Nombres d'Euler $$\tan(x)=\sum_{k\ge0}E_{2k+1}\frac{x^{2k+1}}{(2k+1)!}\ \text{et}\ \frac1{\cos(x)} =\sum_{k\ge 0}E_{2k}\frac{x^{2k}}{(2k)!}$$
# Exemple de calcul
from sympy import *
var('x')
s = series(exp(2*x),x,0,9).removeO().as_poly(); s
ss = s.all_coeffs()[::-1]; ss
[ss[i]*factorial(i) for i in range(len(ss))]
Les exemples 1 et 2 seront traités en cours.
Pour l'exemple 3, on constate que les $E_n$ sont des entiers positifs, ce qui n'a rien d'évident. Regardez leur interprétation combinatoire sur l'encyclopédie en ligne.
Une permutation $\sigma$ sera dite alternante si σ(1)<σ(2)>σ(3)<σ(4)>…. Ecrire une fonction aussi simple que possible qui teste si une permutation (représentée comme une liste ou un tuple d'entiers) est alternante.
Indication : utiliser la syntaxe [f(x) for x in quelquechose if truc(x)], et aussi all(une_liste) qui renvoie True si tous les éléments de la liste sont vrais.
On pourra ensuite importer la fonction permutations depuis le module itertools, et compter les permutations alternantes pour $n=1,2,3,4,...,?$.
Les suites combinatoires peuvent souvent être raffinées en prenant en compte un paramètre supplémémentaire. Par exemple, la suite $2^n$ compte les sous-ensembles d'un ensemble à $n$ éléments, et les coefficients du polynôme $$(1+t)^n = \sum_{k=0}^n{n\choose k}t^k$$ (qui devient $2^n$ pour $t=1$) comptent les sous-ensembles à $k$ éléments. Il forment un triangle combinatoire bien connu, le triangle de Pascal.
On pourrait le représenter par une série génératrice exponentielle double $$e^{(1+t)x} = \sum_{n\ge 0}(1+t)^n\frac{x^n}{n!}.$$
# On introduit une nouvelle variable
var('t')
# et on procède comme d'habitude
s = series(exp((1+t)*x),x,0,9).removeO().as_poly(x); s # noter le paramètre de as_poly
ss = s.all_coeffs()[::-1]; ss
[ss[i]*factorial(i) for i in range(len(ss))]
for p in _: print (p.as_poly(t).all_coeffs())
Calculer les premiers polynômes de Bell $b_n(t)$, définis par la série génératrice exponentielle $$ b(x,t)=e^{t(e^x−1)}=\sum_{\ge 0}b_n(t)\frac{x^n}{n!}. $$ (Ils sont souvent appelés polynômes de Touchard,cf. la page de Wikipedia).
Leurs coefficients sont les nombres de Stirling de seconde espèce : $$b_n(t)=\sum_{k=0}^n S(n,k)t^k.$$
Affichez le triangle Stirling2 comme ci-dessus (puissances de $t$ en ordre croissant).
On verra en cours leur interprétation combinatoire.
Les nombres de Stirling de première espèce $s(n,k)$ sont les coefficients des polynômes $$(t)_n = t(t-1)\cdots (t-n+1)$$ dont la série génératrice exponentielle est $$ (1+x)^t = \sum_{n\ge 0}{t\choose n} = \sum_{n\ge 0}(t)_n\frac{x^n}{n!}.$$ Affichez le triangle Stirling1.
Les polynômes de Bernoulli sont définis par la série génératreice exponentielle
$$B(x,t)=\sum_{n\ge 0}B_n(t)\frac{x^n}{n!} = \frac{xe^{tx}}{e^x-1}$$Calculez les premiers polynômes $B_n(t)$.
Les nombres de Bernoulli sont les termes constants $B_n(0)$. Ils ne sont pas entiers (ni positifs). Affichez les 20 premiers, et consultez la page qui leur est consacrée sur Wikipedia.