Dénombrement - arrangement combinaison permutation

Conseils

Arrangement & Combinaison

Cours

$k$-uplet - Arrangement - permutation

•

Factorielle

•

$k$-uplet

Définition Un $\boldsymbol{k}$-uplet d'éléments de $\rm E$ est une liste ordonnée de $k$ éléments de $\rm E$ distincts ou pas.

Mathématiquement, un $k$-uplet d'élements de $\rm E$ est un élément de $ \underbrace{\rm E\times ...\times E}_k$.
Un $k$-uplet s'appelle aussi une $k$-liste.
Les parenthèses $( ... ;...;...)$ indiquent que l'on a affaire à un $k$-uplet

L'ordre compte dans un $k$-uplet

Il peut y avoir des répétitions dans un $k$-uplet

Un $k$-uplet correspond à un tirage successif de $k$ boules (l'une après l'autre donc avec ordre) et avec remise (on remet la boule après chaque tirage) dans une urne contenant $n$ boules discernables.
Exemple Les mots

Propriété Le nombre de $\boldsymbol{k}$-uplets d'un ensemble de $n$ éléments est de $\boldsymbol{n^k}$.

Exemple Déterminer le nombre de mots de 3 lettres (on ne compte pas les accents)

•

Arrangement

Définition Soit $\rm E$ un ensemble fini non vide à $n$ éléments. Un

arrangement de $\rm E$

est un $k$-uplet d'éléments distincts de $\rm E$

Autrement dit, dans un arrangement, l'ordre compte car c'est un $k$-uplet mais il n'y a pas de répétition car les éléments doivent être distincts

Un arrangement correspond à un tirage successif de $k$ boules (c'est à dire l'une après l'autre donc l'ordre compte) et sans remise (on ne remet pas la boule après le tirage) dans une urne contenant $n$ boules discernables.

$k\leqslant n$

Exemple $(s;o;p;h;i;e)$ et $(g;a;s;p;a;r;d)$ sont-ils des arrangements?

Propriété Le nombre d'arrangements de $k$ éléments d'un ensemble ayant $n$ éléments est égal à $\boldsymbol{n\times (n-1)\times ... \times (n-k+1)}$

On a $\boldsymbol{n}$ choix pour le premier élément, puis $\boldsymbol{n-1}$ pour le second car les éléments doivent être distincts, puis $n-2$ pour le troisième et ainsi de suite et $\boldsymbol{n-k+1}$ pour le $\boldsymbol{k}$-ième c'est à dire le dernier. Donc au final, on a $\boldsymbol{n\times (n-1)\times ...\times (n-k+1)}$ choix possibles.
$k\leqslant n$

Avec la notation factorielle: $n\times (n-1)\times ... \times (n-k+1)=\dfrac{n!}{(n-k)!}$

Exemple Une urne contient dix boules numérotées de 1 à 10. On tire 4 boules une par une et sans remise. Déterminer le nombre de tirages possibles

•

Permutation

Définition Soit $\rm E$ un ensemble fini non vide à $n$ éléments. Une permutation de $\rm E$ est un $\boldsymbol{n}$-uplet d'éléments distincts de $\rm E$.

Propriété Le nombre de permutations d'un ensemble à $n$ éléments est $\boldsymbol{n!}$

Exemple Un professeur doit interroger 4 élèves à l'oral. Déterminer dans combien d'ordres différents le professeur peut le faire

Cours

Combinaison

Définition Soit $\rm E$ un ensemble fini à $n$ éléments et $k$ un entier naturel avec $k\leqslant n$. Une combinaison de $k$ élements de $\rm E$ est une partie (c'est à dire un sous-ensemble) de $\rm E$ à $k$ éléments

Le nombre de combinaisons de $k$ éléments parmi $n$ est noté $\begin{pmatrix} n \\ k \end{pmatrix}$

$\begin{pmatrix} n \\ k \end{pmatrix}$ est également appelé coefficient binomial

Ne pas confondre $\{a;b;c \}$ et $(a;b;c)$

Propriétés

$\begin{pmatrix} n \\ k \end{pmatrix}=?$

$\begin{pmatrix} n \\ k \end{pmatrix}=\dfrac{n!}{k!(n-k)!}$

Exemple Dans une classe de 35 élèves, les élèves décident d'envoyer une délégation de 4 élèves voir le proviseur. Déterminer le nombre de délégations que l'on peut faire

$\begin{pmatrix} n \\ 0 \end{pmatrix}=?$

$\begin{pmatrix} n \\ 0 \end{pmatrix}=1$

$\begin{pmatrix} n \\ 1 \end{pmatrix}=?$

$\begin{pmatrix} n \\ 1 \end{pmatrix}=n$

$\begin{pmatrix} n \\ 1 \end{pmatrix}$ désigne le nombre de parties de $\rm E$ à 1 élément. Or il y a $n$ parties à 1 éléments dans un ensemble à $n$ éléments.
Donc $\begin{pmatrix} n \\ 1 \end{pmatrix}=n$

Cette relation $\begin{pmatrix} n \\ 1 \end{pmatrix}=n$ a un sens sous réserve que $n \geqslant 1$.

$\begin{pmatrix} n \\ n-k \end{pmatrix}=?$

$\begin{pmatrix} n \\ n-k \end{pmatrix}=\begin{pmatrix} n \\ k \end{pmatrix}$

Cette relation traduit le fait que choisir $\boldsymbol{n-k}$ objets parmi $n$ revient à choisir ceux qu'on ne prend pas c'est à dire $k$ parmi $n$

Exemple Soit ${\rm E}=\{a;b;c;d;e\}$. Choisir $\{a;b;d\}$ revient à indiquer que l'on n'a pas choisi $\{c;e\}$. Donc choisir 3 objets parmi 5 revient à indiquer ceux qu'on ne prend pas c'est à dire 2 parmi 5. Et donc il y a autant de façons de choisir 3 objets parmi 5 que de choisir 2 parmi 5 et donc: $\begin{pmatrix} 5 \\ 3 \end{pmatrix}=\begin{pmatrix} 5 \\ 2 \end{pmatrix}$

On retrouve $\begin{pmatrix} n \\ n-k \end{pmatrix}=\begin{pmatrix} n \\ k \end{pmatrix}$ en utilisant la formule$\begin{pmatrix} n \\ k \end{pmatrix}=\dfrac{n!}{k!(n-k)!}$

Relation de Pascal

$\begin{pmatrix} n-1 \\ k-1 \end{pmatrix}+\begin{pmatrix} n-1 \\ k \end{pmatrix}=\begin{pmatrix} n \\ k \end{pmatrix}$

Cette relation est appelée relation de Pascal

Savoir utiliser cette relation pour construire le
triangle de Pascal

Ne pas apprendre cette formule par cœur mais la retrouver avec le triangle de Pascal

Démonstration de la relation de Pascal en vidéo

Écrire un programme Python pour déterminer le triangle de Pascal et les coefficients binomiaux

$\displaystyle\sum_{k=0}^{n}\begin{pmatrix} n \\ k \end{pmatrix}=?$

$\displaystyle\sum_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix}=2^n$

$\displaystyle\sum_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix}$ correspond au nombre de partie à 0 élément + au nombre de parties à 1 élément + au nombre de parties à 2 éléments,...., + au nombre de parties à $n$ éléments. Autrement dit $\displaystyle\sum_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix}$ correspond au nombre total de parties d'un ensemble. Et donc cette formule $\displaystyle\sum_{k=0}^{n} \begin{pmatrix} n \\ k \end{pmatrix}=2^n$ indique qu'un ensemble à $n$ éléments a $2^n$ parties.

Exemple Déterminer $\begin{pmatrix} 3 \\ 0 \end{pmatrix}+\begin{pmatrix} 3 \\ 1 \end{pmatrix}+\begin{pmatrix} 3 \\ 2 \end{pmatrix}+\begin{pmatrix} 3 \\ 3 \end{pmatrix}$

D'après la formule $\begin{pmatrix} 3 \\ 0 \end{pmatrix}+\begin{pmatrix} 3 \\ 1 \end{pmatrix}+\begin{pmatrix} 3 \\ 2 \end{pmatrix}+\begin{pmatrix} 3 \\ 3 \end{pmatrix}=2^3$
On peut le vérifier en comptant le nombre de parties d'un ensemble à 3 éléments. Soit ${\rm E}=\{ a;b;c\}$.
• $\begin{pmatrix} 3 \\ 0\end{pmatrix}$ est le nombre de partie de $\rm E$ à 0 élément. Il y en a qu'une seule: l'ensemble vide $\varnothing$. Donc $\begin{pmatrix} 3 \\ 0\end{pmatrix}=1$
• $\begin{pmatrix} 3 \\ 1\end{pmatrix}$ est le nombre de parties $\rm E$ à 1 élément. Il y en a 3: $\{a\}$, $\{b\}$ et $\{c\}$. Donc $\begin{pmatrix} 3 \\ 1\end{pmatrix}=3$
• $\begin{pmatrix} 3 \\ 2\end{pmatrix}$ est le nombre de parties de $\rm E$ à 2 éléments. Il y en a 3: $\{a;b\}$, $\{a;c\}$ et $\{b;c\}$. Donc $\begin{pmatrix} 3 \\ 2\end{pmatrix}=3$
• $\begin{pmatrix} 3 \\ 3\end{pmatrix}$ est le nombre de parties à 3 éléments de $\rm E$. Il y en a qu'une: $\{a;b;c\}$. Donc $\begin{pmatrix} 3 \\ 3\end{pmatrix}=1$
Finalement $\rm E$ a 8 parties ce qui correspond à $\begin{pmatrix} 3 \\ 0\end{pmatrix} + \begin{pmatrix} 3 \\ 1 \end{pmatrix}+\begin{pmatrix} 3 \\ 2\end{pmatrix} + \begin{pmatrix} 3 \\ 3\end{pmatrix}=1+3+3+1=8$.

Cours

Résumé du cours - Ce qu'il faut savoir pour faire les exercices

•

Les questions à se poser

• Cas particulier important

Méthode Souvent on rencontre la situation suivante ou une situation s'y ramenant:
Combien de façons a-t-on de placer $k$ objets identiques dans $n$ cases (chaque case ne pouvant contenir qu'un objet au maximum? En fait cela revient à numéroter les cases de 1 à n, puis à choisir $k$ emplacements parmi les $n$ cases pour les $k$ objets. Le nombre de façons de placer les $k$ objets parmi les $n$ cases correspond donc au nombre de combinaisons $\begin{pmatrix} n \\ k \end{pmatrix}$.

Exemple Combien y-a-t-il de façons de ranger $3$ œufs identiques parmi 10 cases?

Voir cet exercice qui illustre bien cette méthode et qui est très classique

Cours

Démonstration: Formule du triangle de Pascal

par le Dénombrement

et par le calcul

Cours

Démonstration: Parties d'un ensemble

Exercice 1:

Dénombrement - tiercé - Mot - Arrangement Combinaison

Déterminer le nombre de tiercés possibles dans une course avec $15$ chevaux et pas d'ex-aequo.
Déterminer le nombre de mots de quatre lettres, formés avec les $26$ lettres de l'alphabet.
De combien de façons peut-on garer $4$ voitures distinctes dans un parking à $6$ places?
On place $10$ points distincts sur un cercle. Dénombrer le nombre de droites passant par deux de ces points.

Exercice 2:

Dénombrement - Arrangement - Combinaison

On dispose de 8 souris, quatre mâles et quatre femelles. Combien de couples peut-on former afin qu'ils se reproduisent?
On choisit deux villes parmi 7 pour une course cycliste entre ces 2 villes. Combien y-a-t-il de choix si on ne distingue pas ville de départ et d'arrivée?
Même question mais en distinguant ville de départ et d'arrivée?
Dix nageurs participent à une course. Combien y-a-t-il de podiums possibles? Il n'y a pas d'ex-æquo. .

Exercice 3:

Dénombrement - Tirage avec et sans remise et simultané

On tire 4 boules dans une urne contenant 10 boules de couleurs différentes. Déterminer le nombre de tirages possibles lorsque:

on tire les 4 boules successivement et avec remise.
on tire les 4 boules successivement et sans remise.
on tire les 4 boules simultanément.

Exercice 4

Dénombrement - Arrangement Combinaison

Huit nageurs dont un français participent à une compétition. Un podium est constitué du premier, du deuxième et du troisième. Il n'y a pas d'ex-æquo.

Combien y-a-t-il de podiums possibles?
Déterminer le nombre de podiums possibles avec le nageur français de deux façons différentes.

Exercice 5:

Dénombrement - digicode

Un digicode à l'entrée d'un immeuble est constitué d'un clavier avec 13 touches marquées des trois lettres U, V et X et des 10 chiffres de 0 à 9. Un code est formé d'une lettre suivie d'une liste de 3 chiffres non nécessairement distincts. Rose a oublié le code.

Parmi combien de code différents Rose doit faire son choix?
Rose se souvient de la lettre du code. Parmi combien de code différents Rose fait-elle son choix?
Rose maintenant se souvient en plus de la lettre que les trois chiffres du code sont 6, 2 et 9, mais ne se souvient plus de l'ordre. Quelle est la probabilité que Rose trouve le bon code dès le premier essai?

Exercice 6: Dénombrement - Plaque d'immatriculation

La plaque d'immatriculation d'une voiture comporte deux lettres, distinctes de O, I et U pour éviter la confusion avec 0, 1 et V. Puis trois chiffres entre 0 et 9 inclus puis encore deux lettres distinctes de O, I et U. Déterminer le nombre de plaques d'immatriculation différentes possibles.

Exercice 7: Dénombrement - Arrangement Combinaison

On dispose de 6 cages sans limite de capacité. 3 cochons d'Inde discernables se précipitent dans les cages. De combien de façon peuvent-ils occuper les cages?

Exercice 8:

Dénombrement - Cartes

On tire au hasard et simultanément 5 cartes d'un jeu de 32. On constitue ainsi une main.

Matthias affirme que le nombre de mains possibles est égal à $32\times 31\times 30\times 29\times 28$. Qu'en pensez-vous? Corriger si nécessaire.
Zoé affirme que le probabilité que la main ne contienne aucun cœur est égale à $\dfrac {24}{32}$. Qu'en pensez-vous? Corriger si nécessaire.

Exercice 9: Dénombrement - rangement

Sur une étagère se trouvent 12 livres différents : 5 de mathématiques, 4 de physique-chimie et 3 de SVT.

De combien de manières différentes peut-on ranger ces livres sur l'étagère.
De combien de manières différentes peut-on ranger ces livres sur l'étagère en ayant les livres de mathématiques côte à côte ?

Exercice 10

Dénombrement - Loto Joker Quinté

Un joueur se demande ce qu'il en coûte de jouer tous les résultats possibles d'un jeu de hasard afin d'être sûr de gagner. Il s'intéresse au loto, au Joker et au Quinté.

Au Loto, il s'agit d'un tirage au hasard de 6 nombres parmi 49. Un même nombre ne peut être tiré plusieurs fois et l'ordre n'est pas pris en compte. Le prix d'une grille de loto est de 2 euros.
Au Joker, il s'agit d'un tirage successifs de 7 chiffres au hasard parmi les chiffres de 0 à 9. Un même chiffre peut être tiré plusieurs fois. Un jeu coûte 1 euro.
Au Quinté, on s'intéresse à l'arrivée dans l'ordre des 5 premiers chevaux d'une course comportant 18 partants. Le prix d'un pari est de 1,5 euro.

Exercice 11: Dénombrement et géométrie

Dans la figure ci-dessous, les droites $\mathscr{D_1}$, $\mathscr{D_2}$, $\mathscr{D_3}$ et $\mathscr{D_4}$ sont parallèles. De plus, les droites $\mathscr{D'_1}$, $\mathscr{D '_2}$, $\mathscr{D'_3}$, $\mathscr{D '_4}$, et $\mathscr{D'_5}$ sont parallèles.

Combien cette figure contient-elle de parallélogramme non aplatis?

Exercice 12:

Dénombrement et déplacement sur une grille

Une araignée en A se déplace sur une toile quadrillée représentée ci-dessous. Elle veut atteindre la mouche en M et se déplace uniquement de gauche à droite et de bas en haut.

Dénombrer tous les chemins possibles.
Dénombrer tous les chemins passant par P.
Dénombrer tous les chemins passant par P et Q.
Dénombrer tous les chemins passant par P ou Q.

Exercice 13:

Dénombrement et Python

Écrire un programme en Python qui génère les permutations d'une liste par 2 méthodes

Exercice 14: Dénombrement et Python

Écrire un programme en Python qui affiche pour un entier $n$ donné la liste des coefficients $\displaystyle\binom{n}{k}$ à l'aide de la relation de Pascal.

Exercice 15: Dénombrement et rangement

On dispose de trois tiroirs pour ranger cinq pulls différents. Chaque tiroir peut contenir les cinq pulls.

De combien de façons peut-on réaliser le rangement?
Combien y-a-t-il de rangements possibles pour lesquels aucun tiroir ne reste vide?

Exercice 16:

Dénombrement et anagramme - Nathan Hyperbole exercice 31 chapitre 2

Lorsqu'on permute les lettres d'un mot, on obtient une anagramme de ce mot.
On s'intéresse aux anagrammes du mot DIJON sans tenir compte de la signification ou non.

Combien y-a-t-il de telles anagrammes ?
Combien de ces anagrammes commencent par la lettre D ?
Combien de ces anagrammes commencent par une consonne ?
Combien de ces anagrammes commencent par une voyelle et finissent par une consomme ?

Exercice 17:

Dénombrement et anagramme

Lorsqu'on permute les lettres d'un mot, on obtient une anagramme de ce mot.
Dénombrer les anagrammes de SOPHIE, GASPARD puis ANANAS.

Exercice 18: Dénombrement et Poker Nathan hyperbole 45 chapitre 2 Terminale spécialité maths

Combien de mains différentes peut recevoir un joueur ?
Une couleur est une main constituée de $5$ cartes de la même famille.
1. Combien y a-t-il de mains de ce type en coeur ?
2. Combien y a-t-il de mains de ce type en tout ?
Un carré est une main composée de $4$ cartes de la même valeur et d'une cinquième carte quelconque.
1. En considérant la cinquième carte, déterminer combien de carrés présentent le numéro $10$ répété $4$ fois ?
2. Combien y a-t-il de carrés en tout ?

Exercice 19:

Dénombrement et Poker

Au poker, on utilise un jeu de $52$ cartes : $13$ valeurs (de l'as au $10$, puis valet, dame, roi) en quatre familles (cœur, carreau, pique, trèfle). Une main est un ensemble de $5$ cartes différentes. À l'aide de la calculatrice, retrouver les résultats présentés dans le tableau ci-contre.

Main	Combinaisons
Quinte flush	40
Carré	624
Full	3 744
Couleur	5 108
Quinte	10 200
Brelan	54 912
Deux paires	123 552
Paire	1 098 240
Carte haute	1 302 540
Total	2 598 960

Exercice 20: Dénombrement et jeton sur une grille

Sur un damier carré de cinq cases sur cinq, on pose au hasard cinq jetons indiscernables sur cinq cases différentes. Quelle est la probabilité de chacun des événements suivants:

un jeton exactement est placé par ligne et par colonne
Aucun jeton n'est sur une diagonale
Une colonne au moins est vide

Dénombrement - Arrangement & Combinaison

$k$-uplet - Arrangement - permutation

Factorielle

$k$-uplet

Arrangement

arrangement de $\rm E$

Permutation

Combinaison

Relation de Pascal

triangle de Pascal

Résumé du cours - Ce qu'il faut savoir pour faire les exercices

Les questions à se poser

Démonstration: Formule du triangle de Pascal

Démonstration: Parties d'un ensemble

Dénombrement - tiercé - Mot - Arrangement Combinaison

Dénombrement - Arrangement - Combinaison

Dénombrement - Tirage avec et sans remise et simultané

Dénombrement - Arrangement Combinaison

Dénombrement - digicode

Dénombrement - Cartes

Dénombrement - Loto Joker Quinté

Dénombrement et déplacement sur une grille

Dénombrement et Python

Dénombrement et anagramme - Nathan Hyperbole exercice 31 chapitre 2

Dénombrement et anagramme

Dénombrement et Poker