Exercice 1 1529 Correction

Soient $E$ et $F$ deux ensembles finis de cardinaux respectifs $n$ et $p$ .
Combien y a-t-il d’injections de $E$ dans $F$ ?

Solution

Si $n > p$ , il n’y a pas d’injections possibles.
Si $n = 0$ , il y a une injection: l’application vide.
Si $0 < n \leq p$ alors on peut écrire $E = {x_{1}, \dots, x_{n}}$ avec les $x_{i}$ deux à deux distincts.
Pour former une injection de $E$ dans $F$ :
On choisit $f (x_{1})$ dans $F$ : $p$ choix.
On choisit $f (x_{2})$ dans $F ∖ {f (x_{1})}$ : $p - 1$ choix.
…
On choisit $f (x_{n})$ dans $F ∖ {f (x_{1}), \dots, f (x_{n - 1})}$ : $p - n + 1$ choix.
Au total, il y a $p \times (p - 1) \times \dots \times (p - n + 1) = \frac{p!}{(p - n)!}$ choix.

Exercice 2 1531 Correction

Combien existe-t-il de relation d’ordre total sur un ensemble $E$ à $n$ éléments?

Solution

Une relation d’ordre total sur $E$ permet de définir par numérotation des éléments, une bijection de ${1, \dots, n}$ vers $E$ et inversement.

Par suite, il y a exactement $n!$ relations d’ordre total possibles.

Exercice 3 1530 Correction

Soient $E = {1, \dots, n}$ et $F = {1, \dots, p}$ avec $n, p \in ℕ ∖ {0,1}$ .

(a)

Combien y a-t-il d’applications constantes de $E$ vers $F$ ?
(b)

Combien y a-t-il d’applications strictement croissantes de $E$ vers $F$ ?
(c)

Combien y a-t-il d’applications strictement monotones de $E$ vers $F$ ?
(d)

Combien y a-t-il d’applications croissantes de $E$ vers $F$ ?
(e)

Combien y a-t-il d’applications monotones de $E$ vers $F$ ?

Solution

(a)

Une application constante de $E$ vers $F$ est entièrement déterminée par le choix de la valeur de sa constante dans $F$ . Il y a $p$ choix possibles et donc $p$ applications constantes de $E$ vers $F$ .
(b)

Une application $f : E \to F$ strictement croissante est entièrement déterminée par son image qui est une partie formée de $n$ éléments de $F$ : il suffit d’ordonner les $n$ éléments qui constituent cette image pour définir l’application strictement croissante associée.

Si $p \geq n$ : il y a $(\binom{p}{n})$ parties à $n$ éléments dans $F$ et donc autant d’applications strictement croissantes de $E$ vers $F$ .

Si $p < n$ : il n’y a pas de parties à $n$ éléments dans $F$ et donc pas d’applications strictement croissantes de $E$ vers $F$ . Cela correspond encore à la valeur de $(\binom{p}{n})$ .
(c)

Par le même raisonnement, il y autant d’applications strictement décroissantes que d’applications strictement croissantes. De plus, les applications strictement croissantes sont distinctes des applications strictement décroissantes. Au total, il y a $2 (\binom{n}{p})$ applications strictement monotones de $E$ vers $F$ .
(d)

À une application $f : E \to F$ , on associe $g : E \to G$ définie par

$\forall k \in ⟦ 1; n ⟧, g (k) = f (k) + k - 1 avec G = {1, \dots, p + n - 1}$

Par cette association, on fait se correspondre de façon bijective les applications croissantes de $E$ vers $F$ et les applications strictement croissantes de $E$ vers $G$ . Il y a donc $(\binom{n + p - 1}{n})$ applications croissantes de $E$ vers $F$ .
(e)

En composant une application à valeurs dans $F$ avec l’application $h : F \to F$ donnée par $h (k) = p + 1 - k$ , on fait se correspondre de façon bijective les applications croissantes de $E$ vers $F$ et les applications décroissantes de $E$ vers $F$ . Il y a donc exactement $(\binom{n + p - 1}{n})$ applications décroissantes de $E$ vers $F$ . Aussi, les applications à la fois croissantes et décroissantes de $E$ vers $F$ sont les applications constantes, il y en a $p$ . Au final, il y a

$2 (\binom{n + p - 1}{n}) - p$

applications monotones de $E$ vers $F$ .

Exercice 4 4437

Soient $n \in ℕ$ , $p \in ℕ^{*}$ et $E = ⟦ 1; n ⟧$ .

(a)

Dénombrer les familles strictement croissantes $(x_{1}, \dots, x_{p})$ d’éléments de $E$ .
(b)

Dénombrer les familles croissantes $(x_{1}, \dots, x_{p})$ d’éléments de $E$ .

Exercice 5 3933 Correction

(a)

Quel est le coefficient de $a^{2} b^{5} c^{3}$ dans le développement de ${(a + b + c)}^{10}$ ?
(b)

Même question avec $a_{1}^{k_{1}} a_{2}^{k_{2}} \dots a_{p}^{k_{p}}$ dans ${(a_{1} + a_{2} + \dots + a_{p})}^{n}$ .

Solution

(a)

Dans le développement de

${(a + b + c)}^{10} = (a + b + c) (a + b + c) \dots (a + b + c)$

on obtient un terme $a^{2} b^{5} c^{3}$ en choisissant deux $a$ , cinq $b$ et trois $c$ .
Il y a $(\binom{10}{2})$ choix possibles pour les facteurs dont seront issus les $a$ .
Une fois ceux-ci choisis, il y a $(\binom{8}{5})$ choix possibles pour les facteurs fournissant les $b$ .
Une fois ces choix faits, les trois facteurs restant fournissent les $c$ .
Au total, il y a

$(\binom{10}{2}) (\binom{8}{5}) = \frac{10!}{2! 5! 3!} = 2520$

termes $a^{2} b^{5} c^{3}$ apparaissant lors du développement de ${(a + b + c)}^{10}$ .
(b)

On reprend le même protocole, pour obtenir

$\frac{n!}{k_{1}! k_{2}! \dots k_{p}!}$

si $k_{1} + k_{2} + \dots + k_{p} = n$ et 0 sinon.

Exercice 6 4438

(Anagrammes)

Un mot $M$ long de $n$ lettres est constitué de $r$ lettres différentes. La $j$ -ème lettre apparaît $p_{j}$ fois dans le mot $M$ et donc $p_{1} + \dots + p_{r} = n$ .

(a)

Combien d’anagrammes différentes du mot $M$ peut-on écrire?
(b)

Dans le développement de ${(a_{1} + a_{2} + \dots + a_{r})}^{n}$ , quel est le coefficient du terme $a_{1}^{p_{1}} a_{2}^{p_{2}} \dots a_{r}^{p_{r}}$ ?

Exercice 7 4440

(Nombres de combinaisons avec répétition)

On appelle combinaison avec répétition de longueur $p$ formée d’éléments d’un ensemble $E$ , le choix non ordonné de $p$ éléments dans $E$ avec possibilité de répétitions de ceux-ci¹¹ 1 Par exemple, les choix de $1,1,2$ ou de $1,2,1$ définissent la même combinaison avec répétition de longueur $3$ formée d’éléments de ${1,2,3,4}$ .. Combien peut-on former de combinaisons avec répétition de longueur $p$ sur un ensemble à $n \geq 1$ éléments?

Exercice 8 1536 Correction

Soit $E$ un ensemble à $n$ éléments.

(a)

Soit $X$ une partie à $p$ éléments de $E$ .
Combien y a-t-il de parties $Y$ de $E$ disjointes de $X$ ?
(b)

Combien y a-t-il de couples $(X, Y)$ formés de parties disjointes de $E$ ?

Solution

(a)

Autant que de parties de $E ∖ X$ : $2^{n - p}$
(b)

$\sum_{p = 0}^{n} (\binom{n}{p}) 2^{n - p} = {(1 + 2)}^{n} = 3^{n}$ .

Exercice 9 1538 Correction

Soit $A$ une partie d’un ensemble $E$ à $n$ éléments. On pose $p = Card (A)$ .

(a)

Combien y a-t-il de parties $X$ de $E$ contenant $A$ ?
(b)

Combien y a-t-il de parties $X$ de $E$ à $m \in {p, \dots, n}$ éléments contenant $A$ ?
(c)

Combien y a-t-il de couples $(X, Y)$ de parties de $E$ tels que $X \cap Y = A$ ?

Solution

(a)

Il y en a autant que de parties de $E ∖ A$ : $2^{n - p}$
(b)

Il y en a autant que de parties de $E ∖ A$ à $m - p$ éléments: $(\binom{n - p}{m - p})$ .
(c)

Une fois $X$ à $m$ éléments contenant $A$ déterminé, il y a $2^{n - m}$ choix de $Y$ possibles. On obtient un total de couples de:

$\sum_{m = p}^{n} (\binom{n - p}{m - p}) 2^{n - m} = \sum_{k = 0}^{n - p} (\binom{n - p}{k}) 2^{n - p - k} = {(1 + 2)}^{n - p} = 3^{n - p} .$

Exercice 10 1537

Soit $E$ un ensemble à $n \in ℕ$ éléments. Combien existe-t-il de couples $(X, Y)$ constitués de parties de $E$ vérifiant $X \subset Y$ ?

Exercice 11 1532 Correction

On trace dans un plan $n$ droites en position générale (c’est-à-dire deux d’entre elles ne sont jamais parallèles ni trois d’entre elles concourantes). Combien forme-t-on ainsi de triangles?

Solution

Notons $t_{n}$ le nombre de triangles formés.

t_{0} = t_{1} = t_{2} = 0 .

Pour $n \geq 3$ , former un triangle revient à choisir les trois droites définissant ses côtés:

il y a (\binom{n}{3}) possibilités.

Chacune de ses possibilités définit un véritable triangle (car il y a ni concourance, ni parallélisme) et les triangles obtenus sont deux à deux distincts.

Finalement,

t_{n} = (\binom{n}{3}) .

Exercice 12 1540 Correction

Combien y a-t-il de $p$ -cycles dans le groupe $(𝒮_{n}, \circ)$ ?

Solution

Une injection $f$ de $ℕ_{p}$ dans $ℕ_{n}$ permet de définir le $p$ -cycle $(f (1) \dots f (p))$ .
Inversement, un $p$ -cycle de $ℕ_{n}$ peut être définis par exactement $p$ injections différentes.
En vertu du principe des bergers, il y a exactement $\frac{n!}{p (n - p)!}$ $p$ -cycles dans $𝒮_{n}$ .

[<] Ensemble fini [>] Dénombrements élémentaires

Édité le 29-08-2023

Listes et combinaisons