Combinatoire - TP 2 : Séries génératrices exponentielles

1) Les dérangements sont les permutations sans points fixes.

Déduire de la série vue en cours que le nombre $d_n$ de dérangements de $n$ objets vérifie $$D(x) =\frac{e^{-x}}{1-x}=\sum_{n\ge 0}d_n \frac{x^n}{n!}$$

Utiliser sympy pour calculer les 10 premiers $d_n$.

2) Les nombres de Bell $b_n$, qui comptent les partitions ensemblistes (à ne pas confondre avec les partitions d'entiers), ont pour série génératrice exponentielle

$$B(x)= e^{e^x-1}=\sum_{n\ge 0}b_n \frac{x^n}{n!}$$ Calculer de même les 10 premiers.

3) Même question avec $$\tan(x)=\sum_{k\ge 0}E_{2k+1}\frac{x^{2k+1}}{(2k+1)!}\ \text{et}\ \frac1{\cos(x)} = \sum_{k\ge 0}E_{2k}\frac{x^{2k}}{(2k)!}\ \text{(nombres d'Euler)}$$ On peut les traiter simulatnément, car l'une est impaire et l'autre paire.

4) Il a été prouvé en 1881 par D. André que $E_n$ était le nombre de permutations alterrnantes, c'est à dire telles que $\sigma(1)<\sigma(2)>\sigma(3)<\sigma(4)>\cdots$, autrement dit, ayant des descentes exactement aux positions 2,4,6, etc.

Vérifier l'interprétation combinatoire de ces nombres. On pourra utiliser itertools pour engendrer les permutations, et une fonction descents (à écrire si ce n'est pas déjà fait) pour sélectionner celles qui ont des descentes à toutes les positions paires.

Remarque Pour faire des statistiques sur un grand nombre de permutations, il ne faut pas utiliser la classe Permutation écrite au TD1, car la création des instances prend du temps. Il faut donc disposer de certaines de ses méthodes sous forme de fonctions indépendantes.

5) On va maintenant compter les permutations par nombres de cycles. Ecrire une fonction cycles qui calcule la décomposition en cycles, et une fonction CC(n) qui calcule la distribution du nombre de cycles sur $\mathfrak{S}_n$.

In [10]:
for i in range(10): print CC(i)
[1]
[1]
[1, 1]
[2, 3, 1]
[6, 11, 6, 1]
[24, 50, 35, 10, 1]
[120, 274, 225, 85, 15, 1]
[720, 1764, 1624, 735, 175, 21, 1]
[5040, 13068, 13132, 6769, 1960, 322, 28, 1]
[40320, 109584, 118124, 67284, 22449, 4536, 546, 36, 1]

Les nombres obtenus sont les nombres de Stirling de première espèce (non signés). On vérifie que les polynômes $P_n(t)$ ont bien la factorisation prédite par la théorie :

In [11]:
for n in range(2,9):
    ll=CC(n)
    p=Poly.from_list(ll,t)
    print p.factor()
t + 1
(t + 1)*(2*t + 1)
(t + 1)*(2*t + 1)*(3*t + 1)
(t + 1)*(2*t + 1)*(3*t + 1)*(4*t + 1)
(t + 1)*(2*t + 1)*(3*t + 1)*(4*t + 1)*(5*t + 1)
(t + 1)*(2*t + 1)*(3*t + 1)*(4*t + 1)*(5*t + 1)*(6*t + 1)
(t + 1)*(2*t + 1)*(3*t + 1)*(4*t + 1)*(5*t + 1)*(6*t + 1)*(7*t + 1)

6) Les polynômes eulériens $A_n(t)$ comptent les permutations par nombre de descentes, sont également très importants. Par définition, $$A_n(t)=\sum_{k=0}^{n-1}A(n,k)t^{k+1}= \sum_{\sigma\in\mathfrak{S}_n}t^{d(\sigma)+1}$$ où $A(n,k)$ est le nombre de permutations ayant exactement $k$ descentes.

Calculer les premiers polynômes $A_n(t)$.

7) Les nombres de Bell sont les valeurs en 1 des polynômes de Bell (ou de Touchard), dont les coefficients sont les nombres de Stirling de deuxième espèce.

La série génératrice de ces polynômes est $$B(x,t) = e^{t(e^x-1)} = \sum_{n\ge 0}b_n(t)\frac{x^n}{n!}.$$

Calculer les premiers $b_n(t)$.