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 [2]:
# Exemple de calcul
from sympy import *
var('x')
s = series(exp(2*x),x,0,9).removeO().as_poly(); s
Out[2]:
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 [3]:
ss = s.all_coeffs()[::-1]; ss
Out[3]:
[1, 2, 2, 4/3, 2/3, 4/15, 4/45, 8/315, 2/315]
In [4]:
[ss[i]*factorial(i) for i in range(len(ss))]
Out[4]:
[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,...,?\).

In [26]:
# Dérangements
d = exp(-x)/(1-x)
d = series(d,x,0,10).removeO().as_poly();d
Out[26]:
Poly(16687/45360*x**9 + 2119/5760*x**8 + 103/280*x**7 + 53/144*x**6 + 11/30*x**5 + 3/8*x**4 + 1/3*x**3 + 1/2*x**2 + 1, x, domain='QQ')
In [27]:
dd = d.all_coeffs()[::-1];dd
Out[27]:
[1, 0, 1/2, 1/3, 3/8, 11/30, 53/144, 103/280, 2119/5760, 16687/45360]
In [28]:
[dd[i]*factorial(i) for i in range(len(dd))]
Out[28]:
[1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496]
In [29]:
# Nombres de Bell
b = exp(exp(x)-1)
b = series(b,x,0,10).removeO().as_poly();b
Out[29]:
Poly(1007/17280*x**9 + 23/224*x**8 + 877/5040*x**7 + 203/720*x**6 + 13/30*x**5 + 5/8*x**4 + 5/6*x**3 + x**2 + x + 1, x, domain='QQ')
In [30]:
bb = b.all_coeffs()[::-1];bb
Out[30]:
[1, 1, 1, 5/6, 5/8, 13/30, 203/720, 877/5040, 23/224, 1007/17280]
In [31]:
[bb[i]*factorial(i) for i in range(len(bb))]
Out[31]:
[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]
In [32]:
# Nombres d'Euler
e = 1/cos(x)+tan(x)
e = series(e,x,0,10).removeO().as_poly();e
Out[32]:
Poly(62/2835*x**9 + 277/8064*x**8 + 17/315*x**7 + 61/720*x**6 + 2/15*x**5 + 5/24*x**4 + 1/3*x**3 + 1/2*x**2 + x + 1, x, domain='QQ')
In [33]:
ee = e.all_coeffs()[::-1];ee
Out[33]:
[1, 1, 1/2, 1/3, 5/24, 2/15, 61/720, 17/315, 277/8064, 62/2835]
In [34]:
[ee[i]*factorial(i) for i in range(len(ee))]
Out[34]:
[1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936]
In [39]:
from itertools import permutations

print list(permutations(range(1,4)))
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

In [40]:
def is_alt(ll):
    return all([(ll[i]-ll[i+1])*(-1)**i > 0 for i in range(len(ll)-1)])
In [41]:
filter(is_alt,permutations(range(1,5)))
Out[41]:
[(2, 1, 4, 3), (3, 1, 4, 2), (3, 2, 4, 1), (4, 1, 3, 2), (4, 2, 3, 1)]
In [42]:
def altperm(n): return filter(is_alt,permutations(range(1,n+1)))
In [44]:
print altperm(5)
[(2, 1, 4, 3, 5), (2, 1, 5, 3, 4), (3, 1, 4, 2, 5), (3, 1, 5, 2, 4), (3, 2, 4, 1, 5), (3, 2, 5, 1, 4), (4, 1, 3, 2, 5), (4, 1, 5, 2, 3), (4, 2, 3, 1, 5), (4, 2, 5, 1, 3), (4, 3, 5, 1, 2), (5, 1, 3, 2, 4), (5, 1, 4, 2, 3), (5, 2, 3, 1, 4), (5, 2, 4, 1, 3), (5, 3, 4, 1, 2)]

In [46]:
def Euler(n): return len(altperm(n))
In [47]:
for n in range(12): print Euler(n)
1
1
1
2
5
16
61
272
1385
7936
50521
353792

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 [5]:
# 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[5]:
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 [6]:
ss = s.all_coeffs()[::-1]; ss
Out[6]:
[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 [7]:
[ss[i]*factorial(i) for i in range(len(ss))]
Out[7]:
[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 [8]:
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}x^n = \sum_{n\ge 0}(t)_n\frac{x^n}{n!}.\] Affichez le triangle Stirling1.

In [9]:
B = exp(t*(exp(x)-1)); B
s = series(B,x,0,10).removeO().as_poly(x); s
Out[9]:
Poly((t**9/362880 + t**8/10080 + 11*t**7/8640 + 7*t**6/960 + 331*t**5/17280 + 37*t**4/1728 + 605*t**3/72576 + 17*t**2/24192 + t/362880)*x**9 + (t**8/40320 + t**7/1440 + 19*t**6/2880 + 5*t**5/192 + 27*t**4/640 + 23*t**3/960 + 127*t**2/40320 + t/40320)*x**8 + (t**7/5040 + t**6/240 + t**5/36 + 5*t**4/72 + 43*t**3/720 + t**2/80 + t/5040)*x**7 + (t**6/720 + t**5/48 + 13*t**4/144 + t**3/8 + 31*t**2/720 + t/720)*x**6 + (t**5/120 + t**4/12 + 5*t**3/24 + t**2/8 + t/120)*x**5 + (t**4/24 + t**3/4 + 7*t**2/24 + t/24)*x**4 + (t**3/6 + t**2/2 + t/6)*x**3 + (t**2/2 + t/2)*x**2 + t*x + 1, x, domain='QQ[t]')
In [10]:
ss = s.all_coeffs()[::-1]; ss
Out[10]:
[1,
 t,
 t**2/2 + t/2,
 t**3/6 + t**2/2 + t/6,
 t**4/24 + t**3/4 + 7*t**2/24 + t/24,
 t**5/120 + t**4/12 + 5*t**3/24 + t**2/8 + t/120,
 t**6/720 + t**5/48 + 13*t**4/144 + t**3/8 + 31*t**2/720 + t/720,
 t**7/5040 + t**6/240 + t**5/36 + 5*t**4/72 + 43*t**3/720 + t**2/80 + t/5040,
 t**8/40320 + t**7/1440 + 19*t**6/2880 + 5*t**5/192 + 27*t**4/640 + 23*t**3/960 + 127*t**2/40320 + t/40320,
 t**9/362880 + t**8/10080 + 11*t**7/8640 + 7*t**6/960 + 331*t**5/17280 + 37*t**4/1728 + 605*t**3/72576 + 17*t**2/24192 + t/362880]
In [15]:
ll = [ss[i]*factorial(i) for i in range(len(ss))];ll
Out[15]:
[1,
 t,
 t**2 + t,
 t**3 + 3*t**2 + t,
 t**4 + 6*t**3 + 7*t**2 + t,
 t**5 + 10*t**4 + 25*t**3 + 15*t**2 + t,
 t**6 + 15*t**5 + 65*t**4 + 90*t**3 + 31*t**2 + t,
 t**7 + 21*t**6 + 140*t**5 + 350*t**4 + 301*t**3 + 63*t**2 + t,
 t**8 + 28*t**7 + 266*t**6 + 1050*t**5 + 1701*t**4 + 966*t**3 + 127*t**2 + t,
 t**9 + 36*t**8 + 462*t**7 + 2646*t**6 + 6951*t**5 + 7770*t**4 + 3025*t**3 + 255*t**2 + t]
In [19]:
# Stirling 2
for p in ll: print p.as_poly(t).all_coeffs()[::-1]
[1]
[0, 1]
[0, 1, 1]
[0, 1, 3, 1]
[0, 1, 7, 6, 1]
[0, 1, 15, 25, 10, 1]
[0, 1, 31, 90, 65, 15, 1]
[0, 1, 63, 301, 350, 140, 21, 1]
[0, 1, 127, 966, 1701, 1050, 266, 28, 1]
[0, 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1]

In [13]:
# Stirling 1
def fallpow(n):
    return expand(reduce(lambda a,b:a*b,[t-i for i in range(n)]))
In [20]:
fallpow(4)
Out[20]:
t**4 - 6*t**3 + 11*t**2 - 6*t
In [24]:
for i in range(1,10): 
    print fallpow(i).as_poly(t).all_coeffs()[::-1]
[0, 1]
[0, -1, 1]
[0, 2, -3, 1]
[0, -6, 11, -6, 1]
[0, 24, -50, 35, -10, 1]
[0, -120, 274, -225, 85, -15, 1]
[0, 720, -1764, 1624, -735, 175, -21, 1]
[0, -5040, 13068, -13132, 6769, -1960, 322, -28, 1]
[0, 40320, -109584, 118124, -67284, 22449, -4536, 546, -36, 1]

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 [48]:
be = x*exp(t*x)/(exp(x)-1)
be = series(be,x,0,10).removeO().as_poly(x); be
Out[48]:
Poly((t**9/362880 - t**8/80640 + t**7/60480 - t**5/86400 + t**3/181440 - t/1209600)*x**9 + (t**8/40320 - t**7/10080 + t**6/8640 - t**4/17280 + t**2/60480 - 1/1209600)*x**8 + (t**7/5040 - t**6/1440 + t**5/1440 - t**3/4320 + t/30240)*x**7 + (t**6/720 - t**5/240 + t**4/288 - t**2/1440 + 1/30240)*x**6 + (t**5/120 - t**4/48 + t**3/72 - t/720)*x**5 + (t**4/24 - t**3/12 + t**2/24 - 1/720)*x**4 + (t**3/6 - t**2/4 + t/12)*x**3 + (t**2/2 - t/2 + 1/12)*x**2 + (t - 1/2)*x + 1, x, domain='QQ[t]')
In [49]:
be = be.all_coeffs()[::-1];be
Out[49]:
[1,
 t - 1/2,
 t**2/2 - t/2 + 1/12,
 t**3/6 - t**2/4 + t/12,
 t**4/24 - t**3/12 + t**2/24 - 1/720,
 t**5/120 - t**4/48 + t**3/72 - t/720,
 t**6/720 - t**5/240 + t**4/288 - t**2/1440 + 1/30240,
 t**7/5040 - t**6/1440 + t**5/1440 - t**3/4320 + t/30240,
 t**8/40320 - t**7/10080 + t**6/8640 - t**4/17280 + t**2/60480 - 1/1209600,
 t**9/362880 - t**8/80640 + t**7/60480 - t**5/86400 + t**3/181440 - t/1209600]
In [50]:
ll = [be[i]*factorial(i) for i in range(len(be))];ll
Out[50]:
[1,
 t - 1/2,
 t**2 - t + 1/6,
 t**3 - 3*t**2/2 + t/2,
 t**4 - 2*t**3 + t**2 - 1/30,
 t**5 - 5*t**4/2 + 5*t**3/3 - t/6,
 t**6 - 3*t**5 + 5*t**4/2 - t**2/2 + 1/42,
 t**7 - 7*t**6/2 + 7*t**5/2 - 7*t**3/6 + t/6,
 t**8 - 4*t**7 + 14*t**6/3 - 7*t**4/3 + 2*t**2/3 - 1/30,
 t**9 - 9*t**8/2 + 6*t**7 - 21*t**5/5 + 2*t**3 - 3*t/10]
In [51]:
b = x/(exp(x)-1)
b = series(b,x,0,20).removeO().as_poly();b
Out[51]:
Poly(43867/5109094217170944000*x**18 - 3617/10670622842880000*x**16 + 1/74724249600*x**14 - 691/1307674368000*x**12 + 1/47900160*x**10 - 1/1209600*x**8 + 1/30240*x**6 - 1/720*x**4 + 1/12*x**2 - 1/2*x + 1, x, domain='QQ')
In [52]:
b = b.all_coeffs()[::-1];b
Out[52]:
[1,
 -1/2,
 1/12,
 0,
 -1/720,
 0,
 1/30240,
 0,
 -1/1209600,
 0,
 1/47900160,
 0,
 -691/1307674368000,
 0,
 1/74724249600,
 0,
 -3617/10670622842880000,
 0,
 43867/5109094217170944000]
In [55]:
print [factorial(i)*b[i] for i in range(len(b))]
[1, -1/2, 1/6, 0, -1/30, 0, 1/42, 0, -1/30, 0, 5/66, 0, -691/2730, 0, 7/6, 0, -3617/510, 0, 43867/798]

In []: