Travaux Dirigés de Structures Discrètes n^{o} 6

— Licence Informatique —

▶ Exercice 1 (Nombres de Fibonacci) On appelle F_{n} le n-ième nombre de Fibonacci : F_{0} = F_{1} = 1 et F_{n+2} = F_{n+1} + F_{n}

1. Montrer que

f(z) = ∑_{k=0}^{∞} F_{k}z^{k} = \frac{1}{1 − z − z^{2}} .

2. On definit la suite G_{n} par

∀ n ≥ 0 G_{n} = F_{2n} .

Établir une relation de récurrence vérifiée par les G_{n}.

3. En déduire que

g(z) = ∑_{k=0}^{∞} G_{k}z^{k} = \frac{1 − z}{1 − 3z + z^{2}} .

4. Retrouver ce résultat en utilisant f(z). ▶ Exercice 2 (Nombres de Catalan) On appelle C_{n} le nombre d’arbres binaires à n nœuds.

1. Calculer C_{1}, C_{2} et C_{3} ;

2. Montrer que pour n ≥ 0

C_{n+1} = ∑_{k=0}^{n} C_{k}C_{n−k} .

3. En déduire une expression de b(z) = ∑_{n=0}^{∞} C_{n}z^{n}

4. En utilisant le développement en série entière de (1 + x)^{1/2}, établir la formule

b(z) = ∑_{n=0}^{∞} \frac{1}{n + 1}\binom{2n}{n}z^{n} .

▶ Exercice 3 (Partitions) On appelle M_{n} le nombre de partitions d’un ensemble à n éléments (par convention M_{0} = 1).

1. Calculer M_{1}, M_{2} et M_{3} ;

2. Montrer que pour n ≥ 0

M_{n} = ∑_{k=1}^{n} \binom{n − 1}{k − 1}M_{n−k} .

3. En déduire la formule

∑_{n=0}^{∞} \frac{M_{n}t^{n}}{n!} = e^{e^{t}−1} .

4. Trouver une relation entre M_{n} et le nombre S_{k}^{n} de surjections d’un ensemble à n éléments dans un ensemble à k éléments.

▶ Exercice 4 Montrer que

∑_{m,n≥0} \binom{m + n}{m}x^{m}y^{n} = \frac{1}{1 − x − y} .

▶ Exercice 5 Montrer que la série génératrice de la fonction min qui à un couple d’entiers associe le plus petit des deux (min(5, 3) = 3 et min(4, 4) = 4) est donnée par

∑_{m,n≥0} min(m, n)x^{m}y^{n} = \frac{xy}{(1 − x)(1 − y)(1 − xy)} .

▶ Exercice 6 Montrer que la série formelle u définie par

u(z) = z + z^{2} + z^{4} + z^{8} + z^{16} + ⋯ = ∑_{n=0}^{∞} z^{2^{n}}

vérifie l’équation suivante

u(z) = u(z^{2}) + z .

▶ Exercice 7 Pour un entier positif n, on note V (n) le nombre de 1 dans l’écriture binaire de n. On a par exemple V (0) = 0, V (4) = 1 et V (13) = 3.

1. Montrer que pour tout entier n, on a

V (2n) = V (n)
V (2n + 1) = V (n) + 1 .

2. Montrer que la fonction génératrice v(z) = ∑_{n=0}^{∞} V (n)z^{n} vérifie l’équation suivante

v(z) = (1 + z)v(z^{2}) + \frac{z}{1 − z^{2}} .

▶ Exercice 8 On note J(n) la fonction de Josephus (cf. feuille de TD no 4). Montrer que la série formelle j(z) = ∑_{n=0}^{∞} J(n)z^{n} vérifie l’équation suivante

j(z) = 2(1 + z)j(z^{2}) − \frac{1}{1 + z} .