Mathématiques pour l'informatique 4

TD 5

Nombres de Stirling et calcul de sommes

On rappelle (cf. TP 3) que les polynômes de Bell (ou de Touchard) $b_n(t)$, sont 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!}. $$ 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 pour $n\le 9$ (puissances de $t$ en ordre croissant).

Écrivez un fonction calculant $S(n,k)$ au moyen de la récurrence vue en cours $$ S(n,k) = S(n-1,k-1)+kS(n-1,k),$$ avec les conditions initiales $S(0,0)=1$ et $S(n,0)=S(0,n)=0$ (voir ici).

Les nombres de Stirling de première espèce $s(n,k)$ sont les coefficients des polynômes $$t^{\underline n}=(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 pour $n\le 9$.

Écrivez une fonction calculant $s(n,k)$ au moyen de la récurrence vue en cours $$ s(n,k)= s(n-1,k-1) - (n-1)s(n-1,k),$$ avec les conditions initiales $s(0,0)=1$ et $s(n,0)=s(0,n)=0$ (voir ).

In [1]:
# Modèle avec le triangle de Pascal

from sympy import *
var('x t')
Out[1]:
(x, t)
In [2]:
def C(n,k):
    if k==n==0: return 1
    elif k>n or k<0: return 0
    else: return C(n-1,k-1)+C(n-1,k)
In [3]:
for n in  range(10):
    for k in range(n+1): 
        print C(n,k),
    print 
        
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
1 9 36 84 126 126 84 36 9 1

Calcul de sommes

On a vu que l'opération "intégrale discrète" $$\Sigma_a^b f(t)\delta t := \sum_{k=a}^{b-1} f(k)$$ était à l'opérateur de différence finie ce que l'intégrale ordinaire est à la dérivée : $$ \Sigma_a^b f(t)\delta t = F(b)-F(a)\ {\rm si}\ \Delta F(t):=F(t+1)-F(t)=f(t)$$ et aussi que $$\Sigma_0^n t^{\underline n} \delta t = \frac {t^{\underline{n+1}}}{n+1}$$

Sachant que $$t^n = \sum_{k=1}^n S(n,k) t^{\underline k}$$ on a donc $$S_p(n):=\sum_{k=0}^{n-1}k^p = \Sigma_0^n t^p\delta t = \Sigma_0^n \sum_{j=1}^p S(p,j)t^{\underline j}\delta t$$ $$ = \sum_{j=1}^p S(p,j)\frac {n^{\underline{j+1} }}{j+1}$$ et il ne reste plus qu'à redévelopper les $t^{\underline {j+1}}$ au moyen des nombres de Stirling de première espèce (ou plus brutalement, avec la fonction expand).

Utilisez vos nombres de Stirling pour donner l'expression des sommes $S_p(n)$ pour $p$ de 1 à 8. Présentez les résultats sous forme factorisée.

Le résultat devra ressembler à ceci :

>>> for p in range(1,5): print sumpow(p)

t*(t - 1)/2
t*(t - 1)*(2*t - 1)/6
t**2*(t - 1)**2/4
t*(t - 1)*(2*t - 1)*(3*t**2 - 3*t - 1)/30
In [4]:
# Un test
S4 = (t*(t - 1)*(2*t - 1)*(3*t**2 - 3*t - 1)/30).as_poly()
S4
Out[4]:
Poly(1/5*t**5 - 1/2*t**4 + 1/3*t**3 - 1/30*t, t, domain='QQ')
In [5]:
# Un petit test pour voir

for n in range(1,10): 
    print sum([k**4 for k in range(n)]), S4.eval(n)
0 0
1 1
17 17
98 98
354 354
979 979
2275 2275
4676 4676
8772 8772

Sommes de puissances et polynômes de Bernoulli

Les polynômes de Bernoulli sont définis par la série génératreice exponentielle (TP 3)

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

D'après le calcul vu en cours, on doit avoir $$S_p(n)=\frac{B_{p+1}(n)-B_{p+1}(0)}{p+1}\ \text{et aussi}\ S(x,n)=\sum_{p\ge 0}S_p(n)\frac{x^p}{p!}=\frac{e^{nx}-1}{e^x-1}.$$ Calculez les premiers polynômes de Bernoulli, recalculez les sommes $S_p(t)$ par cette méthode, et comparez à vos résultats précédents.

In [5]: