ΣThomaths
Cours & TD
Devoirs
Devoirs surveillés Devoirs maisons
Colles
Cours & TD
Devoirs
Devoirs surveillés Devoirs maisons Colles
Cours Feuille d'exercices
Cours TD Résumé
Sommaire
#15 Cours
Publié|12/11/2026 à 01:19
Dernière modification 30/10/2026 à 00:39
Dénombrement
Filières MPSIPCSI
Créé le 22/07/2026 à 12:16
Exercices 74
Type de feuille Cours
Position 1000
Importer des exercices
Bibmath DD Maths Ensemble fini DD Maths Listes et combinaisons DD Maths Dénombrements élémentaires DD Maths Dénombrements avancés DD Maths Composition d'un entier DD Maths Démonstrations combinatoires Bertault V Vuibert p. 919-934 Dunod p. 433-442
I) Cardinal d'un ensemble fini II) Dénombrement A - Principe du dénombrement B - Réunion et différence C - Produit cartésien, listes et arrangements D - Ensembles d'applications E - Combinaisons
Cours

Dénombrement

Cours

Introduction
Question de cours Non
Notes
Aperçu
Type Introduction
Référence —
Position 1000
Introduction + titre

Dans ce chapitre, on cherche à apprendre à dénombrer un ensemble, c’est-à-dire à compter son nombre d’éléments. On se concentre sur les méthodes de dénombrement et on omet, conformément au programme de MPSI, la plupart des démonstrations.

Sommaire

I) Cardinal d'un ensemble fini

Définition 1 — Ensemble fini/infini, cardinal d'un ensemble fini
Question de cours Non
Notes
Aperçu
Type Définition
Référence —
Position 4000
Définition 1 — Ensemble fini/infini, cardinal d'un ensemble fini

Soit $E$ un ensemble.

  • Ensemble fini/infini :    On dit que $E$ est $\Emph{fini}$ s'il existe une bijection de $\Intn{1}{n}$ sur $E$, pour un certain $n \in \N$. Dans le cas contraire, $E$ est dit $\Emph{infini}$.
  • Cardinal :    Si $E$ est fini, l'entier $n$ de la définition précédente est unique. On l'appelle le $\Emph{cardinal}$ de $E$, ou le $\Emph{nombre d'éléments}$ de $E$, et on le note $\abs{E}$ (ou $\Card{E}$ ou $\#E$).

En particulier, l'ensemble vide est fini et $\abs{\emptyset}=0$.

Exemple 2
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 5000
Exemple 2 + titre

Soient $m, n \in \mathbb{Z}$ deux entiers pour lesquels $m < n$. L'ensemble $\Intn{m}{n}$ est fini de cardinal $n-m+1$ car la fonction $k \mapsto k+m-1$ est bijective de $\Intn{1}{n-m+1}$ sur $\Intn{m}{n}$ et de réciproque $k \mapsto k-m+1$.

Définition 3 — Équipotence
Question de cours Non
Notes
Aperçu
Type Définition
Référence —
Position 6000
Définition 3 — Équipotence

On dit que deux ensembles $E$ et $F$ sont équipotents s'il existe une bijection de $E$ sur $F$. La relation d'équipotence est une relation d'équivalence.

Proposition 4 — Équipotence et cardinal
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 7000
Proposition 4 — Équipotence et cardinal

Soient $E$ et $F$ deux ensembles. Si $E$ est fini et si $E$ et $F$ sont équipotents, alors $F$ est fini et $\abs{E}=\abs{F}$.

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 8000
Démonstration

Comme $E$ est fini, il existe une bijection $f:\Intn{1}{n}\to E$ pour un certain $n \in \N$. Comme $E$ et $F$ sont équipotents, il existe une bijection $g:E\to F$. Alors $g\circ f:\Intn{1}{n}\to F$ est une bijection. Donc $F$ est fini et $\abs{F}=n = \abs{E}$.

Proposition 5 — Parties d'un ensemble fini
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 9000
Proposition 5 — Parties d'un ensemble fini

Soit $E$ un ensemble fini et $A$ une partie de $E$. Alors    $A$ est finie et $\abs{A} \leq \abs{E}$,    avec égalité si et seulement si $A = E$.

Raw Latex
Notes
Aperçu
Position 10000
Latex brut

Pour montrer que deux ensembles finis $A$ et $B$ sont égaux, on peut remplacer l'une des deux inclusions par la vérification de $\abs{A}=\abs{B}$.

Proposition 6 — Effet d'une application sur le cardinal
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 11000
Proposition 6 — Effet d'une application sur le cardinal

Soient $E$ et $F$ deux ensembles et $f : E \to F$ une application.

  1. Si $f$ est injective et si $E$ est fini, alors    $F$ est fini et $\abs{E} \leq \abs{F}$,    avec égalité si et seulement si $f$ est bijective.
  2. Si $f$ est surjective et si $E$ est fini, alors    $F$ est fini et $\abs{E} \geq \abs{F}$,    avec égalité si et seulement si $f$ est bijective.
  3. Si $E$ et $F$ sont finis de même cardinal : $$ f \text{ est bijective } \iff f \text{ est injective } \iff f \text{ est surjective.} $$
Raw Latex
Notes
Aperçu
Position 12000
Latex brut

Une application est injective si deux points distincts ont deux images distinctes. Cela n'est possible que s'il y a au moins autant d'éléments à l'arrivée qu'au départ, c'est-à-dire $\abs{E} \leq \abs{F}$.

Une application est surjective si tout élément de l'ensemble d'arrivée a au moins un antécédent. Cela n'est possible que s'il y a au moins autant d'éléments au départ qu'à l'arrivée, c'est-à-dire $\abs{F}\leq\abs{E}$.

Proposition 7 — Principe des tiroirs
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 13000
Proposition 7 — Principe des tiroirs

Quand on range $n+1$ chaussettes dans $n$ tiroirs, deux chaussettes au moins se retrouvent dans le même tiroir.

Raw Latex
Notes
Aperçu
Position 14000
Latex brut

Ranger $n+1$ chaussettes dans $n$ tiroirs revient à choisir une application d'un ensemble de cardinal $n+1$ dans un ensemble de cardinal $n$. Puisque $n+1>n$, cette application ne peut pas être injective : deux chaussettes au moins sont donc rangées dans le même tiroir --- d'où le résultat.

Exemple 8
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 15000
Exemple 8 + titre

Étant donnés $5$ points dans un carré de côté $2$, on peut toujours en trouver deux dont la distance est inférieure ou égale à $\sqrt{2}$.

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 16000
Démonstration

Découpons le carré en quatre carrés de côté $1$. Les $5$ points étant répartis dans ces $4$ carrés, le principe des tiroirs assure que deux d'entre eux au moins appartiennent au même petit carré. Or la distance maximale entre deux points d'un carré de côté $1$ est la longueur de sa diagonale, soit $\sqrt{2}$. Ces deux points sont donc distants d'au plus~$\sqrt{2}$.

Proposition 9 — Cardinal d'une partie à l'aide d'indicatrices
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 17000
Proposition 9 — Cardinal d'une partie à l'aide d'indicatrices

Pour tout ensemble fini $E$ et toute partie $A$ de $E$ : $\abs{A} = \Sum{x \in E}{} \one_A(x)$.

Raw Latex
Notes
Aperçu
Position 18000
Latex brut

Compter les éléments d'un ensemble $A$, c'est parcourir tous les éléments de $E$ et compter $1$ lorsque l'élément considéré appartient à $A$, et $0$ sinon.

II) Dénombrement

A - Principe du dénombrement

Raw Latex
Notes
Aperçu
Position 21000
Latex brut

Dénombrer, c'est compter. Lorsqu'un ensemble contient beaucoup d'éléments, il n'est pas envisageable de les énumérer un par un. Le dénombrement consiste précisément à développer des méthodes permettant de compter efficacement.

Pour dénombrer un ensemble, on peut commencer par se demander :

Comment construire un élément quelconque de cet ensemble ?

On peut alors décomposer sa construction en une succession de choix, et compter le nombre de possibilités à chaque étape.

Raw Latex
Notes
Aperçu
Position 22000
Latex brut

Imaginons que vous alliez au restaurant. Le menu du midi propose $4$ entrées, $2$ plats et $3$ desserts. Combien de menus différents peut-on composer ? Plutôt que de les écrire un par un, décomposons la construction d'un menu :

  • il faut d'abord choisir une entrée : $4$ possibilités ;
  • puis choisir un plat : $2$ possibilités ;
  • enfin choisir un dessert : $3$ possibilités.

À ce stade, une remarque est essentielle : ce qui compte n'est pas le choix effectué, mais le nombre de possibilités qu'il laisse pour la suite. Par exemple, que l'on ait choisi l'entrée $E_1$ ou l'entrée $E_2$, il reste dans les deux cas $2$ choix de plats, puis $3$ choix de desserts. On obtient donc $4\times2\times3=24$ menus différents.

Cependant, construire un objet par choix successifs n'est pas toujours aussi direct. Il faut parfois trouver une manière plus astucieuse de procéder.

Raw Latex
Notes
Aperçu
Position 23000
Latex brut

Considérons maintenant cinq lancers d'un dé, et cherchons le nombre de suites de résultats dans lesquelles le $6$ apparaît exactement deux fois, le $1$ exactement deux fois et le $4$ exactement une fois. On pourrait essayer de construire la suite lancer après lancer.

Pour le premier lancer, les seules valeurs compatibles avec la condition recherchée sont $1$, $4$ et $6$. Mais les possibilités pour les lancers suivants dépendent des résultats déjà obtenus, ce qui oblige à distinguer de nombreux cas. Par exemple, si les deux premiers lancers sont $6,6$, les trois suivants doivent être $1,1,4$, tandis que si les deux premiers sont $6,1$, il reste encore plusieurs possibilités pour la suite. Le dénombrement devient alors rapidement fastidieux.

Raw Latex
Notes
Aperçu
Position 24000
Latex brut

Il faut alors changer de point de vue.

Une telle suite est entièrement déterminée par les positions occupées par les deux $6$, puis par les positions occupées par les deux $1$. La position restante est alors nécessairement occupée par le $4$.

On peut donc commencer par choisir deux positions parmi les cinq pour y placer les $6$ : il y a $\binom{5}{2}$ possibilités. Il reste alors trois positions, parmi lesquelles on choisit les deux positions occupées par les $1$ : il y a $\binom{3}{2}$ possibilités. La dernière position est automatiquement occupée par le $4$. On obtient ainsi $\binom{5}{2}\times\binom{3}{2}=30$ suites possibles.

B - Réunion et différence

Proposition 10 — Cardinal d'une réunion, cardinal d'une différence
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 26000
Proposition 10 — Cardinal d'une réunion, cardinal d'une différence
  • Réunion :    $\abs{A \cup B} = \abs{A} + \abs{B} - \abs{A \cap B}$.    En particulier, si $A$ et $B$ sont disjoints :    $\abs{A \cup B} = \abs{A} + \abs{B}$.
    [6pt] Plus généralement, si $A_1, \ldots, A_n$ sont deux à deux disjoints :    $\abs{\mkern2mu \bigsqcup_{i=1}^n A_i} = \Sum{i=1}{n} \abs{A_i}.$
  • Différence : $\abs{A \setminus B} = \abs{A} - \abs{A \cap B}$.    En particulier, si $B \subset A : \hquad \abs{A \setminus B} = \abs{A} - \abs{B}$.
Raw Latex
Notes
Aperçu
Position 27000
Latex brut

L'idée derrière la formule de la réunion est simple : en additionnant $|A|$ et $|B|$, on compte deux fois les éléments communs, ceux de $A \cap B$.    Il faut donc les retrancher une fois pour compenser.

En revanche, dès que les ensembles sont disjoints, ce problème de double comptage disparaît : on additionne les cardinaux sans rien retrancher.    Ce cas particulier, décliné pour $n$ ensembles de même cardinal, porte même un petit nom :

Proposition 11 — Principe des bergers
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 28000
Proposition 11 — Principe des bergers

Toute réunion disjointe de $n$ ensembles de même cardinal $p$ est un ensemble de cardinal $np$.

Raw Latex
Notes
Aperçu
Position 29000
Latex brut

Bref, un berger qui possède $n$ moutons possède aussi $4n$ pattes de moutons !

C'est sans doute le principe que nous utiliserons le plus dans ce chapitre, car il correspond à une situation très fréquente~: un problème de dénombrement qui se décompose en deux étapes successives, «  étape 1  » offrant $n$ choix possibles, puis «  étape 2  » offrant $p$ choix possibles quel que soit le choix fait à l'étape 1.    Le problème complet admet alors $np$ solutions.

Exemple 12
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 30000
Exemple 12 + titre

Un cadenas à trois molettes, chacune graduée de $0$ à $9$, possède $10^3$ codes possibles : $10$ choix pour la première molette, puis $10$ pour la deuxième, puis $10$ pour la troisième, indépendamment des choix précédents.

Exemple 13
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 31000
Exemple 13 + titre

Combien y a-t-il de couples $(x,y)$ dans $\Intn{1}{n}^2$ pour lesquels $x \neq y$ ?

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 32000
Démonstration

Pour construire un tel couple, on peut d'abord choisir $x$, puis choisir $y$. Il y a $n$ valeurs possibles de $x$, et pour chacune de ces valeurs, $n-1$ valeurs restantes pour $y$ — donc en tout $n(n-1)$ couples possibles.

Exemple 14
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 33000
Exemple 14 + titre

À partir d'un alphabet de $p$ lettres, combien de mots de $n$ lettres peut-on former qui ne contiennent jamais deux lettres identiques consécutives ?

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 34000
Démonstration

Pour la première lettre, on peut choisir n'importe quelle lettre de l'alphabet ($p$ possibilités). Pour chacune des $n-1$ lettres suivantes, il faut éviter de répéter la précédente : il reste donc $p-1$ choix à chaque fois — d'où un total de $p(p-1)^{n-1}$ mots.

Exemple 15
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 35000
Exemple 15 + titre

Une urne contient $2n$ boules numérotées de $1$ à $2n$ qu'on tire successivement sans remise. Combien de tirages peut-on faire pour lesquels un numéro pair est toujours suivi d'un numéro impair et un numéro impair d'un numéro pair ?

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 36000
Démonstration

Les tirages à dénombrer sont de deux types : ceux qui commencent par un numéro pair et ceux qui commencent par un numéro impair. Nous allons dénombrer séparément ces deux ensembles de tirages et additionner à la fin les deux cardinaux obtenus.

  • Cas 1 : tirages commençant par un numéro pair. Faire un tel tirage consiste à tirer successivement :
    • une boule paire ($n$ possibilités),
    • puis une boule impaire ($n$ possibilités),
    • puis une boule paire restante ($n-1$ possibilités),
    • puis une boule impaire restante ($n-1$ possibilités),
    • \dots
    On obtient ainsi un total de $n \times n \times (n-1) \times (n-1) \times \dots \times 2 \times 2 \times 1 \times 1 = (n!)^2$ tirages.
  • Cas 2 : tirages commençant par un numéro impair. Un raisonnement analogue montre que $(n!)^2$ tirages exactement commencent par un numéro impair.

Le nombre total de tirages recherchés est donc $(n!)^2 + (n!)^2 = 2 \times (n!)^2. $

Raw Latex
Notes
Aperçu
Position 37000
Latex brut

Comment savoir s'il faut additionner ou multiplier ? Le réflexe à avoir :

$\begin{array}{cl} \text{\Og soit ceci, soit cela \Fg} & \Rightarrow \quad \textbf{Addition} \\ \text{\Og d'abord ceci, \textbf{puis} cela \Fg} & \Rightarrow \quad \textbf{Multiplication} \end{array}$

C - Produit cartésien, listes et arrangements

Proposition 16 — Cardinal d'un produit cartésien
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 39000
Proposition 16 — Cardinal d'un produit cartésien

Pour tous ensembles finis $E_1, \dots, E_p$,    $|E_1 \times \dots \times E_p| = |E_1| \times \dots \times |E_p|.$    En particulier, $|E|^p = |E^p|.$

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 40000
Démonstration

Construire un élément de $E_1 \times \dots \times E_p$, c'est choisir successivement un élément de $E_1$ ($|E_1|$ possibilités), puis un élément de $E_2$ ($|E_2|$ possibilités), \dots, puis un élément de $E_p$ ($|E_p|$ possibilités) — indépendamment des choix précédents. Le principe des bergers donne alors un total de $|E_1| \times \dots \times |E_p|$ éléments

Définition 17 — Liste
Question de cours Non
Notes
Aperçu
Type Définition
Référence —
Position 41000
Définition 17 — Liste

Soit $p \in \N^*$. On appelle p-liste de $E$ ou p-uplet de $E$ toute famille de $p$ éléments de $E$, i.e. tout élément de $E^p$.

Si on pose $n = |E|$, il existe $n^p$ p-listes de $E$.

Raw Latex
Notes
Aperçu
Position 42000
Latex brut

Une liste, c'est une famille et non un ensemble : l'ordre des éléments compte, et un même élément peut y figurer plusieurs fois.

C'est exactement ce qui se passe lors d'un tirage successif avec remise : on tire un élément, on le remet, on retire, etc. — d'où la modélisation des tirages successifs avec remise par des listes.

Exemple 18
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 43000
Exemple 18 + titre

Il y a $52^5$ façons de tirer 5 cartes successivement avec remise dans un jeu de 52 cartes.

Exemple 19
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 44000
Exemple 19 + titre

Un mot de passe est composé de 9 caractères, chacun choisi parmi 26 lettres. Combien de mots de passe contiennent, à des positions consécutives, la séquence MATHS ?

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 45000
Démonstration

Un mot de passe de 9 caractères ne peut contenir MATHS qu'une seule fois : si les 5 lettres qui le composent apparaissaient deux fois, il faudrait au moins 10 caractères pour les loger sans qu'elles se chevauchent. Pour construire un tel mot de passe, il suffit donc de :

  • choisir la position du bloc MATHS : le M initial peut se placer à n'importe laquelle des positions $1$ à $5$, soit $5$ possibilités ;
  • puis remplir les $4$ positions restantes avec des lettres quelconques, i.e. choisir une 4-liste de l'alphabet ($26^4$ possibilités).

D'où un total de $5 \times 26^4$ mots de passe.

Définition 20 — Arrangement
Question de cours Non
Notes
Aperçu
Type Définition
Référence —
Position 46000
Définition 20 — Arrangement

Soit $p \in \N^*$. On appelle p-arrangement de $E$ toute p-liste de $E$ d'éléments distincts.

Si on pose $n = |E|$, il existe $\frac{n!}{(n-p)!}$ p-arrangements de $E$ si $p \leq n$, et il n'en existe pas si $p > n$.

En particulier, pour $p = n$, on peut ordonner de $n!$ façons différentes exactement les $n$ éléments de $E$.

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 47000
Démonstration

Pour construire un p-arrangement dans le cas où $p \leq n$, on peut choisir un premier élément dans $E$ (n possibilités), puis un deuxième distinct du premier ($n-1$ possibilités), etc., enfin un p-ème distinct des précédents ($n - p + 1$ possibilités). D'où un total de $n \times (n-1) \times \dots \times (n - p + 1) = \frac{n!}{(n-p)!}$ arrangements de $E$.

Raw Latex
Notes
Aperçu
Position 48000
Latex brut

Les arrangements sont utilisés pour modéliser des tirages successifs sans remise — les répétitions sont interdites.

Exemple 21
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 49000
Exemple 21 + titre

De combien de façons peut-on tirer 5 cartes successivement sans remise dans un jeu de 52 cartes ? Il y a $52$ choix pour la première, $51$ pour la deuxième, etc. Ainsi, il y en a au total    $\dfrac{52!}{(52 - 5)!} = 52 \times 51 \times 50 \times 49 \times 48.$

Exemple 22
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 50000
Exemple 22 + titre

De combien de façons peut-on asseoir $n$ personnes sur un banc rectiligne ? Et autour d'une table ronde ? Dans les deux cas, ce qui compte pour chaque personne, c'est de savoir qui se trouve à sa gauche et à sa droite.

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 51000
Démonstration

Banc rectiligne : Numérotons les $n$ personnes de $1$ à $n$. Les asseoir sur un banc, c'est choisir dans quel ordre les énumérer de gauche à droite, i.e. se donner un $n$-arrangement de $\{1, \dots, n\}$ — d'où $n!$ configurations possibles.

Table ronde : Autour d'une table ronde, il n'y a en revanche pas de «  première place  » : faire glisser tout le monde d'un cran vers la droite ne change rien à la configuration. On peut donc asseoir arbitrairement une première personne, puis placer les $n-1$ autres de proche en proche autour d'elle, i.e. se donner un $(n-1)$-arrangement de $\{1, \dots, n-1\}$ — d'où $(n-1)!$ configurations possibles.

On peut retrouver ce résultat autrement. Chacune des $n!$ configurations rectilignes donne une configuration circulaire en joignant ses deux extrémités, mais ce procédé construit chaque configuration circulaire plusieurs fois : une configuration circulaire donnée provient exactement de $n$ configurations rectilignes distinctes, selon l'endroit où on la «  coupe  » pour la mettre en ligne. Il y a donc bien $\dfrac{n!}{n} = (n-1)!$ configurations circulaires.

D - Ensembles d'applications

Raw Latex
Notes
Aperçu
Position 53000
Latex brut

Une p-liste de $E$ n'est en fait rien d'autre qu'une application de $\Intn{1}{p}$ dans $E$ : à la p-liste $(x_1, \dots, x_p)$ correspond l'application $i \mapsto x_i$, et réciproquement, toute application $f$ de $\Intn{1}{p}$ dans $E$ redonne la p-liste $(f(1), \dots, f(p))$. Cette identification permet d'adapter directement les résultats du paragraphe précédent aux applications : les arrangements y jouent pour les applications le même rôle que les listes, mais du côté des injections.

Proposition 23 — Nombre d'applications entre deux ensembles
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 54000
Proposition 23 — Nombre d'applications entre deux ensembles

Soient $E$ et $F$ deux ensembles finis. On pose $p = |E|$ et $n = |F|$.

  1. Applications quelconques : $|F^E| = |F|^{|E|} = n^p$.
  2. Applications injectives : Une application injective de $E$ dans $F$ n'existe que si $p \le n$.
    Sous cette condition, l'ensemble des applications injectives de $E$ dans $F$ est de cardinal $\dfrac{n!}{(n-p)!}$.
  3. Bijections : Une bijection de $E$ sur $F$ n'existe que si $p = n$.
    L'ensemble des bijections de $E$ dans $F$ est alors de cardinal $n!$. En particulier, $|S_E| = |E|!$.
Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 55000
Démonstration
  1. Pour construire une application quelconque $f : E = \{e_1, \dots, e_p\} \to F$, il suffit de se donner une p-liste $(f(e_1), \dots, f(e_p))$ de $F$ et de poser $f : e_i \mapsto f(e_i)$ — d'où un total de $|F|^p = |F|^{|E|}$ applications.
  2. Pour construire une application injective, il suffit là encore de se donner une p-liste $(f(e_1), \dots, f(e_p))$ de $F$, mais l'injectivité impose que cette p-liste soit en fait un p-arrangement de $F$ — d'où un total de $\dfrac{n!}{(n-p)!}$ applications injectives si $p \le n$, et $0$ si $p > n$.
  3. Une application injective entre deux ensembles finis de même cardinal est automatiquement bijective. Le calcul de $|S_E|$ découle donc de (ii) en prenant $p = n = |E|$.
Exemple 24
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 56000
Exemple 24 + titre

Soit $n \ge 3$. Combien y a-t-il de permutations de $\llbracket 1, n \rrbracket$ qui envoient $1$ sur $2$ et $2$ sur $3$ ?

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 57000
Démonstration

Soit $\sigma$ une telle permutation : les images $\sigma(1) = 2$ et $\sigma(2) = 3$ sont fixées. Il reste à choisir les images des $n-2$ éléments restants, en respectant l'injectivité de $\sigma$ :

  • $\sigma(3)$ peut être choisi parmi les $n-2$ valeurs de $\Intn{1}{n} \setminus \{2, 3\}$ ;
  • $\sigma(4)$ doit être distinct de $\sigma(3)$ : $n-3$ possibilités restantes ;
  • \dots
  • $\sigma(n)$ est alors la seule valeur restante : $1$ possibilité.

D'où un total de $(n-2) \times (n-3) \times \dots \times 1 = (n-2)!$ permutations possibles.

Autrement dit, une fois $\sigma(1)$ et $\sigma(2)$ fixés, se donner $\sigma$ revient exactement à se donner une bijection quelconque de $\{3, \dots, n\}$ sur $\Intn{1}{n} \setminus \{2, 3\}$ — deux ensembles de cardinal $n-2$ — d'où là encore $(n-2)!$ possibilités.

E - Combinaisons

Définition 25 — Coefficients binomiaux, combinaison
Question de cours Oui
Notes
Aperçu
Type Définition
Référence —
Position 59000
Définition 25 — Coefficients binomiaux, combinaison
  • Combinaison : Soit $E$ un ensemble fini et $p \in \Z$. On appelle p-combinaison de $E$ toute partie de $E$ de cardinal $p$. Cet ensemble est noté $\mathcal{P}_p(E)$ (notation non universelle).
  • Coefficients binomiaux : Soient $n \in \N$ et $k \in \Z$.
    On appelle $\mathbf{k}$ parmi $\mathbf{n}$ et on note $\dbinom{n}{k}$ le nombre de parties de cardinal $k$ de l'ensemble $\Intn{1}{n}$. On a alors :
    • Si $k < 0 \text{ ou } k > n$, $\dbinom{n}{k} = 0$.
    • Si $k \in \Intn{0}{n}$, $\displaystyle \dbinom{n}{k} = \f{n!}{k!(n-k)!}$.
    Si on pose $n = |E|$, le nombre de p-combinaisons de $E$ vaut alors $|\mathcal{P}_p(E)| = \binom{n}{p}$.
Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 60000
Démonstration

Si $k \in \Intn{0}{n}$, on compte de deux façons le nombre de $k$-uplets d'éléments distincts de $\Intn{1}{n}$.

  • Premier comptage : pour construire $(x_1, \dots, x_k)$, il y a $n$ choix pour $x_1$, puis $n-1$ choix pour $x_2$ (distinct de $x_1$), \dots, puis $n-k+1$ choix pour $x_k$. Il y a donc $$n(n-1)\cdots(n-k+1) = \f{n!}{(n-k)!}$$ tels $k$-uplets.
  • Second comptage : construire $(x_1, \dots, x_k)$, c'est aussi
    • choisir une partie $A = \{x_1, \dots, x_k\}$ de cardinal $k$ de $\Intn{1}{n}$ : il y a $\dbinom{n}{k}$ choix possibles ;
    • ordonner les éléments de $A$, c'est-à-dire d'une bijection de $\Intn{1}{k}$ dans $A$ : il y a $k!$ choix possibles.
    Il y a donc $\dbinom{n}{k} \times k!$ tels $k$-uplets.

Par double comptage : $\dbinom{n}{k} \, k! = \f{n!}{(n-k)!}.$

Raw Latex
Notes
Aperçu
Position 61000
Latex brut

Une combinaison est un ensemble, et non une famille : ses éléments sont donnés sans ordre. On peut toujours décider de les numéroter pour les manipuler, mais ce choix de numérotation est totalement arbitraire — une combinaison n'a pas, en tant que telle, de premier élément, de deuxième, etc.

C'est exactement ce qui se passe lors d'un tirage simultané : on prélève plusieurs éléments d'un coup, sans qu'aucun ordre n'apparaisse entre eux — d'où la modélisation des tirages simultanés par des combinaisons.

Exemple 26
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 63000
Exemple 26 + titre

Il y a $\binom{52}{5}$ façons de tirer 5 cartes simultanément dans un jeu de 52 cartes.

Proposition 27 — Propriétés des coefficients binomiaux
Question de cours Oui
Notes
Aperçu
Type Proposition
Référence —
Position 64000
Proposition 27 — Propriétés des coefficients binomiaux

Soient $n,k \in \N$.

  1. Symétrie :    $\dbinom{n}{k} = \dbinom{n}{n-k}$.
  2. Formule de Pascal :    $\dbinom{n}{k} + \dbinom{n}{k+1} = \dbinom{n+1}{k+1}$.
  1. Formule du capitaine :    Si $n \geq 1$ et $k \in \Intn{1}{n}$ : $ k\dbinom{n}{k} = n \dbinom{n-1}{k-1}$.
    La formule reste vraie lorsque $k > n$ ou $k \leq 0$.
Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 65000
Démonstration

On démontre les formules (i) et (ii) lorsque $n \geq 1$ et $k \in \Intn{0}{n}$.

  1. Choisir une partie à $k$ éléments de $\Intn{1}{n}$ revient à choisir les $n-k$ éléments qui ne seront pas dans la partie. Il y a donc $\dbinom{n}{k}$ possibilités mais aussi $\dbinom{n}{n-k}$ possibilités.
  2. On compte de deux façons le nombre de parties à $k+1$ éléments dans $\Intn{1}{n+1}$.
    • On peut directement choisir les $k+1$ éléments --- $\dbinom{n+1}{k+1}$ choix.
    • Nous pouvons distinguer selon que la partie contienne l'entier $n+1$ ou non.
      • Si elle contient $n+1$, il reste $k$ éléments à choisir dans $\Intn{1}{n}$ --- $\dbinom{n}{k}$ choix.
      • Sinon, il reste $k+1$ éléments à choisir dans $\Intn{1}{n}$ --- $\dbinom{n}{k+1}$ choix.
  3. Ici, $k \in \Intn{1}{n}$. Cherchons à dénombrer le nombre de couples $(A,k)$ où $A$ est une partie de $\Intn{1}{n}$ et $k \in A$ est le représentant de cette partie, dit « capitaine ». On procède encore par double comptage.
    • Premier comptage : Pour construire le couple $(A,k)$, on peut :
      • commencer par choisir l'ensemble $A$ --- $\dbinom{n}{k}$ choix ;
      • choisir le représentant de $A$ --- $k$ choix.
    • Deuxième comptage : On peut aussi :
      • commencer par choisir le représentant --- $n$ choix ;
      • choisir les $k-1$ éléments restants de $A$ parmi les $n-1$ entiers restants --- $\dbinom{n-1}{k-1}$ choix.
Proposition 28 — \textit{$k$-listes strictement croissantes de $\llbracket 1, n \rrbracket$}
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 66000
Proposition 28 — $k$-listes strictement croissantes de $\llbracket 1, n \rrbracket$

Pour tout $k \in \llbracket 1, n \rrbracket$, il existe $\binom{n}{k}$ familles d'entiers $(i_1, \dots, i_k)$ pour lesquelles $1 \le i_1 < \dots < i_k \le n$.

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 66500
Démonstration

Il y a autant de telles familles que de $k$-combinaisons de $\Intn{1}{n}$, car il n'y a qu'une seule manière de ranger les éléments d'une $k$-combinaison de $\Intn{1}{n}$ dans l'ordre croissant.

Exemple 29
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 66625
Exemple 29 + titre

Un jeu de tarot contient $78$ cartes --- $21$ atouts, la carte qu'on appelle l'excuse, et $14$ cartes de chacune des $4$ couleurs cœur, pique, trèfle et carreau. Combien de tirages simultanés de $6$ cartes d'un tel jeu peut-on obtenir contenant exactement un atout et au moins $3$ as ?

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 66687
Démonstration

Un tel tirage se construit en choisissant l'atout, puis les 5 autres cartes.

  • L'atout :    $\binom{21}{1}$ choix.
  • Les 5 autres cartes sont prises parmi les 57 cartes qui ne sont pas des atouts : 4 as et 53 autres cartes.

Il est tentant de choisir 3 as puis 2 cartes quelconques parmi les 54 restantes, mais une main à 4 as serait alors comptée 4 fois (une fois par as laissé de côté). On compte donc selon le nombre exact d'as :

  • Exactement 3 as :    $\binom{4}{3}$ choix pour les as et $\binom{53}{2}$ pour les deux autres cartes.
  • Exactement 4 as :    $\binom{4}{4}$ choix pour les as et $\binom{53}{1}$ pour la dernière carte.

Ces deux cas sont disjoints, donc le nombre de tirages cherché est $$ \binom{21}{1}\left[\binom{4}{3}\binom{53}{2} + \binom{4}{4}\binom{53}{1}\right]. \qedhere $$

Remarque
Question de cours Non
Notes
Aperçu
Type Remarque
Référence —
Position 66734
Remarque + titre
  • Et le complémentaire ? Pour un « au moins », on pense souvent à compter le contraire. Ici, ce n'est pas rentable : le contraire de « au moins 3 as » est « 0, 1 ou 2 as », soit trois cas au lieu de deux : $$ \binom{21}{1}\left[\binom{57}{5} - \binom{4}{0}\binom{53}{5} - \binom{4}{1}\binom{53}{4} - \binom{4}{2}\binom{53}{3}\right]. $$ Le complémentaire vaut le coup quand il a moins de cas que l'événement lui-même, typiquement pour « au moins un » (contraire : « aucun », un seul cas).
  • Piège. Il ne faut pas compter « on choisit 3 as, puis 2 cartes quelconques parmi les 54 restantes » : $\binom{4}{3}\binom{54}{2}$ compte plusieurs fois les mains à 4 as (chacune est obtenue 4 fois, selon l'as qu'on considère comme « en plus »).
Exemple 30 — Anagrammes
Question de cours Non
Notes
Aperçu
Type Exemple
Référence —
Position 66750
Exemple 30 — Anagrammes

On appelle anagramme d'un mot tout autre mot composé des mêmes lettres avec multiplicité, mais dans un ordre quelconque. Les mots STAHM et HTMAS sont par exemple deux anagrammes de MATHS. Combien d'anagrammes BANANE possède-t-il ?

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 66875
Démonstration

Le mot BANANE est composé de $6$ lettres : $B$, $A$, $N$, $A$, $N$, $E$ — la lettre $A$ apparaît $2$ fois, la lettre $N$ apparaît $2$ fois, et $B$, $E$ apparaissent chacune $1$ fois.

  • Démonstration avec des coefficients binomiaux. Un anagramme est déterminé par le choix, parmi les $6$ positions disponibles, de celles occupées par chaque lettre. On construit un tel anagramme en :
    • choisissant les $2$ positions des $A$ parmi les $6$ positions --- $\dbinom{6}{2}$ choix ;
    • choisissant, parmi les $4$ positions restantes, les $2$ positions des $N$ --- $\dbinom{4}{2}$ choix ;
    • choisissant, parmi les $2$ positions restantes, celle du $B$ --- $\dbinom{2}{1}$ choix ---,
    • puis celle du $E$ parmi la dernière position restante --- $\dbinom{1}{1}$ choix.
    D'où le nombre d'anagrammes de BANANE : $\dbinom{6}{2} \dbinom{4}{2} \dbinom{2}{1} \dbinom{1}{1} = 15 \times 6 \times 2 \times 1 = 180.$
  • Formule directe avec des factorielles. On peut remarquer que le résultat précédent s'écrit aussi $$ \dbinom{6}{2} \dbinom{4}{2} \dbinom{2}{1} \dbinom{1}{1} = \frac{6!}{2! \, 4!} \times \frac{4!}{2! \, 2!} \times \frac{2!}{1! \, 1!} \times \frac{1!}{1! \, 0!} = \frac{6!}{2! \, 2! \, 1! \, 1!}. $$ Cela s'explique simplement : si les $6$ lettres étaient toutes distinctes, il y aurait $6!$ façons de les ordonner. Mais pour un anagramme donné, on peut permuter entre elles les $2$ occurrences de $A$ ($2!$ façons) et, indépendamment, permuter entre elles les $2$ occurrences de $N$ ($2!$ façons) sans changer le mot obtenu : chaque anagramme réel est donc compté $2! \times 2! \times 1! \times 1! = 4$ fois dans le $6!$. On corrige ce surcomptage en divisant par $2! \, 2! \, 1! \, 1!$, et on retrouve bien $180$.
Proposition 31 — Nombres de parties d'un ensemble fini
Question de cours Non
Notes
Aperçu
Type Proposition
Référence —
Position 68000
Proposition 31 — Nombres de parties d'un ensemble fini

$\abs{\Pr(E)} = 2^{\abs{E}}$.

Démonstration
Question de cours Non
Notes
Aperçu
Type Démonstration
Référence —
Position 69000
Démonstration

On pose $n = \abs{E}$.

  • Démonstration par dénombrement. Choisir une partie $A$ de $E$ revient à décider, pour chacun des $n$ éléments de $E$, s'il appartient à $A$ ou non : il y a $2$ choix indépendants par élément, donc $$ \abs{\Pr(E)} = \underbrace{2 \times 2 \times \cdots \times 2}_{n \text{ facteurs}} = 2^n. $$
  • Démonstration par bijection.
    Montrons que l'application $\phi : \fun{\Pr(E)}{\{0,1\}^E}{A}{\one_A}$ est bijective de réciproque $\psi : \fun{\{0,1\}^E}{\Pr(E)}{f}{f^{-1}(\{1\})}$.
    • Pour tout $A \in \Pr(E)$,    $\psi(\phi(A)) = \{x \in E \mid \one_A(x) = 1\} = A$ ;
    • Pour tout $f \in \{0,1\}^E$,    $\phi(\psi(f)) = \one_{f^{-1}(\{1\})}$.
      Or,    $\one_{f^{-1}(\{1\})}(x) = 1 \hiffh x \in f^{-1}(\{1\}) \hiffh f(x) = 1$.    Donc $\phi(\psi(f)) = f$.
    Ainsi $\psi \circ \phi = \Id_{\Pr(E)}$ et $\phi \circ \psi = \Id_{\{0,1\}^E}$, donc $\phi$ est bijective. Deux ensembles en bijection ayant même cardinal, on en déduit $\abs{\Pr(E)} = \abs{\{0,1\}^E} = 2^n$.
  • Démonstration avec le binôme de Newton. On part de l'égalité $\Pr(E) = \bigsqcup_{k=0}^{n} \Pr_k(E)$. En passant au cardinal on obtient : $$ \abs{\Pr(E)} = \sum_{k=0}^{n} \dbinom{n}{k} = (1+1)^n = 2^n. \qedhere $$
– / –
/ –
100%


0/0










    Ajouter un exercice — IA

    Glissez une image, collez-la (Ctrl+V), ou parcourez un fichier — ou collez directement l'énoncé en texte.

    Glisser-déposer, coller, ou parcourir…
    Importer une variante






    Fusionner un fichier .tex
    — ou —
    Notes
    Aperçu