Méthode de dénombrement : MPSI

Sommaire

Méthode 1. Dénombrement d’une situation.
Méthode 2. Utilisation dans un cadre abstrait.

Tu cherches une méthode de dénombrement ? Dans cet article nous t’en présentons même deux ! N’oublie pas d’appliquer ce que tu as appris en faisant des exercices corrigés. Ainsi, tu auras toutes les cartes en main pour réussir ta prochaine interro de maths !

Pour aller encore plus loin, découvre les méthodes de dénombrement les plus efficaces et prépare-toi à résoudre des problèmes complexes en t’aidant de nos cours de soutien scolaire en maths. 🧠

Méthode 1. Dénombrement d’une situation.

Pour tout $n\in\mathbb{N}^*$

, on note $d_n$

le nombre de parties de $[\![1;n]\!]$

ne contenant pas deux entiers consécutifs. On se propose de donner une expression explicite de $d_n$

en fonction de $n$

. On choisit une partie $A$

de $[\![1;n+2]\!]$

ne contenant pas deux entiers consécutifs. On discute que $n+2$

appartienne à $A$

ou non.

Si $n+2$

n’appartient pas à $A$

, alors pour choisir $A$

, il faut et il suffit de choisir une partie de $[\![1;n+1]\!]$

, ce que l’on peut faire de $d_{n+1}$

façons.

Si ${n+2}\in\mathbb{A}$

, alors ${n+1}\notin\mathbb{A}$

. Pour choisir $A$

, il faut et il suffit de choisir une partie $A$

de $[\![1;n]\!]$

ne contenant pas deux entiers consécutifs et d’y ajouter $n+2$

, ce que l’on peut faire de $d_n$

façons.

Donc $d_{n+2}=d_{n+1}+d_n$

Or, $d_1=2$

(il y a deux parties de {1} ne contenant pas deux entiers consécutifs: {1} et $\O$

) et $d_2=3$

(il y a trois parties de {1,2} ne contenant pas deux entiers consécutifs: {1}, {2} et $\O$

). $(d_n)_{n\in\mathbb{N}^*}$

est une suite récurrente linéaire d’ordre 2 à coefficients constants dont l’équation caractéristique est $r^2=r+1$

. Les racines sont $\frac{1\pm\sqrt{5}}{2}$

, ainsi il existe deux réels $A$

et $B$

tels que

$$\forall n\in\mathbb{N}^*$, $d_n = A(\frac{1+\sqrt{5}}{2})^n + B(\frac{1-\sqrt{5}}{2})^n$.$

En utilisant les valeurs de $d_1$

et $d_2$

, on a $A=\frac{3+\sqrt{5}}{2\sqrt{5}}$

et $B=\frac{\sqrt{5}-3}{2\sqrt{5}}$

, d’où

$$\forall n\in\mathbb{N}^*$, $d_n = \frac{3+\sqrt{5}}{2\sqrt{5}}\times(\frac{1+\sqrt{5}}{2})^n + \frac{\sqrt{5}-3}{2\sqrt{5}}\times(\frac{1-\sqrt{5}}{2})^n$.$

Méthode 2. Utilisation dans un cadre abstrait.

Soit $(A,+,\times)$

un anneau commutatif fini et intègre, i.e. tel que :

$$\forall (x,y)\in\mathbb{$A$}^2$, $(x \times y = 0) \Longrightarrow (x=0$ ou $y=0)$.$

Montrons que $A$

est un corps. Soit $a \in A$

non nul. Soit $f:x \in A\longmapsto ax$

. Soit $(x,y)\in {A}^2$

tel que $f(x)=f(y)$

. On a donc $a\times(x-y)=0$

. Or, $a\ne 0$

, donc par hypothèse, $x-y=0$

, puis $x=y$

On a montré que $f$

est injective. Comme $A$

est fini, d’après une proposition, $f$

est surjective. il s’ensuit que 1 admet un antécédent par $f$

: il existe $x_0 \in A$

tel que $1 = f(x_0) = ax_0$

. Par commutativité, on a $ax_0 = x_0a = 1$

, donc $a$

est inversible. On a montré que tout élément non nul est inversible, donc $a$

est un corps.

Cet article est extrait de l’ouvrage Maths MPSI-MP2I. Tout-en-un : cours, méthodes, entraînement et corrigés (éditions Vuibert, juin 2021) écrit par E. Thomas, S. Bellec, G. Boutard. ISBN n°9782311408720