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

— Licence Informatique —

▶ Exercice 1 On note \binom{n}{k}, le nombre de parties à k éléments d’un ensemble à n éléments. 1. Montrer que \binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1};

2. Donner une interprétation combinatoire de cette formule;

3. Montrer que \binom{n}{k} + 2\binom{n}{k+1} + \binom{n}{k+2} = \binom{n+2}{k+2};

4. Donner une interprétation combinatoire de cette formule; ▶ Exercice 2 Calculer le nombre de parties d’un ensemble à n éléments

1. par récurrence;

2. en utilisant les fonctions caractéristiques. ▶ Exercice 3 Calculer les sommes suivantes :

1. ∑_{k=0}^{n} \binom{n}{k};

(a) par récurrence;

(b) en développant le polynôme (1 + x)^{n};

(c) en donnant une interprétation combinatoire.

2. ∑_{k=0}^{n}(−1)^{k}\binom{n}{k};

3. ∑_{k=0}^{n} k\binom{n}{k};

(a) par récurrence;

(b) en utilisant le polynôme (1 + x)^{n};

(c) en donnant une interprétation combinatoire.

4. ∑_{k=0}^{n} \frac{1}{k + 1}\binom{n}{k};

5. ∑_{k=0}^{n} \binom{n − k}{k};

6. ∑_{m=k}^{n} \binom{m}{k};

7. ∑_{m=k}^{n} \binom{m}{m − k}.

▶ Exercice 4 Calculer les sommes suivantes :

1. ∑_{k=0}^{n} \binom{n}{k}^{2};

(a) en étudiant le coefficient de x^{n} dans le polynôme (1 + x)^{2n};

(b) en donnant une interprétation combinatoire. ▶ Exercice 5 On note f^{(n)} la dérivée d’ordre n d’une fonction. Par définition, on a f^{(0)} = f et f^{(n+1)} = (f^{(n)})′. On rappelle la formule pour la dérivée d’un produit : (fg)′ = f′g + fg′.

1. Donner des expressions de (fg)^{(n)} pour n = 2, 3, 4, 5;

2. Généraliser et démontrer. Cette formule est due à Leibniz.