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

# Exemple de calcul
from sympy import *
var('x')
s = series(exp(2*x),x,0,9).removeO().as_poly(); s

$\displaystyle \operatorname{Poly}{\left( \frac{2}{315} x^{8} + \frac{8}{315} x^{7} + \frac{4}{45} x^{6} + \frac{4}{15} x^{5} + \frac{2}{3} x^{4} + \frac{4}{3} x^{3} + 2 x^{2} + 2 x + 1, x, domain=\mathbb{Q} \right)}$

ss = s.all_coeffs()[::-1]; ss

[1, 2, 2, 4/3, 2/3, 4/15, 4/45, 8/315, 2/315]

[ss[i]*factorial(i) for i in range(len(ss))]

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

# Dérangements
d = exp(-x)/(1-x)
d = series(d,x,0,10).removeO().as_poly();d

$\displaystyle \operatorname{Poly}{\left( \frac{16687}{45360} x^{9} + \frac{2119}{5760} x^{8} + \frac{103}{280} x^{7} + \frac{53}{144} x^{6} + \frac{11}{30} x^{5} + \frac{3}{8} x^{4} + \frac{1}{3} x^{3} + \frac{1}{2} x^{2} + 1, x, domain=\mathbb{Q} \right)}$

dd = d.all_coeffs()[::-1];dd

[1, 0, 1/2, 1/3, 3/8, 11/30, 53/144, 103/280, 2119/5760, 16687/45360]

[dd[i]*factorial(i) for i in range(len(dd))]

[1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496]

# Nombres de Bell
b = exp(exp(x)-1)
b = series(b,x,0,10).removeO().as_poly();b

$\displaystyle \operatorname{Poly}{\left( \frac{1007}{17280} x^{9} + \frac{23}{224} x^{8} + \frac{877}{5040} x^{7} + \frac{203}{720} x^{6} + \frac{13}{30} x^{5} + \frac{5}{8} x^{4} + \frac{5}{6} x^{3} + x^{2} + x + 1, x, domain=\mathbb{Q} \right)}$

bb = b.all_coeffs()[::-1];bb

[1, 1, 1, 5/6, 5/8, 13/30, 203/720, 877/5040, 23/224, 1007/17280]

[bb[i]*factorial(i) for i in range(len(bb))]

[1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147]

# Nombres d'Euler
e = 1/cos(x)+tan(x)
e = series(e,x,0,10).removeO().as_poly();e

$\displaystyle \operatorname{Poly}{\left( \frac{62}{2835} x^{9} + \frac{277}{8064} x^{8} + \frac{17}{315} x^{7} + \frac{61}{720} x^{6} + \frac{2}{15} x^{5} + \frac{5}{24} x^{4} + \frac{1}{3} x^{3} + \frac{1}{2} x^{2} + x + 1, x, domain=\mathbb{Q} \right)}$

ee = e.all_coeffs()[::-1];ee

[1, 1, 1/2, 1/3, 5/24, 2/15, 61/720, 17/315, 277/8064, 62/2835]

[ee[i]*factorial(i) for i in range(len(ee))]

[1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936]

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)]

def is_alt(ll):
    return all([(ll[i]-ll[i+1])*(-1)**i > 0 for i in range(len(ll)-1)])

filter(is_alt,permutations(range(1,5)))

<filter at 0x7fae9528f110>

list(_)

[(2, 1, 4, 3), (3, 1, 4, 2), (3, 2, 4, 1), (4, 1, 3, 2), (4, 2, 3, 1)]

def altperm(n): return filter(is_alt,permutations(range(1,n+1)))

print (list(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)]

def Euler(n): return len(list(altperm(n)))

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

# 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

$\displaystyle \operatorname{Poly}{\left( \left(\frac{t^{8}}{40320} + \frac{t^{7}}{5040} + \frac{t^{6}}{1440} + \frac{t^{5}}{720} + \frac{t^{4}}{576} + \frac{t^{3}}{720} + \frac{t^{2}}{1440} + \frac{t}{5040} + \frac{1}{40320}\right) x^{8} + \left(\frac{t^{7}}{5040} + \frac{t^{6}}{720} + \frac{t^{5}}{240} + \frac{t^{4}}{144} + \frac{t^{3}}{144} + \frac{t^{2}}{240} + \frac{t}{720} + \frac{1}{5040}\right) x^{7} + \left(\frac{t^{6}}{720} + \frac{t^{5}}{120} + \frac{t^{4}}{48} + \frac{t^{3}}{36} + \frac{t^{2}}{48} + \frac{t}{120} + \frac{1}{720}\right) x^{6} + \left(\frac{t^{5}}{120} + \frac{t^{4}}{24} + \frac{t^{3}}{12} + \frac{t^{2}}{12} + \frac{t}{24} + \frac{1}{120}\right) x^{5} + \left(\frac{t^{4}}{24} + \frac{t^{3}}{6} + \frac{t^{2}}{4} + \frac{t}{6} + \frac{1}{24}\right) x^{4} + \left(\frac{t^{3}}{6} + \frac{t^{2}}{2} + \frac{t}{2} + \frac{1}{6}\right) x^{3} + \left(\frac{t^{2}}{2} + t + \frac{1}{2}\right) x^{2} + \left(t + 1\right) x + 1, x, domain=\mathbb{Q}\left[t\right] \right)}$

