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

Cours d’Informatique —Licence Informatique—

Exercice 1. (Surjections) On appelle S_{k}^{n} le nombre de surjections d’un ensemble à n éléments dans un ensemble à k éléments.

1. calculer S_{k}^{n} pour k = 0, 1, 2 et k = n − 1, n;

2. montrer que

∑_{l=0}^{k} \binom{k}{l}S_{l}^{n} = k^{n} .

3. écrire les formules précédentes avec la matrice M

( \begin{matrix}( & {0 \atop 0} & ) \\ \binom{1}{0} & \binom{1}{1} \\ ⋮ & ⋮ & ... \\ \binom{n}{0} & \binom{n}{1} & ⋯ & \binom{n}{n} \end{matrix} )

4. inverser la matrice M en considérant l’endomorphisme U de polynômes défini par U(P)(X) = P (X + 1).

5. donner une formule pour S_{k}^{n}.

Exercice 2. (Partitions) On appelle M_{n} le nombre de partitions d’un ensemble à n éléments.

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 3. (Analyse d’un algorithme de tri) Un algorithme de tri est basé sur le principe “diviser pour règner”. Ainsi pour trier n objets, on les divise en deux sous ensembles de tailles ⌈n/2⌉ et ⌊n/2⌋. Chaque sous-ensemble est trié récursivement avec la même méthode. Après cela, on a besoin d’au plus n − 1 nouvelles comparaisons pour terminer le tri. Le nombre total de comparaisons effectuées est donc au plus f(n) où f est définie par

\{ \begin{matrix}f(1) = 0 \\ f(n) = f (⌈n/2⌉) + f (⌊n/2⌋) + n − 1 \end{matrix}

1. calculer f(n) pour 2 ≤ n ≤ 10 ;

2. soit g la fonction définie par g(n) = ∑_{k=1}^{n} ⌈log_{2}(k)⌉; Calculer g(n) pour 2 ≤ n ≤ 10 ;

3. trouver une expression simple pour g(2^{p}) puis pour g(n) ;

4. montrer que g(n) = f(n).

Exercice 4. (Problème des rencontres—Montmort 1708) Soit d(n) le nombre de permutations σ = σ(1)σ(2) … σ(n) de n entiers telles que σ(i) ≠ i pour tout i (σ s’appelle un dérangement). On pose par convention d(0) = 1.

1. montrer que n! = ∑_{k=0}^{n} \binom{n}{k}d(n − k) ;

2. en déduire la série génératrice g(t) = ∑_{n=0}^{∞} \frac{d(n)}{n!} t^{n};

3. calculer g(t) e^{t}. En déduire une formule explicite de g(t) et la formule

d(n) = n! (1 − \frac{1}{1!} + \frac{1}{2!} − ⋯ + \frac{(−1)^{n}}{n!} ) ;

4. calculer lim_{n→∞} \frac{d(n)}{n!}.

Exercice 5. (Petit théorème de Fermat) Soit p un nombre premier.

1. montrer que pour k ∈ \{1, 2, …, p − 1\}, le coefficient binomial \binom{p}{k} est divisible par p;

2. en déduire que (a + b)^{p} ≡ a^{p} + b^{p}[p] pour tout entier a et b;

3. en déduire le “petit théorème de Fermat” : a^{p} ≡ a[p] pour tout entier a;

4. quel est le chiffre des unités dans l’écriture 2^{1000000} en base 7.