Arrangements, factorielle et combinaisons

Signaler

I. k-uplets d’éléments distincts d’un ensemble à nn éléments connu également sous le nom de k-arrangements

1.11.1 Définition

Soit un ensemble EE ayant nn éléments distincts.Un k-uplet (ou k-arrangement avec k1k\neq 1 ) est une suite ordonnée de kk éléments distincts choisis dans EE.

1.2.1.2. Nombre de k-uplets et arrangements

Définition de la factorielle n!n!

Définition : Soit nn un entier naturel non nul. On appelle factorielle de nn le nombre :
n!=1×2××nn! = 1 \times 2 \times \dots \times n

Par convention, 0!=10! = 1.

Définition d'un arrangement : Soit A un ensemble fini non vide à nn éléments et kk un entier naturel inférieur ou égal à nn . Un arrangement de kk éléments de AA (ou k -arrangement) est un k -uplet

d’éléments distincts de AA .

Comme l’ordre compte, pour construire un k-uplet de AA, on choisit :

Le premier élément parmi les nn disponibles, le deuxième élément parmi les (n1)(n-1) restants, etc., jusqu’au kk-ième élément.

Le nombre total de k-uplets distincts est donc : n×(n1)×(n2)××(nk+1)n \times (n-1) \times (n-2) \times \cdots \times (n-k+1).

On le note parfois A(n,k)A(n, k)ou P(n,k)P(n, k). En notation factorielle, cela s’écrit : n!(nk)!\dfrac{n!}{(n-k)!}.

Exemples :

Si A={1;2;3;4}A = \lbrace 1 ; 2 ; 3 ; 4 \rbrace, alors (1;3;4)(1 ; 3 ; 4) et (1;4;3)(1 ; 4 ; 3) sont deux arrangements de trois éléments de AA. Ce sont deux 3-arrangements de AA.

Remarque : Un arrangement de AA peut être interprété comme un tirage avec ordre et sans remise des éléments de AA.

Propriété : Soient AA un ensemble fini non vide à nn éléments, et kk un entier naturel tel que knk \leq n.
Le nombre de kk-arrangements de AA est égal à :
Ank=n×(n1)××(nk+1)=n!(nk)!{\boxed{A_n^k = n \times (n - 1) \times \dots \times (n - k + 1) = \dfrac{n!}{(n - k)!}}}

Exemple : On dispose de trois jetons et de cinq boîtes notées AA, BB, CC, DD et EE. On doit ranger les jetons dans les boîtes, une boîte ne pouvant pas contenir deux jetons.

On dispose de cinq possibilités pour le premier jeton, de quatre possibilités pour le deuxième jeton, et de trois possibilités pour le troisième jeton.

Les rangements possibles sont les 3-uplets d’éléments deux à deux distincts de l’ensemble T={A,B,C,D,E}T = \lbrace A, B, C, D, E \rbrace. Leur nombre est : 5×4×3=605 \times 4 \times 3 = 60.


II. Permutations d’un ensemble à nn éléments

Définition : Soit AA un ensemble fini non vide à nn éléments. Une permutation de AA est un nn-uplet d’éléments distincts de AA.

Remarque : Une permutation est un nn-arrangement.

Exemple : Si A={1;2;3}A = \lbrace 1 ; 2 ; 3 \rbrace, les permutations de AA sont :
{{1;2;3};{1;3;2};{2;1;3};{2;3;1};{3;1;2};{3;2;1}}\lbrace \lbrace 1 ; 2 ; 3 \rbrace ; \lbrace 1 ; 3 ; 2 \rbrace ; \lbrace 2 ; 1 ; 3 \rbrace ; \lbrace 2 ; 3 ; 1 \rbrace ; \lbrace 3 ; 1 ; 2 \rbrace ; \lbrace 3 ; 2 ; 1 \rbrace \rbrace.

Propriété : Le nombre de permutations d’un ensemble fini non vide à nn éléments est : n!n!.

