Chapitre 7 : Entiers naturels, ensembles finis et dénombrement

Questions de cours

1. Citer les 3 axiomes de $\mathbb{N}$.

On postule l'existence d'un ensemble non vide, noté $\mathbb{N}$ ensemble des entiers naturels dont les propriétés fondamentales sont :

1. Toute partie non vide de $\mathbb{N}$ possède un plus petit élément.

2. Toute partie non vide et majorée de $\mathbb{N}$ possède un plus grand élément.

3. $\mathbb{N}$ n'est pas majoré.

2. Que dire d'une partie infinie de $\mathbb{N}$ ?

Une partie infinie de $\mathbb{N}$ est en bijection avec $\mathbb{N}$

3. Comment montrer que des ensembles finis sont égaux via les cardinaux ?

Théorème :

Soient $A$ et $B$ des ensembles finis.
Alors $|A|=|B|$ ssi $A\sim B$ i.e. il existe une bijection de $A$ dans $B$.
Inclusion : $E$ désigne un ensemble fini.

Si $A\subset E$, alors $A$ est fini et $|A|\leq |E|$
En particulier : $$\left.\begin{array}{c} A\subset E\\ |A|=|E| \end{array}\right\rbrace \Rightarrow A=E$$

4. Cardinal de l'union (inégalité). Cas d'une union disjointe. Égalité dans le cas de deux ensembles.

Théorème : Propriétés

1. Une partie $A$ d'un ensemble fini $E$ est finie et $\text{card}(A)\leq\text{card}(E)$ avec égalité ssi $A=E$
2. Une réunion finie d'ensembles finis est un ensemble fini et $$\text{card}\left( \bigcup_{i=1}^n A_i \right) \leq \sum_{i=1}^n\text{card}(A_i)$$ avec égalité ssi les $A_i$ sont deux à deux distincts.

On écrit $\displaystyle{} \bigcup_{i=1}^nA_i = \bigsqcup_{i=1}^n A_i$

5. Définition d'une partition d'un ensemble, d'une union disjointe.

Définition : Partition d'un ensemble

Si $\displaystyle{}E = \bigsqcup_{i\in I}A_i$, alors les $\displaystyle{}(A_i)_{i\in I}$ forment une partition de $E$.

Définition : Partition d'une union disjointe

Si $E$ et $F$ sont des ensembles et $f : E\to F$ est une application quelconque, alors $$E = \bigsqcup_{y\in F}f^{-1}(\{y\})$$

6. Cardinal du produit cartésien.

Théorème : Propriété

Un produit fini d'ensemble finis est fini et $$\text{card}\left( \prod_{i=1}^n A_i \right) = \prod_{i=1}^n\text{card}(A_i)$$

7. Quel est l'effet d'une application sur les cardinaux finis ? À quelle condition a-t-on égalité des cardinaux de la source et de l'image ?

Théorème :

Soient $E$ un ensemble fini, $F$ un ensemble quelconque et $f\in \mathscr{F}(E,F)$
Alors $f(E)$ est fini et $\text{card}(f(E))\leq\text{card}(E)$ avec égalité ssi $f$ est inj.

8. Que dire sur les cardinaux si $f : E\to F$ est une surjection ? injection ?

Corollaire :

1. Si $E \hookrightarrow F$ et si $F$ est fini alors $E$ est fini et $|E|\leq |F|$
2. Si $E F$ et si $E$ est fini alors $F$ est fini et $|F|\leq |E|$

9. SAVOIR REFAIRE : montrer que si $E$ et $F$ ont le même cardinal, et si $f : E\to F$, alors $f$ est bijective ssi elle est injective ssi elle est surjective.

Théorème :

Soient $E$ et $F$ des ensembles finis de même cardial.
On se donne $f = E\to F$ quelconque.
Alors $f$ est injective (1) $\Leftrightarrow$ $f$ est surjective (2).

Preuve :

(1) $\Rightarrow$ (2) : on suppose que $f$ est injective. Montrons que $f$ est surjective.
$\displaystyle{}f|_{E}^{f(E)}$ est bijective (par construction à l'image).
Donc $|f(E)| = |E|$
Or par hypothèse $|E|=|F|$
Ainsi $f(E)\subset F$ et $|f(E)| = |F|$
Donc $f(E) = F$
Donc $f$ est surjective.

(2) $\Rightarrow$ (1) : réciproquement, supposons que $f$ est surjective. Montrons que $f$ est injective.
On a $f(E) = F$
Or $|F|=|E|$
Donc $|f(E)| = |E|$
D'après le théorème, $f$ est donc injective.

10. Pour $E$ et $F$ des ensembles finis, quel est le cardinal de $\mathscr{F}(E,F)$ ?

Théorème :

Soient $E$ et $F$ des ensembles finis.
Alors $\mathscr{F}(E,F)$ est fini et $$\text{card}(\mathscr{F}(E,F)) : (\text{card}(F))^{\text{card}(E)}$$

11. SAVOIR REFAIRE : prouver que si $E$ est un ensemble fini, alors $\text{card}(\mathscr{P}(E))=...$

Théorème :

Soit $E$ un ensemble fini. Alors $\mathscr{P}(E)$ et fini, et $$\text{card}(\mathscr{P}(E)) = 2^{\text{card}(E)}$$

Preuve :

$\begin{array}{lccl} \text{On envisage } \Phi : & \mathscr{P}(E) & \to & \mathscr{F}(E,\{0,1\})\\ & A & \mapsto & 𝟙_A \end{array}$
Il suffit de montrer que $\Phi$ est bijective.
En effet, d'après le théorème précédent, $\mathscr{F}(E,\{0,1\})$ est fini de cardinal $2^{\text{card}(E)}$.

Montrons que $\Phi$ est injective :
Soient $A$ et $B$ dans $\mathscr{P}(E)$ tq $\Phi(A) = \Phi(B)$
Alors $𝟙_A = 𝟙_B$, donc $A=B$ (cf. propriétés des fonctions indicatrices)
Donc $\Phi$ est injective.

Montrons que $\Phi$ est surjective.
Soit $f\in\mathscr{F}(E,\{0,1\})$
On cherche une paire $A$ de $E$ tq $f = 𝟙_A$
On pose $A = f^{-1}(\{1\})$ (préimage) i.e. $A = \{x\in E, f(x) = 1\}$
Par construction, $f$ ne prenant que les valeurs 0 ou 1 :
Si $x\in A$, alors $f(x) = 1$
Si $x\not\in A$, alors $f(x)=0$
Donc $f = 𝟙_A$
Alors $f = \Phi(A)$ ($A$ est un antécédent de $f$ par $\Phi$)
Donc $\Phi$ est surjective.

Conclusion : $\Phi$ est bijective, d'où le résultat.

12. Définir la fonction indicatrice d'un ensemble. Donner ses propriétés.

Définition :

Si $A\subset E$, alors on appelle fonction indicatrice de la partie $A$, la fonction $$\begin{array}{lccl} 𝟙_A : & E & \to & \{0;1\}\\ & x & \mapsto & 𝟙_A(x) = \left\lbrace \begin{array}{c} A\text{ si }x\in A\\ 0\text{ si } x\not\in A \end{array} \right. \end{array}$$

Théorème : Propriétés fondamentales

Soient $A$ et $B$ des parties de $E$

$𝟙_{\overline{A}} = 1-𝟙_A$
$𝟙_{A\cap B} = 𝟙_A\times 𝟙_B$ et $𝟙_{A\cup B} = 𝟙_A+𝟙_B - 𝟙_A\times 𝟙_B = 𝟙_A+𝟙_B - 𝟙_{A\cap B}$
$A\subset B \Leftrightarrow 𝟙_A\leq 𝟙_B$ et $A=B \Leftrightarrow 𝟙_A = 𝟙_B$
Lien avec le cardinal : Si $A$ est fini alors $$|A| = \sum_{x\in E}𝟙_A(x)$$

13. Donner le cardinal des permutations d'un ensemble $\text{card}(\sigma(E))=...$

Théorème :

Si $E$ est fini alors $\sigma(E)$ aussi et $$\text{card}(\sigma(E)) = |E|!$$

14. Qu'est ce qu'une $p$-liste d'un ensemble fini de $E$ ? Qu'est ce que cela modélise ?

Définition :

Soient $E$ un ensemble non vide, $p\in\mathbb{N}^*$
On appelle $p$-liste de $E$ ou $p$-uplet de $E$ tout élément de $E^p$ (produit cartésien)
Les $p$-listes sont des familles où l'ordre compte et les répétitions sont possibles. Elles modélisent des tirages successifs avec remise.

Théorème :

Il existe $|E|^p$ $p$-listes de $E$

15. Qu'est ce qu'un $p$-arrangement d'un ensemble fini $E$ ? Qu'est ce que cela modélise ?

Définition :

On appelle $p$-arrangement de $E$ tout $p$-lise d'éléments distincts de $E$
Les $p$-arrangements modélisent des tirages successifs sans remise.

16. Nombre de $p$-arrangement d'un ensemble à $n$ éléments. Rapport avec les injections ?

Théorème :

Soient $E$ un ensemble de cardinal $n\in\mathbb{N}^*$ et $p\in\mathbb{N}^*$
Alors,
1. Si $p\leq n$, il existe $\displaystyle{}A_n^p = \frac{n!}{(n-p)!}$ $p$-arrangements de $E$.
2. Si $p>n$, il n'en existe pas.

Corollaire :

On suppose que $|E|=p$, $|F|=n$
1. Si $p\leq n$, il existe $\displaystyle{}A_n^p = \frac{n!}{(n-p)!}$ injection de $E$ dans $F$.
2. Si $p>n$, il n'y en a pas.

Il existe le même nombre de $p$-arrangements que d'injections dans un ensemble.

17. Qu'est-ce qu'une $p$-combinaison d'un ensemble fini de $E$ ? Qu'est ce que cela modélise ?

Définition :

On appelle $p$-combinaison de $E$ tout sous-ensemble à $p$ élément de $E$.

Définition :

Si $n\in\mathbb{N}$, on note $\begin{pmatrix} n\\p \end{pmatrix}$ le nombre de $p$-combinaison d'un ensemble à $n$éléments.

C'est le nombre de parties à $p$-éléments d'un ensemble à $n$-éléments.
$\begin{pmatrix} n\\p \end{pmatrix}$ est le nombre de façons de choisir $p$ objets parmi $n$ objets.
Modélisent des tirages simultanés.

18. Définir proprement, puis exprimer en termes de factorielles le nombre de $p$-combinaison d'un ensemble à $n$ éléments. Donner une interprétation en termes de choix.

Théorème :

Choisir $p$ objets, c'est exactement choisir une partie à $p$-éléments d'un ensemble à $n$-éléments. $$\begin{pmatrix} n\\p \end{pmatrix} = \frac{n!}{p!(n-p)!}$$ On choisir l'ordre dans lequel on les place.
Au total $\begin{pmatrix} n\\p \end{pmatrix}\times p!$ $p$-arrangement de $E$

19. Rappeler les propriétés usuelles des combinaisons.

Théorème : Propriétés des combinaisons

1. $\begin{pmatrix} n\\n-p \end{pmatrix} = \begin{pmatrix} n\\p \end{pmatrix}$

2. $\begin{pmatrix} n\\p \end{pmatrix} + \begin{pmatrix} n\\p+1 \end{pmatrix} = \begin{pmatrix} n+1\\p+1 \end{pmatrix}$

3. Binôme de Newton $$(a+b)^n = \sum_{k=0}^n \begin{pmatrix} n\\k \end{pmatrix} a^kb^{n-k}$$ 4. $$\begin{pmatrix} n\\0 \end{pmatrix} = \begin{pmatrix} n\\n \end{pmatrix} = 1\hspace{20pt}\begin{pmatrix} n\\1 \end{pmatrix} = \begin{pmatrix} n\\n-1 \end{pmatrix} = n \hspace{20pt} \begin{pmatrix} n\\2 \end{pmatrix} = \begin{pmatrix} n\\n-2 \end{pmatrix} = \frac{n(n-1)}{2}$$

arrow_back arrow_forward