Combinatoire et dénombrement

Exercices, évaluations et cours - Niveau Terminale Spécialité.

Par où commencer ?

Sur chaque chapitre, suis cet ordre pour progresser efficacement.

  1. 1. Apprendre — résumé et méthodes vidéo
  2. 2. Exercices — t’entraîner par niveau
  3. 3. Évaluations — te tester (quiz / contrôles)
Voir Apprendre Passer aux exercices
Tous À faire Terminés
Intermediaire

Intermediaire

6 exercices

Produit cartésien et cardinal

Intermédiaire Premium

Soit $E=\{-1;3;5\}$

  1. Déterminer $card(E^2)$ et $E^2$
  2. Combien de 5-uplets d'éléments de $E$ peut-on former?
  3. Dans chaque cas donner 1 élément appartenant aux ensembles suivants:
    4. $\N^3$ $\R \times \Z$ $\R^2$ $\Z \times \mathbb{Q}^2$
Aide

Compter les anagrammes d'un mot avec permuations

Intermédiaire Premium

Déterminer le nombre d'anagrammes (mêmes lettres mais dans un ordre différent) que l'on peut former pour chacun des mots suivants, en utilisant le nombre de permutations $n!$

  1. OVALE
  2. EQUIPE
  3. COOPERATION
  4. ANANAS
Aide

Compter les mot possibles

Intermédiaire Premium

Dénombrer dans les cas suivants:

  1. Compter le nombre d'anagrammes des mots: POULPE, ANAGRAMME, LITTERATURE
  2. Combien de mots de 8 lettres peut-on former avec les lettres A et B?
  3. Combien de mots de 8 lettres peut-on former avec exactement 5 lettres A et 3 lettres B?
  4. Combien de mots à 10 lettres peut-on former avec les lettres A, B, C et D?
  5. Combien de mots de 10 lettres peut-on former avec exactement 4 lettres A, 3 lettres B et 3 lettres C?
Aide

Relation de Pascal

Intermédiaire Premium

Le but de cet exercice est de démontrer la relation de Pascal: si $1\leq k \leq n-1$ alors $\dbinom{n}{k}=\dbinom{n-1}{k-1}+\dbinom{n-1}{k}$

Méthode 1: On considère un ensemble $E$ de $n$ éléments et on note un de ces éléments $A$.

  1. De combien de façons peut-on choisir $k$ éléments parmi les éléments de $F$?
  2. De combien de façons peut-on choisir $k-1$ éléments parmi les éléments de $F$?
  3. Conclure

Méthode 2: Par le calcul, en utilisant la formule $\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}$

Aide

Calcul de coefficients binomiaux

Intermédiaire Premium
  1. Montrer que pour tout entier $n$:
    2. $\dbinom{n}{0}=1$ $\dbinom{n}{1}=n$ $\dbinom{n}{2}=\dfrac{n(n-1)}{2}$
  2. En déduire les valeurs de:
    3. $\dbinom{n}{n}$ $\dbinom{n}{n-1}$ $\dbinom{n}{n-2}$
  3. Déterminer sans calculatrice les valeurs de:
    1. $\dbinom{10}{2}-\dbinom{6}{1}+\dbinom{8}{7}+\dbinom{11}{9}-\dbinom{4}{4}$
    2. $\dbinom{5}{0}+\dbinom{5}{1}-\dbinom{5}{2}+\dbinom{5}{3}-\dbinom{5}{4}+\dbinom{5}{5}$
Aide

Dénombrement et Python

Intermédiaire Premium

On considère l'algorithme Python suivant:

  1. Décrire ce que calcule cet algorithme
  2. Quelle est la valeur de f(3,7)?
  3. Écrire un algorithme qui permet de calculer $n!$ quelle que soit la valeur de l'entier $n$
Aide

Résumé de cours

Combinatoire et dénombrement

Combinatoire et dénombrement

Ensembles disjoints

Deux ensembles $A$ et $B$ sont disjoints lorsqu'ils n'ont aucun élément commun :

$$A\cap B=\emptyset$$

Exemple : $A=\{1;2;3\}$ et $B=\{4;5\}$ sont disjoints. En revanche $A$ et $C=\{3;6\}$ ne le sont pas ($3$ est commun).

Partie et complémentaire

Partie

$A$ est une partie (ou sous-ensemble) de $E$ si tous les éléments de $A$ sont dans $E$. On note $A\subset E$.

Complémentaire

Si $A\subset E$, le complémentaire $\overline{A}$ (dans $E$) est l'ensemble des éléments de $E$ qui ne sont pas dans $A$.

Exemple : $E=\{1;2;3;4;5\}$ et $A=\{2;4\}$. Alors $\overline{A}=\{1;3;5\}$ et $card(\overline{A})=card(E)-card(A)=3$.

Principe additif

Si $A_1,\ldots,A_n$ sont des ensembles deux à deux disjoints, alors

$$card(A_1\cup \cdots\cup A_n)=card(A_1)+\cdots+card(A_n)$$

Exemple : une urne contient $4$ boules rouges et $7$ boules bleues. Nombre de boules : $4+7=11$ (les deux ensembles de couleurs sont disjoints).

Produit cartésien et principe multiplicatif

$A\times B$ est l'ensemble des couples $(x;y)$ avec $x\in A$ et $y\in B$. On a

$$card(A\times B)=card(A)\times card(B)$$

Exemple

$A=\{a;b\}$, $B=\{1;2;3\}$. Alors $A\times B$ a $2\times 3=6$ couples : $(a;1)$, $(a;2)$, $(a;3)$, $(b;1)$, $(b;2)$, $(b;3)$.

En pratique

« $p$ choix puis $q$ choix indépendants » $\Rightarrow$ $p\times q$ possibilités (arbre, menus, codes…).

$k\text{-uplets (avec répétitions possibles)}$

Un $k$-uplet d'éléments de $E$ est un élément de $E^k=E\times\cdots\times E$ ($k$ facteurs). Si $card(E)=n$,

$$card(E^k)=n^k$$

Exemple : un code PIN à $4$ chiffres (de $0$ à $9$, répétitions autorisées) : $10^4=10\,000$ codes possibles.

Factorielle

Pour $n\in\mathbb{N}^*$,

$$n!=1\times 2\times \cdots\times n\qquad\text{et}\qquad 0!=1$$

Exemple : $5!=120$. On a aussi $n!=n\times(n-1)!$ (utile pour simplifier des quotients de factorielles).

Arrangements

Un arrangement de $k$ éléments parmi $n$ est un $k$-uplet d'éléments distincts (l'ordre compte, pas de répétition).

$$A_n^k=\dfrac{n!}{(n-k)!}=n(n-1)\cdots(n-k+1)$$

Quand l'utiliser ?

Ordre important + éléments distincts (podium, tirage successif sans remise, file d'attente…).

Exemple

Podium (1er, 2e, 3e) parmi $10$ coureurs : $A_{10}^3=10\times 9\times 8=720$.

Permutations

Une permutation de $n$ éléments distincts est un arrangement de ces $n$ éléments (tous les ordres possibles) :

$$P_n=n!$$

Exemple : anagrammes du mot ESPRIT (6 lettres distinctes) : $6!=720$ mots.

Combinaisons

Une combinaison de $k$ éléments parmi $n$ est une partie à $k$ éléments de $E$ (l'ordre ne compte pas, pas de répétition).

$$\binom{n}{k}=\dfrac{n!}{k!(n-k)!}=\dfrac{A_n^k}{k!}$$

Quand l'utiliser ?

On choisit un groupe, une main, un sous-ensemble : l'ordre des éléments n'a pas d'importance.

Exemple

Choisir un comité de $3$ élèves parmi $12$ : $\dbinom{12}{3}=\dfrac{12\times 11\times 10}{3\times 2\times 1}=220$.

Comment choisir la bonne formule ?
Situation Ordre ? Répétitions ? Formule
Listes / codes oui oui $n^k$
Arrangements oui non $A_n^k$
Permutations oui non (tous) $n!$
Combinaisons non non $\binom{n}{k}$

Astuce Bac : se demander « si j'échange deux éléments, est-ce que ça change le résultat ? ». Oui $\to$ arrangement / permutation. Non $\to$ combinaison.

Solution écrite

Aucune solution écrite pour cet exercice.

Vidéo