Exemple : Si A={1;2;3}A = \lbrace 1 ; 2 ; 3 \rbrace, on a bien 3!=63! = 6 permutations possibles.

2.2. Nombre de permutations

Une permutation d’un ensemble de nn éléments est un réarrangement complet de ces nn éléments.

Le nombre de permutations de nn éléments (c’est-à-dire, le nombre de façons de les ordonner) est  : n!n!.

Remarque :

Les permutations correspondent au cas particulier des k-uplets où k=nk = n.

Dans ce cas, la formule n!(nk)!\dfrac{n!}{(n-k)!} devient n!(nn)!=n!0!=n!\dfrac{n!}{(n-n)!} = \dfrac{n!}{0!} = n!.


III. Parties et combinaisons d'un ensemble fini

1. Parties

Soit un ensemble EE fini dont la cardinalité est nn, c’est-à-dire card(E)=n \mathrm{card}(E) = n .

On appelle partie (ou sous-ensemble) de EE tout ensemble AA tel que AE A \subseteq E .On cherche à déterminer le nombre total de parties de EE. On note généralement l’ensemble de toutes les parties de EE par P(E) \mathcal{P}(E) .

La question est donc : Combien y a-t-il d’éléments dans P(E)\mathcal{P}(E) ?

Un exemple : Prenons un petit ensemble EE :

\circ\quad Si E=E = \varnothing (ensemble vide, card(E)=0\mathrm{card}(E) = 0), la seule partie de EE est \varnothing elle-même. Donc card(P(E))=1=20 \mathrm{card}(\mathcal{P}(E)) = 1 = 2^0 .

\circ\quadSi E=aE = {a} (un seul élément, card(E)=1\mathrm{card}(E) = 1), les parties de EE sont \varnothing et {a} \{a\} .
Il y en a 2 au total, donc card(P(E))=2=21 \mathrm{card}(\mathcal{P}(E)) = 2 = 2^1 .

\circ\quad Si E={a,b}E = \{a, b\} (deux éléments, card(E)=2\mathrm{card}(E) = 2), les parties de EE sont :
,{a},{b},{a,b}. \varnothing\,, \{a\}\,, \{b\}\,, \{a\,, b\}.
Il y en a 4, donc card(P(E))=4=22 \mathrm{card}(\mathcal{P}(E)) = 4 = 2^2 .

Conjecture : lorsque EE a nn éléments, le nombre de ses parties serait 2n2^n. Voyons pourquoi.

Justification par le principe multiplicatif

a) Décomposition de la formation d’une partie

Pour construire une partie (sous-ensemble) de EE :

\circ\quad Chaque élément de EE peut soit être inclus dans la partie,

\circ\quad soit être exclu de la partie.Il y a donc 2 choix (inclure ou non) pour chaque élément.

b) Application du principe multiplicatif

Puisque le choix concernant chaque élément est indépendant du choix fait pour les autres éléments, on applique le principe multiplicatif :Nombre total de façons de choisir = produit du nombre de choix pour chaque élément.

\circ\quad Pour chaque élément de EE, on a 2 possibilités.

\circ\quad Il y a nn éléments dans EE. Donc, card(P(E))=2×2××2nfois=2n.\mathrm{card}(\mathcal{P}(E)) = \underbrace{2 \times 2 \times \cdots \times 2}_{n\text{fois}}= 2^n.

Conclusion : Pour un ensemble fini E de cardinal n, le nombre de ses parties est card(P(E))=2n.\boxed{\begin{array}{l}\textbf{Pour un ensemble fini } E \textbf{ de cardinal }n,\\[6pt] \textbf{ le nombre de ses parties est } \mathrm{card}\bigl(\mathcal{P}(E)\bigr) = 2^n.\end{array}}

2. Combinaisons

Définition : Soient nn et kk deux entiers naturels tels que 0kn0 \leq k \leq n, et EE un ensemble fini de cardinal nn. On appelle combinaison de kk éléments de EE toute partie de EE ayant kk éléments.

Le nombre de combinaisons de kk éléments de EE est noté (nk)\binom{n}{k}.

Remarque : Les nombres (nk)\binom{n}{k} sont également appelés coefficients binomiaux et se lisent « kk parmi nn ».

Exemple :
Soit A={1;2;3}A = \lbrace 1 ; 2 ; 3 \rbrace.
i) Les parties de AA sont : \emptyset, {1}\lbrace 1 \rbrace, {2}\lbrace 2 \rbrace, {3}\lbrace 3 \rbrace, {1;2}\lbrace 1 ; 2 \rbrace, {1;3}\lbrace 1 ; 3 \rbrace, {2;3}\lbrace 2 ; 3 \rbrace, {1;2;3}\lbrace 1 ; 2 ; 3 \rbrace.
ii) Il y a 3 parties à 1 élément.
iii) (32)=3\begin{pmatrix}3\\2\end{pmatrix} = 3.

Propriété :
Soient nn et kk deux entiers naturels tels que knk \leq n, alors :
(nk)=n!k!(nk)!\begin{pmatrix}n\\k\end{pmatrix} = \dfrac{n!}{k!(n-k)!}.

i) Symétrie : (nk)=(nnk)\begin{pmatrix}n\\k\end{pmatrix} = \begin{pmatrix}n\\n-k\end{pmatrix}.

ii) Exemples particuliers :
\circ\quad si k=0k=0 , (n0)=1\begin{pmatrix}n\\0\end{pmatrix} = 1: Il n’y a qu’une seule façon de ne rien choisir : le sous-ensemble vide \varnothing.
\circ\quad si k=1k=1 , (n1)=n\begin{pmatrix}n\\1\end{pmatrix} = n : Choisir un élément parmi nn donne nn sous-ensembles à 1 élément.
\circ\quad si k=2k=2 , (n2)=n(n1)2\begin{pmatrix}n\\2\end{pmatrix} = \dfrac{n(n-1)}{2} : Pour choisir 2 éléments sans ordre parmi nn, on a n(n1)2\dfrac{n(n-1)}{2} possibilités.

\circ\quad (n+1)!=n!×(n+1)(n+1)!=n!\times (n+1) est une relation intéressante (simplification de fractions etc.) dont on peut donner un exemple 7!=6!×77!=6!\times 7

iii) Relation de Pascal :
Pour tous entiers naturels nn et kk tels que 1kn11 \leq k \leq n-1, on a :
(nk)=(n1k1)+(n1k)\begin{pmatrix}n\\k\end{pmatrix} = \begin{pmatrix}n-1\\k-1\end{pmatrix} + \begin{pmatrix}n-1\\k\end{pmatrix}.


5. Symétrie et triangle de Pascal

5.1. Symétrie

On a la propriété de symétrie :
(nk)=(nnk)\begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}n\\n-k\end{pmatrix}

Autrement dit, choisir kk éléments ou ne pas choisir kk éléments (ce qui revient à choisir nkn-k éléments) donne le même nombre de sous-ensembles.

5.2. Relation de Pascal

Les coefficients de combinaisons vérifient la relation de Pascal :
(nk)=(n1k1)+(n1k)\begin{pmatrix}n\\k\end{pmatrix} = \begin{pmatrix}n-1\\k-1\end{pmatrix} + \begin{pmatrix}n-1\\k\end{pmatrix}.

Cette relation donne naissance au triangle de Pascal. On peut l’interpréter de manière combinatoire : pour choisir kk éléments parmi nn, on distingue les sous-ensembles contenant un élément spécifique (disons le premier) et ceux ne le contenant pas.

Triangle de Pascal : (issu de Wikipedia)

picture-in-textPrésenté également souvent ainsi :

picture-in-text

À l'intersection de la ligne nn et de la colonne kk, on lit l'entier (nk)\begin{pmatrix}n\\k\end{pmatrix}.

On commence par écrire les « 1 » dans la 1ère colonne et sur la diagonale, puis on utilise la relation de Pascal, selon le schéma :

(nk)=(n1k1)+(n1k)\begin{pmatrix}n\\k\end{pmatrix}=\begin{pmatrix}n-1\\k-1\end{pmatrix}+\begin{pmatrix}n-1\\k\end{pmatrix}


Propriété : Soit nn un entier naturel. Alors : k=0n(nk)=2n\displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n

Démonstration :
Par dénombrement, on compte le nombre de parties d’un ensemble à nn éléments.

\circ\quad Il y a (n0)\begin{pmatrix}n\\0\end{pmatrix} parties à 0 élément, (n1)\begin{pmatrix}n\\1\end{pmatrix} parties à 1 élément, ...

\circ\quad En tout, il y a 2n2^n parties d’un ensemble à nn éléments (chaque élément peut être présent ou absent).

Ainsi, en sommant les (nk)\begin{pmatrix}n\\k\end{pmatrix} pour kk allant de 00 à nn, on obtient la relation : k=0n(nk)=2n\displaystyle\sum_{k=0}^n \binom{n}{k} = 2^n.

IV. Lien entre les sous-ensembles et d’autres objets combinatoires

Lorsque nous comptons les parties (sous-ensembles) d’un ensemble à nn éléments, nous obtenons un total de 2n2^n. Ce résultat se retrouve de manière équivalente dans plusieurs situations :

1.1. nombre de parties de EE à nn éléments et n-uplets de {0,1}\{0,1\}

Pour construire un sous-ensemble de EE, on considère nn étapes où pour chaque élément de EE, on décide de le choisir ou de ne pas le choisir pour l’inclure dans le sous-ensemble. Il y a donc deux possibilités par étape et il y a nn étapes. On retrouve bien qu'il y a 2n2^n sous-ensembles possibles.

Ainsi, il existe une correspondance bijective entre les sous-ensembles de EE et les nn-uplets de {0,1}\{0,1\}.

22 Mots de longueur nn sur un alphabet à deux éléments {0,1}\{0,1\}

Un mot binaire de nn lettres (0 ou 1) correspond aussi à un sous-ensemble (présence/absence).

33 Chemins dans un arbre

Dans un arbre binaire complet de hauteur nn, chaque étage représente un choix « à gauche » ou « à droite » (analogue à 0 ou 1).

Un chemin complet du sommet à une feuille peut donc être vu comme une suite de nn choix, exactement comme les nn-uplets de {0,1}\{0,1\}.

Le nombre total de chemins (et donc de feuilles) est 2n2^n.

44 Issues dans une succession de nn épeuves de Bernoulli

Une épreuve de Bernoulli est un « tirage » à deux résultats possibles (réussite/échec, pile/face, etc.).

Sur nn épreuves, la collection de résultats forme une suite binaire de longueur nn.

Le nombre total de suites (donc d’issues possibles) est également 2n2^n.

Conclusion
Toutes ces situations (sous-ensembles d’un ensemble à nn éléments, nn-uplets de {0,1}\{0,1\}, mots binaires de longueur nn, chemins dans un arbre binaire, issues de nn épreuves de Bernoulli) sont reliées par une bijection commune et se comptent toutes par la même formule : 2n\boxed{2^n}

En résumé :

\circ\quad Factorielle : sert à compter les arrangements complets (permutations) de nn objets : n!n!

\circ\quad k-uplets (arrangements partiels) : on prend kk objets dans un ordre précis :n!(nk)!\dfrac{n!}{(n-k)!}

\circ\quadCombinaisons : on prend kk objets sans ordre : (nk)=n!k!(nk)!\begin{pmatrix}n\\k\end{pmatrix} = \dfrac{n!}{k!\,(n-k)!}, avec diverses interprétations (mots binaires, chemins, etc.).

\circ\quad Le triangle de Pascal : donne à la fois une interprétation combinatoire et une construction pratique des nombres (nk)\begin{pmatrix}n\\k\end{pmatrix}.

IV. Exercices d'application directe

Exercice 1 :

Soient A={1,2}A = \{1, 2\} et B={a,b,c}B = \{a, b, c\}.

1.1. Déterminez l'ensemble des 22-uplets formés avec les éléments de AA.

2.2. Déterminez l'ensemble des 33-uplets formés avec les éléments de AA et BB, où les deux premiers éléments proviennent de AA et le troisième de BB.

3.3. Combien y a-t-il de 33-uplets au total dans le cas de la question précédente ?

Solution exercice 1 :

1.1. Les 22-uplets de AA sont : (1,1)(1, 1), (1,2)(1, 2), (2,1)(2, 1), (2,2)(2, 2).

2.2. Les 33-uplets formés sont :

(1,1,a)(1, 1, a), (1,1,b)(1, 1, b), (1,1,c)(1, 1, c)

(1,2,a)(1, 2, a), (1,2,b)(1, 2, b), (1,2,c)(1, 2, c)

(2,1,a)(2, 1, a), (2,1,b)(2, 1, b), (2,1,c)(2, 1, c)

(2,2,a)(2, 2, a), (2,2,b)(2, 2, b), (2,2,c)(2, 2, c).

Il y a 4×3=124 \times 3 = 12 33-uplets.



Exercice 2 :

Une urne contient 1010 boules, numérotées de 11 à 1010.

1.1. Combien de façons existe-t-il de choisir 44 boules parmi les 1010 sans tenir compte de l'ordre ?
2.2. Combien de façons existe-t-il de choisir 66 boules parmi les 1010 ?
3.3. Combien de façons existe-t-il de ne pas choisir une seule boule, c'est-à-dire d'en choisir 99 ?


Solution exercice 2 :

1.1. Le nombre de façons de choisir 44 boules parmi 1010 est :
(104)=10!4!(104)!=10×9×8×74×3×2×1=210 \begin{pmatrix}10\\4\end{pmatrix} = \dfrac{10!}{4!(10-4)!} = \dfrac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1} = 210 .

2.2. Le nombre de façons de choisir 66 boules parmi 1010 est :
(106)=(104)=210 \begin{pmatrix}10\\6\end{pmatrix} = \begin{pmatrix}10\\4\end{pmatrix} = 210 .
(Remarque : (nk)=(nnk) \begin{pmatrix}n\\k\end{pmatrix} = \begin{pmatrix}n\\n-k\end{pmatrix} .)

3.3. Le nombre de façons de choisir 99 boules parmi 1010 est :
(109)=(101)=10 \begin{pmatrix}10\\9\end{pmatrix} = \begin{pmatrix}10\\1\end{pmatrix} = 10 .


Exercice 3 :

1.1. Combien de mots de 55 lettres distinctes peut-on former en utilisant les lettres AA, BB, CC, DD et EE ?

2.2. Combien de mots différents de 44 lettres peut-on former en utilisant les lettres AA, BB, CC, DD et EE sans répétition, et en considérant l'ordre des lettres ?

3.3. En utilisant toutes les lettres du mot "PARIS", combien de mots différents peut-on former, en considérant que chaque mot est une permutation des lettres ?


Solution exercice 3 :

1.1. En utilisant toutes les lettres AA, BB, CC, DD, et EE, on forme 5!5! mots différents :
5!=5×4×3×2×1=120 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 .

2.2. Pour former des mots de 44 lettres sans répétition, le nombre de possibilités est donné par A(5,4)A(5, 4) nombre de 44-uplets formés avec ces 55 lettres :
A(5,4)=5!(54)!=5×4×3×2×11=5×4×3×2=120 A(5, 4) = \dfrac{5!}{(5-4)!} = \dfrac{5 \times 4 \times 3 \times 2 \times 1}{1} = 5 \times 4 \times 3 \times 2 = 120 .

3.3. En utilisant toutes les lettres de "PARIS", le nombre de mots différents formés est :
5!=120 5! = 120 .