Méthode de dénombrement : MPSI

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 !

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]\!]$

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}$

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$

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$

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

Tu as aimé cet article ?

Méthode de dénombrement : MPSI

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

Méthode 2. Utilisation dans un cadre abstrait.

*01* Newsletter

01 Newsletter