homecarab1.fr
Biostatistiques et méthodes d'analysechevron_rightOutils mathématiqueschevron_rightEnsembles, dénombrement et analyse combinatoire

Sommaire

  • 1Ensembles et relations fondamentales
  • 2Opérations ensemblistes
  • 3Cardinal et partition d’un ensemble fini
  • 4Principes fondamentaux du dénombrement
  • 5Arrangements et permutations lock — section verrouillée
  • 6Combinaisons lock — section verrouillée
  1. Accueilchevron_right
  2. Ficheschevron_right
  3. Biostatistiques et méthodes d'analysechevron_right
  4. Outils mathématiqueschevron_right
  5. Ensembles, dénombrement et analyse combinatoire

B10 · Outils mathématiques

Ensembles, dénombrement et analyse combinatoire

Manipuler les opérations ensemblistes, la partition et le cardinal d'un ensemble fini. Utiliser factorielles, arrangements, permutations et combinaisons, avec et sans répétition, pour dénombrer des situations.

Biostatistiques et méthodes d'analyse·schedule6 min de lecture·quiz15 QCM corrigés

Ensembles et relations fondamentales

Définition

Ensemble

Collection d'objets distincts, appelés éléments. L’ordre d’énumération des éléments et leur éventuelle répétition dans une description ne modifient pas l’ensemble.

L’appartenance d’un élément xxx à un ensemble AAA se note x∈Ax \in Ax∈A. Sa non-appartenance se note x∉Ax \notin Ax∈/A.

Définition

Ensemble vide ∅\varnothing∅

Ensemble ne contenant aucun élément.

Définition

Inclusion

Un ensemble AAA est inclus dans un ensemble BBB, ce qui se note A⊆BA \subseteq BA⊆B, lorsque tout élément de AAA appartient aussi à BBB.

Deux ensembles sont égaux lorsqu’ils ont exactement les mêmes éléments. Ainsi,

A=B⟺A⊆B et B⊆A.A=B \quad \Longleftrightarrow \quad A\subseteq B \text{ et } B\subseteq A.A=B⟺A⊆B et B⊆A.

L’inclusion stricte A⊊BA\subsetneq BA⊊B signifie que A⊆BA\subseteq BA⊆B et A≠BA\neq BA=B.

Attention

Appartenance et inclusion

x∈Ax\in Ax∈A relie un élément à un ensemble, tandis que A⊆BA\subseteq BA⊆B relie deux ensembles. Ces deux symboles ne sont pas interchangeables.

Définition

Ensemble des parties P(A)\mathcal P(A)P(A)

Ensemble dont les éléments sont tous les sous-ensembles de AAA, y compris ∅\varnothing∅ et AAA lui-même.

Si AAA possède nnn éléments, chacun peut être retenu ou non dans une partie. Les choix étant indépendants, P(A)\mathcal P(A)P(A) possède donc 2n2^n2n éléments.

Opérations ensemblistes

On se place dans un ensemble de référence EEE, qui contient tous les éléments considérés.

Définition

Union A∪BA\cup BA∪B

Ensemble des éléments appartenant à AAA, à BBB, ou aux deux ensembles.

Définition

Intersection A∩BA\cap BA∩B

Ensemble des éléments appartenant simultanément à AAA et à BBB.

Définition

Complémentaire AcA^cAc

Ensemble des éléments de l’ensemble de référence EEE qui n’appartiennent pas à AAA.

Définition

Différence A∖BA\setminus BA∖B

Ensemble des éléments appartenant à AAA mais pas à BBB. Elle vérifie A∖B=A∩BcA\setminus B=A\cap B^cA∖B=A∩Bc.

Définition

Différence symétrique A△BA\mathbin{\triangle}BA△B

Ensemble des éléments appartenant à un seul des deux ensembles AAA et BBB. Elle correspond à l’union privée de l’intersection.

Les opérations d’union et d’intersection sont commutatives et associatives. Elles sont aussi distributives l’une par rapport à l’autre :

A∩(B∪C)=(A∩B)∪(A∩C),A\cap(B\cup C)=(A\cap B)\cup(A\cap C),A∩(B∪C)=(A∩B)∪(A∩C), A∪(B∩C)=(A∪B)∩(A∪C).A\cup(B\cap C)=(A\cup B)\cap(A\cup C).A∪(B∩C)=(A∪B)∩(A∪C).

Les lois de De Morgan décrivent le complémentaire d’une union ou d’une intersection :

(A∪B)c=Ac∩Bc,(A∩B)c=Ac∪Bc.(A\cup B)^c=A^c\cap B^c, \qquad (A\cap B)^c=A^c\cup B^c.(A∪B)c=Ac∩Bc,(A∩B)c=Ac∪Bc.
Définition

Ensembles disjoints

Ensembles dont l’intersection est vide. Ainsi, AAA et BBB sont disjoints si A∩B=∅A\cap B=\varnothingA∩B=∅.

Définition

Produit cartésien A×BA\times BA×B

Ensemble des couples ordonnés dont le premier élément appartient à AAA et le second à BBB.

L’ordre compte dans un couple : les rôles des deux coordonnées sont distincts.

Cardinal et partition d’un ensemble fini

Définition

Cardinal ∣A∣\lvert A\rvert∣A∣

Nombre d’éléments distincts d’un ensemble fini AAA.

Le cardinal de l’ensemble vide vaut 000. Si A⊆BA\subseteq BA⊆B, alors ∣A∣≤∣B∣\lvert A\rvert\leq\lvert B\rvert∣A∣≤∣B∣. Pour deux ensembles finis, le produit cartésien vérifie :

∣A×B∣=∣A∣ ∣B∣.\lvert A\times B\rvert=\lvert A\rvert\,\lvert B\rvert.∣A×B∣=∣A∣∣B∣.

Lorsque deux ensembles sont disjoints, le cardinal de leur union est la somme de leurs cardinaux. Dans le cas général, les éléments de l’intersection seraient comptés deux fois par cette somme : il faut donc les retrancher une fois.

Formule

Principe d’inclusion-exclusion

∣A∪B∣=∣A∣+∣B∣−∣A∩B∣\lvert A\cup B\rvert = \lvert A\rvert+\lvert B\rvert-\lvert A\cap B\rvert∣A∪B∣=∣A∣+∣B∣−∣A∩B∣
  • AAA et BBB : ensembles finis
  • ∣A∣\lvert A\rvert∣A∣ et ∣B∣\lvert B\rvert∣B∣ : cardinaux de AAA et de BBB
  • ∣A∩B∣\lvert A\cap B\rvert∣A∩B∣ : nombre d’éléments communs
  • ∣A∪B∣\lvert A\cup B\rvert∣A∪B∣ : nombre d’éléments appartenant à au moins un des deux ensembles
Exemple

Corriger un double comptage entre deux options

Dans une promotion de 120 étudiants, 70 suivent l’option « biologie » et 55 suivent l’option « physique ». Parmi eux, 25 suivent les deux options.

Les 25 étudiants suivant les deux options sont comptés une première fois parmi les 70, puis une seconde fois parmi les 55. Ils doivent donc être retranchés une fois :

∣A∪B∣=70+55−25=100.\lvert A\cup B\rvert = 70 + 55 - 25 = 100.∣A∪B∣=70+55−25=100.

100 étudiants suivent au moins une des deux options. Il reste donc 120−100=20120 - 100 = 20120−100=20 étudiants qui ne suivent aucune de ces deux options.

Définition

Partition d’un ensemble EEE

Famille de sous-ensembles non vides de EEE, deux à deux disjoints, dont l’union est égale à EEE.

Chaque élément de EEE appartient alors à une et une seule partie de la partition. Si les parties sont A1,…,AkA_1,\ldots,A_kA1​,…,Ak​, alors :

∣E∣=∑i=1k∣Ai∣,\lvert E\rvert=\sum_{i=1}^{k}\lvert A_i\rvert,∣E∣=i=1∑k​∣Ai​∣,

où kkk est le nombre de parties et iii leur indice.

À retenir

Additionner directement des cardinaux n’est permis que pour des ensembles disjoints. Sinon, il faut corriger les recouvrements par le principe d’inclusion-exclusion.

Principes fondamentaux du dénombrement

Définition

Dénombrement

Détermination du nombre d’éléments d’un ensemble fini sans nécessairement les énumérer un à un.

