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

Cours d’Informatique —Licence Informatique—

Exercice 1. Donner les complexités en nombre d’opérations des bouts de code suivants :

1. for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
      fonction(i,j);
2. for(i=1;i<=n;i++)
    for(j=1;j<=i;j++)
      for(k=1;k<=j;k++)
        fonction(i,j,k);

Exercice 2. 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 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. Exercice 6. (Base de Fibonacci)

1. Montrer que pour tout entier n > 0, il existe une suite croissante finie i_{1} < i_{2} < ⋯ < i_{k}

d’indices, telle que

n = F_{i_{k}} + ⋯ + F_{i_{2}} + F_{i_{1}}.

2. Montrer qu’il y a unicité de la suite si l’on impose (a) i_{1} ≥ 1 ;

(b) i_{k} − i_{k−1} ≥ 2.