Christophe Bertault — Mathématiques en MPSI DÉNOMBREMENT Notre objectif est ici
Christophe Bertault — Mathématiques en MPSI DÉNOMBREMENT Notre objectif est ici purement pratique — APPRENDRE À COMPTER. Nous omettrons pour cette raison la plupart des démonstrations de ce chapitre, souvent difficiles, conformément au programme de MPSI. 1 CARDINAL D’UN ENSEMBLE FINI Définition-théorème (Ensemble fini/infini, cardinal d’un ensemble fini) Soit E un ensemble. • On dit que E est fini s’il est vide ou si, pour un certain n ∈N∗, il existe une bijection de l’ensemble ⟦1, n⟧sur E. On dit dans le cas contraire que E est infini. • Si E est fini non vide, l’entier n de la définition précédente est unique, appelé le cardinal de E ou nombre d’éléments de E et noté |E| (ou card(E) ou #E). Par convention, l’ensemble vide est de cardinal 0. Exemple Pour tous m, n ∈Z avec m ⩽n, l’ensemble ⟦m, n⟧est fini de cardinal n −m + 1. En effet La fonction k 7−→k + m −1 est bijective de ⟦1, n−m + 1⟧sur ⟦m, n⟧de réciproque k 7−→k −m + 1. Théorème (Équipotence et cardinal) Soient E et F deux ensembles. Si E est fini et s’il existe une bijection de E sur F, alors F est fini et : |E| = |F|. Démonstration Dans le cas où E est non vide, nous pouvons nous donner une bijection f de 1,|E| sur E et une bijection g de E sur F. L’application g ◦f est alors bijective de 1,|E| sur F, donc d’une part F est fini, mais d’autre part : |F| = |E| par unicité du cardinal. ■ Théorème (Parties d’un ensemble fini) Soient E un ensemble fini et A une partie de E. Alors A est finie et : |A| ⩽|E|, avec égalité si et seulement si : A = E. En pratique Pour montrer que deux ensembles FINIS A et B sont égaux, au lieu de montrer que : A ⊂B et B ⊂A, on peut se contenter de montrer, grâce au théorème précédent, que : A ⊂B et |A| = |B|. Théorème (Effet d’une application sur le cardinal) Soient E et F deux ensembles et f : E −→F une application. (i) Si f est injective et si F est fini, alors E aussi est fini et : |E| ⩽|F|, avec égalité si et seulement si f est bijective. (ii) Si f est surjective et si E est fini, alors F aussi est fini et : |F| ⩽|E|, avec égalité si et seulement si f est bijective. (iii) Si E et F sont FINIS DE MÊME CARDINAL : f est bijective ⇐⇒ f est injective ⇐⇒ f est surjective. Explication • Dire que f est injective, c’est dire que deux points distincts de E sont envoyés par f sur deux points distincts de F, i.e. que f (E) est comme une copie de E dans F. Une telle copie n’est possible que si F est « plus gros » que E, i.e. si : |E| ⩽|F| — assertion (i). • Dire que f est surjective, c’est dire qu’à travers f , E couvre F en totalité. Une telle couverture n’est possible que si E est « plus gros » que F, i.e. si : |F| ⩽|E| — assertion (ii). 1 Christophe Bertault — Mathématiques en MPSI Théorème (Principe des tiroirs) Quand on doit ranger n + 1 chaussettes dans n tiroirs, deux chaussettes au moins se retrouvent dans le même tiroir. Explication Ranger n+1 chaussettes dans n tiroirs, c’est choisir une application d’un ensemble de cardinal n+1 dans un ensemble de cardinal n. Or comme n + 1 > n, une telle application n’est jamais injective — d’où le résultat. Exemple Étant donnés 5 points dans un carré d’arête 2, on peut toujours en trouver deux distants d’au plus p 2. p 2 En effet Coupons simplement notre carré en quatre comme indiqué ci-contre et prenons les quatre sous-carrés ainsi formés pour « tiroirs ». Sommés de ranger 5 « chaussettes » — les 5 points quelconques — dans 4 tiroirs, nous sommes forcés d’en ranger 2 dans le même tiroir d’après le principe des tiroirs. Au pire, ces points sont alors distants de p 2 — longueur de la diagonale de chaque sous-carré. 2 DÉNOMBREMENT 2.1 QU’EST-CE QUE COMPTER ? En pratique Nous allons dans cette partie apprendre à répondre à des questions aussi diverses que : — À 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 ? — Combien un polygone à n côtés possède-t-il de diagonales ? — De combien de façons peut-on tirer 5 cartes simultanément dans un jeu de 52 cartes ? et successivement avec remise ? et sans remise ? — Combien d’anagrammes le mot « BOROROS » possède-t-il ? — De combien de façons peut-on asseoir n personnes sur un banc rectiligne ? autour d’une table ronde ? — Combien existe-t-il d’applications strictement croissantes de ⟦1, p⟧dans ⟦1, n⟧? — Combien un ensemble fini de cardinal n possède-t-il de parties ? Chacune de ces questions requiert, certes, un minimum de théorie mathématique, mais surtout beaucoup de bon sens. Soyez dans ce chapitre plus encore que dans les autres ce que je vous demande souvent d’être — DES GENS CONCRETS ! Pour savoir de combien de façons on peut asseoir n personnes sur un banc rectiligne, imaginez-vous concrètement en train d’asseoir ces personnes et demandez-vous combien de choix cela vous laisse. Notre règle d’or dans ce chapitre sera ainsi la suivante : COMPTER, C’EST ÉNUMÉRER/CONSTRUIRE. Cette règle d’or, hélas, nous en dit à la fois beaucoup et pas assez — car c’est quoi, concrètement, « énumérer » et « construire » ? Nous le comprendrons mieux sur deux exemples. • Dimension de Mn,p(K) : Quand nous avons calculé la dimension de Mn,p(K) au chapitre « Structure d’espace vectoriel », par exemple, nous avons commencé par en trouver une base — la base canonique en l’occurrence. Ensuite, pour compter le nombre de vecteurs de cette base, nous nous la sommes représentés géométriquement comme un tableau, et du coup c’est le nombre de cases de ce tableau que nous devions calculer. Or là, nous n’avons pas compté les cases une à une, nous avons transformé notre tableau en une collection de lignes et nous avons dit : « Ce tableau contient n lignes et chacune contient p cases, donc en tout ce tableau contient : n fois z }| { p + ... + p = n× p cases. » Identification du problème : compter les vecteurs de la base canonique. Représentation du problème : sous la forme d’un tableau. b b b b b b b b b b b b b b b p (ici 5) n (ici 3) Dénombrement : par décomposition du problème. b b b b b b b b b b b b b b b p p p 2 Christophe Bertault — Mathématiques en MPSI p (ici 4) b b Départ Arrivée • Première aventure de la chenille Becky : La chenille Becky se promène le long d’un grillage plan de taille 2 × p dont chaque arête est de longueur 1. Combien de chemins de longueur minimale peut-elle emprunter pour gagner le point d’arrivée depuis son point de départ ? Pour commencer, ces chemins de longueur minimale sont exactement les chemins de lon- gueur p + 2 qui contiennent p déplacements vers la droite et 2 déplacements vers le bas. Chacun peut donc être vu comme un mot de p + 2 lettres contenant p fois lettres « D » et 2 fois lettres « B ». Or combien existe-t-il de tels mots ? Pour construire un tel mot, on n’a finalement qu’à choisir la position des 2 lettres « B », car ensuite il n’y a que des « D » à placer. Or de combien de façons pouvons-nous placer nos 2 « B » sur un mot vierge de p + 2 lettres ? Le deuxième « B » peut être placé en position k pour tout k ∈⟦2, p + 2⟧. Quant au premier, si le deuxième est placé en position k, il peut être placé en position 1,2,... , k −1, soit un total de k −1 positions possibles. Au total, Becky peut donc emprunter : p+2 X k=2 (k −1) i=k−1 = p+1 X i=1 i = (p + 1)(p + 2) 2 chemins. Identification du problème : compter les chemins de longueur p + 2 qui vont p fois à droite et 2 fois vers le bas. Représentation du problème : sous la forme de certains mots. D...DBD...DBD...D | {z } p+2 lettres Dénombrement : par décomposition du problème. D...D B k −1 choix D...D B Position k D...D Pour savoir compter, nous venons de voir qu’il faut savoir énumérer — mais qu’est-ce qu’énumérer ? Énumérer, c’est ordonner selon un principe de classement RÉFLÉCHI. Exemple Pour énumérer les coefficients d’une matrice A uploads/Religion/ cours-denombrement 2 .pdf
Documents similaires
-
16
-
0
-
0
Licence et utilisation
Gratuit pour un usage personnel Attribution requise- Détails
- Publié le Mai 16, 2022
- Catégorie Religion
- Langue French
- Taille du fichier 0.1294MB