Méthode de dénombrement : MPSI

Rédac des Sherpas - Mis à jour le 22/06/2022
méthode de dénombrement

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]\!] 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.
    livre maths mpsi vuibert

    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 ?
    profile picture
    Rédac des Sherpas
    La Rédac des Sherpas, c'est près de 100 auteurs passionnés d'éducation qui mettent leur expertise à ta disposition pour t'aider à profiter pleinement de tes études. Étudiants, profs particuliers ou spécialistes : avec eux, tu es sûr d'avoir les meilleurs conseils ! ⚡️

    Laisse-nous un commentaire !

    Des questions ? Des bons plans à partager ? Nous validons ton commentaire et te répondons en quelques heures ! 🎉

    ebook

    Notre ebook pour réussir ta prépa

    Télécharge notre guide et découvre comment réussir tes années en prépa grâce à nos conseils et nos méthodes ! 👩🏻‍🎓