Le principe additif s’applique lorsqu’une situation se décompose en cas incompatibles : le nombre total est la somme des nombres associés à chaque cas.

Le principe multiplicatif s’applique à une succession de choix : si chaque choix d’une étape peut être associé à tous les choix de l’étape suivante, le nombre total est le produit des nombres de possibilités à chaque étape.

Définition

Factorielle n!n!n!

Pour un entier naturel nnn, produit de tous les entiers de 111 à nnn. Par convention, 0!=10!=10!=1.

Formule

Factorielle

n!=∏i=1ni=n(n−1)⋯2⋅1n!=\prod_{i=1}^{n}i=n(n-1)\cdots 2\cdot 1n!=i=1∏n​i=n(n−1)⋯2⋅1
  • nnn : entier naturel
  • iii : indice parcourant les entiers de 111 à nnn
  • n!n!n! : factorielle de nnn

La convention 0!=10!=10!=1 correspond au produit vide : il existe une seule manière de n’effectuer aucun choix et une seule manière d’ordonner un ensemble vide.

Arrangements et permutations

Définition

Arrangement sans répétition

Sélection ordonnée de ppp éléments distincts parmi nnn éléments, sans qu’un même élément puisse être choisi plusieurs fois.

Le premier rang offre nnn choix, le deuxième n−1n-1n−1, puis le nombre de choix diminue d’une unité à chaque rang.

Formule

Nombre d’arrangements sans répétition

Anp=n!(n−p)!A_n^p=\frac{n!}{(n-p)!}Anp​=(n−p)!n!​
  • nnn : nombre total d’éléments disponibles
  • ppp : nombre d’éléments sélectionnés, avec 0≤p≤n0\leq p\leq n0≤p≤n
  • AnpA_n^pAnp​ : nombre de sélections ordonnées sans répétition
Exemple

Désigner trois responsables parmi sept étudiants

Sept étudiants sont candidats à trois fonctions distinctes : président, vice-président et secrétaire. Une même personne ne peut occuper qu’une fonction.

Le choix est ordonné, car échanger le président et le secrétaire modifie le résultat. Il n’y a pas de répétition :

A73=7×6×5=210.A_7^3 = 7 \times 6 \times 5 = 210.A73​=7×6×5=210.

Il existe donc 210 façons de désigner les trois responsables. Le premier poste compte 7 choix, le deuxième 6 choix après la première désignation, puis le troisième 5 choix.

Définition

Arrangement avec répétition

Sélection ordonnée de ppp éléments parmi nnn, dans laquelle chaque élément peut être choisi plusieurs fois.

Chaque rang offre alors toujours nnn choix, indépendamment des choix précédents.

Nombre d’arrangements avec reˊpeˊtition=np.\text{Nombre d’arrangements avec répétition}=n^p.Nombre d’arrangements avec reˊpeˊtition=np.
Définition

Permutation

Arrangement de tous les éléments d’un ensemble fini : chaque élément est utilisé exactement une fois et seul leur ordre varie.

Une permutation de nnn éléments distincts est donc un arrangement sans répétition avec p=np=np=n, ce qui donne n!n!n! permutations.

Si certains éléments sont indiscernables, les échanges entre eux ne créent pas de nouvel ordre. Il faut diviser par le nombre de permutations internes à chaque groupe d’éléments identiques.

Formule

Permutations avec répétitions

n!n1!n2!⋯nk!,∑i=1kni=n\frac{n!}{n_1!n_2!\cdots n_k!}, \qquad \sum_{i=1}^{k}n_i=nn1​!n2​!⋯nk​!n!​,i=1∑k​ni​=n
  • nnn : nombre total de positions
  • kkk : nombre de catégories d’éléments
  • nin_ini​ : nombre d’éléments indiscernables de la catégorie iii
  • iii : indice de la catégorie

Combinaisons

Définition

Combinaison sans répétition

Sélection non ordonnée de ppp éléments distincts parmi nnn : seules les identités des éléments retenus comptent.

Chaque combinaison peut être ordonnée de p!p!p! façons. Le nombre d’arrangements doit donc être divisé par p!p!p!.

Formule

Coefficient binomial

(np)=n!p!(n−p)!\binom{n}{p} = \frac{n!}{p!(n-p)!}(pn​)=p!(n−p)!n!​
  • nnn : nombre total d’éléments disponibles
  • ppp : nombre d’éléments sélectionnés, avec 0≤p≤n0\leq p\leq n0≤p≤n
  • (np)\binom{n}{p}(pn​) : nombre de combinaisons sans répétition

Les coefficients binomiaux vérifient la symétrie (np)=(nn−p)\binom{n}{p}=\binom{n}{n-p}(pn​)=(n−pn​) : choisir les éléments retenus revient à déterminer ceux qui ne le sont pas.

Définition

Combinaison avec répétition

Sélection non ordonnée de ppp éléments parmi nnn catégories, une même catégorie pouvant être choisie plusieurs fois.

Une telle sélection est entièrement décrite par les effectifs attribués aux différentes catégories. La méthode des séparateurs transforme cette répartition en un choix de positions parmi n+p−1n+p-1n+p−1 positions.

Formule

Nombre de combinaisons avec répétition

(n+p−1p)=(n+p−1)!p!(n−1)!\binom{n+p-1}{p} = \frac{(n+p-1)!}{p!(n-1)!}(pn+p−1​)=p!(n−1)!(n+p−1)!​
  • nnn : nombre de catégories disponibles, avec n≥1n\geq 1n≥1
  • ppp : nombre total d’éléments sélectionnés
  • (n+p−1p)\binom{n+p-1}{p}(pn+p−1​) : nombre de sélections non ordonnées avec répétition
Comparaison

Choisir la formule de dénombrement

SituationOrdre pris en compteRépétitionNombre
Arrangement sans répétitionouinonn!(n−p)!\frac{n!}{(n-p)!}(n−p)!n!​
Arrangement avec répétitionouiouinpn^pnp
Combinaison sans répétitionnonnon(np)\binom{n}{p}(pn​)
Combinaison avec répétitionnonoui(n+p−1p)\binom{n+p-1}{p}(pn+p−1​)
Méthode

Identifier le modèle combinatoire

  1. Déterminer si la situation comporte une succession de choix ou une simple sélection
  2. Vérifier si l’échange de deux éléments modifie le résultat, afin de décider si l’ordre compte
  3. Vérifier si un même élément peut être choisi plusieurs fois
  4. Déterminer si tous les éléments disponibles sont utilisés, ce qui caractérise une permutation
  5. Appliquer la formule correspondant aux réponses précédentes et contrôler ses conditions de validité
Attention

Ordre et répétition sont deux critères indépendants

Une sélection non ordonnée n’est pas nécessairement sans répétition. De même, une sélection ordonnée peut autoriser ou interdire la répétition. Il faut répondre séparément aux deux questions.

À retenir

Le dénominateur d’une formule de dénombrement élimine des descriptions multiples d’un même résultat : p!p!p! supprime les différents ordres d’une combinaison, tandis que les factorielles des multiplicités suppriment les échanges entre éléments indiscernables.

Points clés
  • L’union rassemble, l’intersection conserve les éléments communs et le complémentaire dépend de l’ensemble de référence
  • Une partition est formée de parties non vides, deux à deux disjointes, dont l’union reconstitue l’ensemble
  • Le principe additif traite des cas incompatibles, tandis que le principe multiplicatif traite des choix successifs
  • Une permutation ordonne tous les éléments, un arrangement est ordonné et une combinaison ne l’est pas
  • Le choix de la formule dépend séparément de la prise en compte de l’ordre et de l’autorisation des répétitions
  • Le principe d’inclusion-exclusion corrige le double comptage des intersections
Inscris-toi pour lire la suitearrow_forward

Fiches connexes

Pour maîtriser tous le cours de Outils mathématiques.

  • Fiche 02Fonctions usuelles : exponentielle, logarithme et puissancesOutils mathématiques
  • Fiche 03Dérivation et étude de fonctionsOutils mathématiques
  • Fiche 04Primitives, intégration et applicationsOutils mathématiques
Sommaire
  • 1Ensembles et relations fondamentales
  • 2Opérations ensemblistes
  • 3Cardinal et partition d’un ensemble fini
  • 4Principes fondamentaux du dénombrement
  • 5Arrangements et permutations lock — section verrouillée
  • 6Combinaisons lock — section verrouillée