Mathématiques pour l'informatique 4

TD 4

Séries génératrices exponentielles

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.

  1. Dérangements $$D(x)=\frac{e^{-x}}{1-x}=\sum_{n\ge 0}d_n \frac{x^n}{n!}$$

  2. Nombres de Bell $$\ B(x)= e^{e^x-1}=\sum_{n\ge 0}b_n\frac{x^n}{n!}$$

  3. 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)!}$$

In [1]:
# Exemple de calcul
from sympy import *
var('x')
s = series(exp(2*x),x,0,9).removeO().as_poly(); s
Out[1]:
Poly(2/315*x**8 + 8/315*x**7 + 4/45*x**6 + 4/15*x**5 + 2/3*x**4 + 4/3*x**3 + 2*x**2 + 2*x + 1, x, domain='QQ')
In [2]:
ss = s.all_coeffs()[::-1]; ss
Out[2]:
[1, 2, 2, 4/3, 2/3, 4/15, 4/45, 8/315, 2/315]
In [3]:
[ss[i]*factorial(i) for i in range(len(ss))]
Out[3]:
[1, 2, 4, 8, 16, 32, 64, 128, 256]

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,...,?$.

Triangles combinatoires et séries génératrices doubles

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!}.$$

In [4]:
# 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
Out[4]:
Poly((t**8/40320 + t**7/5040 + t**6/1440 + t**5/720 + t**4/576 + t**3/720 + t**2/1440 + t/5040 + 1/40320)*x**8 + (t**7/5040 + t**6/720 + t**5/240 + t**4/144 + t**3/144 + t**2/240 + t/720 + 1/5040)*x**7 + (t**6/720 + t**5/120 + t**4/48 + t**3/36 + t**2/48 + t/120 + 1/720)*x**6 + (t**5/120 + t**4/24 + t**3/12 + t**2/12 + t/24 + 1/120)*x**5 + (t**4/24 + t**3/6 + t**2/4 + t/6 + 1/24)*x**4 + (t**3/6 + t**2/2 + t/2 + 1/6)*x**3 + (t**2/2 + t + 1/2)*x**2 + (t + 1)*x + 1, x, domain='QQ[t]')
In [5]:
ss = s.all_coeffs()[::-1]; ss
Out[5]:
[1,
 t + 1,
 t**2/2 + t + 1/2,
 t**3/6 + t**2/2 + t/2 + 1/6,
 t**4/24 + t**3/6 + t**2/4 + t/6 + 1/24,
 t**5/120 + t**4/24 + t**3/12 + t**2/12 + t/24 + 1/120,
 t**6/720 + t**5/120 + t**4/48 + t**3/36 + t**2/48 + t/120 + 1/720,
 t**7/5040 + t**6/720 + t**5/240 + t**4/144 + t**3/144 + t**2/240 + t/720 + 1/5040,
 t**8/40320 + t**7/5040 + t**6/1440 + t**5/720 + t**4/576 + t**3/720 + t**2/1440 + t/5040 + 1/40320]
In [6]:
[ss[i]*factorial(i) for i in range(len(ss))]
Out[6]:
[1,
 t + 1,
 t**2 + 2*t + 1,
 t**3 + 3*t**2 + 3*t + 1,
 t**4 + 4*t**3 + 6*t**2 + 4*t + 1,
 t**5 + 5*t**4 + 10*t**3 + 10*t**2 + 5*t + 1,
 t**6 + 6*t**5 + 15*t**4 + 20*t**3 + 15*t**2 + 6*t + 1,
 t**7 + 7*t**6 + 21*t**5 + 35*t**4 + 35*t**3 + 21*t**2 + 7*t + 1,
 t**8 + 8*t**7 + 28*t**6 + 56*t**5 + 70*t**4 + 56*t**3 + 28*t**2 + 8*t + 1]
In [7]:
for p in _: print p.as_poly(t).all_coeffs()
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
[1, 6, 15, 20, 15, 6, 1]
[1, 7, 21, 35, 35, 21, 7, 1]
[1, 8, 28, 56, 70, 56, 28, 8, 1]

Polynômes de Bell et nombres de Stirling

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.

Nombres et polynômes de Bernoulli

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.

In [7]: