Exercices accompagnant le cours de “Combinatoire algébrique, énumérative et fonctionnelle”. Madacascar 2007-2008.

G. H. E. Duchamp^{∗}

Exercice 1.1 Une partition non-ordonnée P d’un ensemble X est une partie P ⊂ 𝔓(X)− {∅}^{1} (c’est un ensemble de blocs [2], c’est à dire de parties non-vides de X) telle que

– la réunion des blocs est X, soit

⋃_{Y ∈P} Y = X

(P est un recouvrement)

– P est formé de parties disjointes deux à deux, soit

(∀ Y_{1},Y_{2} ∈ P)(Y_{1} ≠ Y_{2} ⟹ Y_{1} ∩ Y_{2} = ∅).

L’ensemble des partitions de X en k blocs est noté ici S(X,k). Son cardinal ne dépendant que de celui de X, on pose S_{2}(card(X),k) = card(S(X,k)) (nombre de Stirling de deuxième espèce).

1) Montrer que S(∅,0) = {∅} et S(∅,k) = ∅ si k ≠ 0. En déduire les nombres S_{2}(0,k).

2) Montrer que, pour k ≥ 1,

S_{2}(n + 1,k) = S_{2}(n,k − 1) + kS_{2}(n,k).  (1)

Indication. Soit X un ensemble à n + 1 éléments et x_{0} ∈ X, définir une surjection

S(X,k) ↦ S(X − {x_{0}},k) ∪ S(X − {x_{0}},k − 1)

en “enlevant” x_{0} dans une partition. Analyser les fibres de cette surjection et conclure.

3) a) Montrer que, pour n ≥ 1, S_{2}(n,0) = 0.

b) Expliquez pourquoi la donnée des S_{2}(n,0), S_{2}(0,k) (calculés précédemment) et de la récurrence (1) permet de construire toute la matrice de Stirling (S_{2}(n,k))_{n,k≥0}.

c) Montrer, avec les seules données du (b), que, pour tout n, S_{2}(n,n) = 1 et S_{2}(n,k) = 0 pour k > n.

4) Montrer que

S_{2}(n + 1,k + 1) = ∑_{j=0}^{n−k} ( \begin{matrix}n \\ j \end{matrix} ) S_{2}(n − j,k).  (2)

∗ Prière de signaler les erreurs à gd etu[at]yahoo.fr en mettant Mada07 en objet.

1. L’ensemble des parties de X est noté 𝔓(X) [1].

Indication. Même technique que ci-dessus, définir une bijection

S(X,k + 1) ↦ ∪_{{x_{0}}⊂J⊂X}S(X − J,k)

cette fois en “enlevant” le bloc contenant x_{0} dans une partition. Analyser l’image de cette bijection et conclure.

5) a) Soit T = ∑_{n,k≥0} S_{2}(n,k)\frac{x^{n}}{n!} y^{k}, la série génératrice mixte des nombres S_{2}(n,k). Montrer, à l’aide de (2) que

T e^{x} = \frac{1}{y} \frac{∂}{∂x}(T)  (3)

b) En intégrant (3) et en utilisant les conditions initiales, montrer que

T = e^{y(e^{x}−1)} .

Familles sommables. —

Exercice 1.2 Soit F_{n} définie par F_{0} = 0, F_{1} = 1, F_{n+2} = F_{n+1} + F_{n}.

1) a) Montrer que

∑_{n≥0} F_{n}z^{n} = \frac{z}{1 − z − z^{2}}

b) Montrer (avec soin) que la famille (z(z + z^{2})^{n})_{n≥0} est sommable. Quelle est sa somme? (justifiez)

2) a) Déduire de ce qui précède que, pour tout n ∈ ℕ

F_{n} = ∑_{k≥0} ( \begin{matrix}n − 1 − k \\ k \end{matrix} )

b) Quel est le support de cette somme? la réécrire avec les bornes les plus serrées possibles.

Exercice 1.3 Soit M ∈ ℂ^{ℕ×ℕ}, une matrice infinie à coefficients complexes et x,y deux indéterminées.

1) a) Montrer que la famille

(( ∑_{n≥0} M[n,k]x^{n})y^{k})_{k≥0}

est sommable dans ℂ[[x,y]].

b) De même montrer que

(( ∑_{k≥0} M[n,k]y^{k})x^{n})_{n≥0}

est sommable dans ℂ[[x,y]].

2) Montrer que

∑_{n,k≥0} M[n,k] x^{n} y^{k} = ∑_{k≥0} ∑_{n≥0} M[n,k] x^{n} y^{k} = ∑_{n≥0} ∑_{k≥0} M[n,k] x^{n} y^{k}

3) Appliquer ces résultats pour montrer que, si l’on note I(n,k) le nombre d’applications idempotentes [1..n] ↦ [1..n] qui ont k points fixes, on a

∑_{n,k≥0} I[n,k]\frac{x^{n}}{n!} y^{k} = e^{ye^{x}}

Exercice 1.4 (“Tablettes de Chocolat”) Une tablette de chocolat sera ici un rectangle de p × q cases (largeur p ≥ 1 et hauteur q ≥ 1), elle est caractérisé par ces deux paramètres. Sa surface est s = pq et son demi-périmètre sera l = p+q−1. On compte le nombre a_{l,s} de tablettes de demi-périmètre l (resp. surface s) donné et on considère la série génératrice

T := ∑_{s,l≥1} a_{l,s}x^{l}y^{s}  (4)

1) a) Montrer que, pour tous l,s, on a a_{l,s} ≤ 2.

b) En déduire que la famille (x^{p+q−1}y^{pq})_{p,q≥1} est sommable et de somme T.

2) Montrer que la famille

(\frac{(xy)^{q}}{1 − (xy^{q})})_{q≥1}  (5)

est sommable dans ℂ[[x,y]] et de somme T.

3) (Partie machine, intéressante à faire mais non exigible à l’examen).

a) Vérifier que Maple ne sait pas convertir la somme

∑_{q≥1} \frac{(xy)^{q}}{1 − (xy^{q})}  (6)

en une fonction standard. b)Montrer que si l’on veut le terme a_{l,s}, il suffit de calculer la somme jusqu’à q = s. En désuire un algorithme de calcul de a_{l,s}.

Références

[1] Bourbaki, N., Theorie des ensembles, Hermann.

[2] Comtet, L., Analyse Combinatoire, PUF.