ss = s.all_coeffs()[::-1]; ss

[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]

[ss[i]*factorial(i) for i in range(len(ss))]

[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]

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_{n\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.

B = exp(t*(exp(x)-1)); B
s = series(B,x,0,10).removeO().as_poly(x); s

$\displaystyle \operatorname{Poly}{\left( \left(\frac{t^{9}}{362880} + \frac{t^{8}}{10080} + \frac{11 t^{7}}{8640} + \frac{7 t^{6}}{960} + \frac{331 t^{5}}{17280} + \frac{37 t^{4}}{1728} + \frac{605 t^{3}}{72576} + \frac{17 t^{2}}{24192} + \frac{t}{362880}\right) x^{9} + \left(\frac{t^{8}}{40320} + \frac{t^{7}}{1440} + \frac{19 t^{6}}{2880} + \frac{5 t^{5}}{192} + \frac{27 t^{4}}{640} + \frac{23 t^{3}}{960} + \frac{127 t^{2}}{40320} + \frac{t}{40320}\right) x^{8} + \left(\frac{t^{7}}{5040} + \frac{t^{6}}{240} + \frac{t^{5}}{36} + \frac{5 t^{4}}{72} + \frac{43 t^{3}}{720} + \frac{t^{2}}{80} + \frac{t}{5040}\right) x^{7} + \left(\frac{t^{6}}{720} + \frac{t^{5}}{48} + \frac{13 t^{4}}{144} + \frac{t^{3}}{8} + \frac{31 t^{2}}{720} + \frac{t}{720}\right) x^{6} + \left(\frac{t^{5}}{120} + \frac{t^{4}}{12} + \frac{5 t^{3}}{24} + \frac{t^{2}}{8} + \frac{t}{120}\right) x^{5} + \left(\frac{t^{4}}{24} + \frac{t^{3}}{4} + \frac{7 t^{2}}{24} + \frac{t}{24}\right) x^{4} + \left(\frac{t^{3}}{6} + \frac{t^{2}}{2} + \frac{t}{6}\right) x^{3} + \left(\frac{t^{2}}{2} + \frac{t}{2}\right) x^{2} + t x + 1, x, domain=\mathbb{Q}\left[t\right] \right)}$

ss = s.all_coeffs()[::-1]; ss

[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]

ll = [ss[i]*factorial(i) for i in range(len(ss))];ll

[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]

# 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]

# Stirling 1
from functools import reduce
def fallpow(n):
    return expand(reduce(lambda a,b:a*b,[t-i for i in range(n)]))

fallpow(4)

$\displaystyle t^{4} - 6 t^{3} + 11 t^{2} - 6 t$

factor(_)

$\displaystyle t \left(t - 3\right) \left(t - 2\right) \left(t - 1\right)$

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.

be = x*exp(t*x)/(exp(x)-1)
be = series(be,x,0,10).removeO().as_poly(x); be

$\displaystyle \operatorname{Poly}{\left( \left(\frac{t^{9}}{362880} - \frac{t^{8}}{80640} + \frac{t^{7}}{60480} - \frac{t^{5}}{86400} + \frac{t^{3}}{181440} - \frac{t}{1209600}\right) x^{9} + \left(\frac{t^{8}}{40320} - \frac{t^{7}}{10080} + \frac{t^{6}}{8640} - \frac{t^{4}}{17280} + \frac{t^{2}}{60480} - \frac{1}{1209600}\right) x^{8} + \left(\frac{t^{7}}{5040} - \frac{t^{6}}{1440} + \frac{t^{5}}{1440} - \frac{t^{3}}{4320} + \frac{t}{30240}\right) x^{7} + \left(\frac{t^{6}}{720} - \frac{t^{5}}{240} + \frac{t^{4}}{288} - \frac{t^{2}}{1440} + \frac{1}{30240}\right) x^{6} + \left(\frac{t^{5}}{120} - \frac{t^{4}}{48} + \frac{t^{3}}{72} - \frac{t}{720}\right) x^{5} + \left(\frac{t^{4}}{24} - \frac{t^{3}}{12} + \frac{t^{2}}{24} - \frac{1}{720}\right) x^{4} + \left(\frac{t^{3}}{6} - \frac{t^{2}}{4} + \frac{t}{12}\right) x^{3} + \left(\frac{t^{2}}{2} - \frac{t}{2} + \frac{1}{12}\right) x^{2} + \left(t - \frac{1}{2}\right) x + 1, x, domain=\mathbb{Q}\left[t\right] \right)}$

be = be.all_coeffs()[::-1];be

[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]

ll = [be[i]*factorial(i) for i in range(len(be))];ll

[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]

b = x/(exp(x)-1)
b = series(b,x,0,20).removeO().as_poly();b

$\displaystyle \operatorname{Poly}{\left( \frac{43867}{5109094217170944000} x^{18} - \frac{3617}{10670622842880000} x^{16} + \frac{1}{74724249600} x^{14} - \frac{691}{1307674368000} x^{12} + \frac{1}{47900160} x^{10} - \frac{1}{1209600} x^{8} + \frac{1}{30240} x^{6} - \frac{1}{720} x^{4} + \frac{1}{12} x^{2} - \frac{1}{2} x + 1, x, domain=\mathbb{Q} \right)}$

b = b.all_coeffs()[::-1];b

[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]

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]