BURHAN.

Les p-listes d'un ensemble : Cours de Mathématiques 1BAC Sciences Mathématiques, chapitre Dénombrement

Les p-listes d'un ensemble : notion du chapitre Dénombrement du programme de maths 1BAC SM, expliquée pas à pas, avec 1 exemple guidé. Pour les élèves de 1BAC Sciences Mathématiques, option française (BIOF).

Notions du cours (10)

Apprendre avec Burhan

p-listes : l'ordre compte, la répétition aussi

Étape 1 sur 3

Des mots de trois lettres

En clair. Avec l'alphabet {a,b,c}\{a, b, c\}, un « mot » est une suite de lettres, même sans aucun sens. Les mots de deux lettres sont aaaa, abab, acac, baba, bbbb, bcbc, caca, cbcb et cccc. Ici, l'ordre compte : abab et baba sont deux mots différents. Et une lettre peut se répéter : aaaa est un mot.

Devine : Mots de trois lettres

Combien de mots de trois lettres peut-on écrire avec l'alphabet {a,b,c}\{a, b, c\} ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :99

Faux.

Ce sont les mots de deux lettres : une troisième lettre multiplie encore leur nombre.

Choix B :66

Faux.

On a interdit les répétitions : or aabaab est un mot permis.

Choix C :2727

Juste.

Juste : 3×3×33 \times 3 \times 3.

Choix D :11

Faux.

11 compte les groupes de trois lettres distinctes, sans ordre. Or l'ordre compte, et les lettres peuvent se répéter.

Voir la correction complète

Chaque mot de deux lettres se prolonge de trois façons : avec aa, bb ou cc. Il y a donc 9×3=279 \times 3 = 27 mots de trois lettres, de aaaaaa à cccccc.

Continuer : Combien de listes ? →

Étape 2 sur 3

Combien de listes ?

Définitionp-listes d'un ensemble fini

Soit EE un ensemble fini non vide et p∈N∗p \in \mathbb{N}^{*}. Une pp-liste d'éléments de EE (on dit aussi un arrangement avec répétition) est un pp-uplet (x1,x2,…,xp)(x_1, x_2, \dots, x_p) d'éléments de EE, c'est-à-dire un élément de Ep=E×E×⋯×EE^{p} = E \times E \times \dots \times E (pp facteurs).

Dans une pp-liste, l'ordre compte et un même élément peut apparaître plusieurs fois.

Un mot de trois lettres sur {a,b,c}\{a, b, c\} est un triplet (x1,x2,x3)(x_1, x_2, x_3). Pourquoi est-ce vrai ? Les pp-listes forment exactement le produit EpE^{p}. Il suffit alors d'appliquer le cardinal d'un produit cartésien.

PropriétéNombre de p-listes

Soit EE un ensemble fini de cardinal n≥1n \geq 1 et p∈N∗p \in \mathbb{N}^{*}. Le nombre de pp-listes d'éléments de EE est card(Ep)=np.\mathrm{card}(E^{p}) = n^{p}.

Démonstration

Étape 1. Par définition, les pp-listes d'éléments de EE sont exactement les éléments du produit cartésien Ep=E×E×⋯×EE^{p} = E \times E \times \dots \times E (pp facteurs).

Étape 2. Si p=1p = 1, E1=EE^{1} = E et card(E)=n\mathrm{card}(E) = n. Si p≥2p \geq 2, d'après le cardinal d'un produit cartésien, EpE^{p} est fini et card(Ep)=card(E)×card(E)×⋯×card(E)=np\mathrm{card}(E^{p}) = \mathrm{card}(E) \times \mathrm{card}(E) \times \dots \times \mathrm{card}(E) = n^{p} (pp facteurs).

À retenirCe qu'il faut retenir de la preuve

La preuve tient en une idée : reconnaître un produit cartésien. Une pp-liste d'éléments de EE n'est rien d'autre qu'un élément de E×E×⋯×EE \times E \times \dots \times E. Le reste vient du cardinal d'un produit.

Vérifie : Quel résultat ?

Sur quel résultat la preuve du nombre de pp-listes s'appuie-t-elle ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :Le cardinal d'un produit cartésien.

Juste.

Juste : EpE^{p} est un produit de pp facteurs égaux à EE.

Choix B :La formule du cardinal du complémentaire.

Faux.

Rien n'est retranché dans cette preuve.

Choix C :La composée de deux bijections.

Faux.

La preuve ne construit aucune bijection : les pp-listes sont déjà les éléments de EpE^{p}.

Choix D :Une récurrence rédigée sur pp.

Faux.

La récurrence est cachée dans le cardinal d'un produit ; cette preuve n'en écrit aucune.

Voir la correction complète

D'après la définition, les pp-listes sont les éléments de EpE^{p}. La preuve applique le cardinal d'un produit cartésien, avec pp facteurs égaux à EE : card(Ep)=np\mathrm{card}(E^{p}) = n^{p}.

← Étape précédenteContinuer : Tirages avec remise, puis à toi →

Étape 3 sur 3

Tirages avec remise, puis à toi

Exempletirages successifs avec remise

  • Une urne contient 55 boules numérotées de 11 à 55. On tire une boule, on note son numéro, on la remet, et l'on recommence : trois tirages en tout. Un résultat est une 33-liste d'éléments de {1,2,3,4,5}\{1, 2, 3, 4, 5\}, comme (2,5,2)(2, 5, 2). Il y a 53=1255^{3} = 125 résultats.
  • Un code PIN de quatre chiffres est une 44-liste de chiffres : 104=10 00010^{4} = 10\,000 codes, comme pour le cadenas du début.

Arbre de choix horizontal à trois niveaux, un par tirage. B_k désigne la boule numéro k. De la racine partent les branches B_1 et B_5, et des points de suspension entre elles remplacent B_2, B_3 et B_4. Au bout de chacune repartent B_1, B_2, des points de suspension et B_5 pour le deuxième tirage, puis B_1, des points de suspension et B_5 pour le troisième : la boule tirée est remise, donc les cinq numéros restent possibles à chaque niveau.

Arbre partiel des trois tirages avec remise : à chaque tirage, cinq branches B_1 à B_5, dont seules quelques-unes sont dessinées.

À toi : Au moins un zéro

Combien de codes PIN de quatre chiffres contiennent au moins un 00 ? Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Passe par le complémentaire : compte d'abord les codes sans aucun 00.

Encore bloqué ? Indice 2

Un code sans 00 est une 44-liste de l'ensemble {1,2,…,9}\{1, 2, \dots, 9\}.

Encore bloqué ? Indice 3

Point délicat : retranche du total des codes, 10410^{4}, et non de 949^{4}.

Voir la solution complète

Soit PP l'ensemble des codes PIN, et AA la partie de ceux qui contiennent au moins un 00. Les codes sont les 44-listes de chiffres : card(P)=104=10 000\mathrm{card}(P) = 10^{4} = 10\,000.

Le complémentaire A‾\overline{A}, dans PP, est l'ensemble des 44-listes de {1,2,…,9}\{1, 2, \dots, 9\} : card(A‾)=94=6561\mathrm{card}(\overline{A}) = 9^{4} = 6561. D'après la formule du complémentaire, card(A)=10 000−6561=3439\mathrm{card}(A) = 10\,000 - 6561 = 3439.

← Étape précédenteFin de la notion

S'entraîner sur cette notion

Sources du cours

  • Référentiel BURHAN du chapitre « Dénombrement » (1bac · sciences-mathematiques · mathematiques)