Revenir
Revenir

Combinaisons

un ensemble fini de cardinal

Sommaire

Combinaison d'éléments d'un ensembleNombre de combinaisons d'éléments d'un ensemble☛ Déterminer un nombre de combinaisons d'éléments d'un ensemble☛ Autres exemples de calcul de nombre de combinaisonsTriangle de Pascal - Activité préparatoireTriangle de Pascal✎ Problèmes de dénombrement

Combinaison d'éléments d'un ensemble

Définition
Soit
EEE
un ensemble fini de cardinal
nnn
, où
nnn
est un entier naturel.
Soit
kkk
un entier naturel tel que
0⩽k⩽n0 ⩽ k ⩽ n0⩽k⩽n
.
On appellecombinaisonde
kkk
éléments de
EEE
toute partie (sous-ensemble) de
EEE
ayant
kkk
éléments.
Exemples
Soit
E={1 ; 2 ; 3 ; 4 ; 5 ; 6}E = \{ 1~;~ 2~;~ 3~;~ 4~;~ 5~;~ 6 \}E={1 ; 2 ; 3 ; 4 ; 5 ; 6}
l'ensemble des résultats d'un lancer de dé cubique, dont les faces sont numérotées de
111
à
666
.
    • L'ensemble des issues correspondant aux nombres pairs est le sous-ensemble 
{2 ; 4 ; 6}\{ 2~;~ 4~;~ 6 \}{2 ; 4 ; 6}
. C'est une combinaison de
333
éléments de
EEE
.
    • L'ensemble des issues correspondant aux multiples de
333
est le sous-ensemble
{3 ; 6}\{ 3~;~ 6 \}{3 ; 6}
. C'est une combinaison de
222
éléments de
EEE
.
Remarque
{3 ; 6}\{ 3~;~ 6 \}{3 ; 6}
et
{6 ; 3}\{ 6~;~ 3 \}{6 ; 3}
correspondent au même sous-ensemble.

Nombre de combinaisons d'éléments d'un ensemble

Propriété
Soit
kkk
 et
nnn
entiers naturels tels que
0⩽k⩽n0 ⩽ k ⩽ n0⩽k⩽n
.
Le nombre de combinaisons à
kkk
éléments d'un ensemble
EEE
à
nnn
éléments est noté
(nk)\displaystyle \binom nk(kn​)
 et se lit : «
kkk
parmi
nnn
».
Ce nombre vaut : 
(nk)=n(n−1)...(n−k+1)k!=n!k!(n−k)!\displaystyle \binom nk = \dfrac{n(n-1)...(n-k+1)}{k!} =\boxed{\dfrac{n!}{k!(n-k)!}}(kn​)=k!n(n−1)...(n−k+1)​=k!(n−k)!n!​​
.
Démonstration
Une liste de \(k\)éléments distincts parmi
nnn
est définie par : 
    • le choix des\(k\)éléments de
EEE
pris parmi les
nnn
éléments de 
(nk)\displaystyle \binom{n}{k}(kn​)
 manières ;
    • la manière d'arranger ces\(k\)éléments entre eux, de
k!k!k!
manières possibles.
Alors, par le principe multiplicatif, le nombre de listes de \(k\) éléments distincts est donné par \(\displaystyle \binom nk \times k!\). Or, ce nombre est égal à 
n!(n−k)!\dfrac{n!}{(n-k)!}(n−k)!n!​
. D'où  
(nk)=n!k!(n−k)!\boxed{\displaystyle \binom nk = \dfrac{n!}{k!(n-k)!}}(kn​)=k!(n−k)!n!​​
.
Exemples
(50)=1\displaystyle \binom 50 = 1(05​)=1
, 
(51)=5\displaystyle \binom 51 = 5(15​)=5
, 
(52)=10\displaystyle \binom 52 = 10(25​)=10
, 
(53)=10\displaystyle \binom 53 = 10(35​)=10
, 
(54)=5\displaystyle \binom 54 = 5(45​)=5
, 
(55)=1\displaystyle \binom 55 = 1(55​)=1
.
Propriété
Pour tout
n⩾0n ⩾ 0n⩾0
, on a : 
(n0)=1\displaystyle \binom n0 = 1(0n​)=1
, 
(n1)=n\displaystyle \binom n1 = n(1n​)=n
 et 
(n2)=n(n−1)2\displaystyle \binom n2 = \dfrac{n(n-1)}{2}(2n​)=2n(n−1)​
.
Démonstration
Soit 
nnn
un entier naturel.
(n0)=n!0!×(n−0)!=n!1×n!=1\displaystyle \binom n0 =\dfrac{n!}{0!\times (n-0)!}=\dfrac{n!}{1\times n!}=1(0n​)=0!×(n−0)!n!​=1×n!n!​=1
.
(n1)=n!1!×(n−1)!=(n−1)!×n1×(n−1)!=(n−1)!(n−1)!=1\displaystyle \binom n1 =\dfrac{n!}{1!\times (n-1)!}=\dfrac{(n-1)!\times n}{1\times (n-1)!}=\dfrac{(n-1)!}{(n-1)!}=1(1n​)=1!×(n−1)!n!​=1×(n−1)!(n−1)!×n​=(n−1)!(n−1)!​=1
.
(n2)=n!(n−2)!2!=n(n−1)(n−2)!(n−2)!×2=n(n−1)2\displaystyle \binom n2 = \dfrac{n!}{(n-2)!2!} = \dfrac{n(n-1)(n-2)!}{(n-2)! \times 2} = \dfrac{n(n-1)}{2}(2n​)=(n−2)!2!n!​=(n−2)!×2n(n−1)(n−2)!​=2n(n−1)​
.
Remarque
Le nombre de parties d'un ensemble à
nnn
éléments est  :
∑k=0n(nk)\displaystyle \sum_{k=0}^n \binom{n}{k}k=0∑n​(kn​)
.
Donc 
∑k=0n(nk)=2n\displaystyle \sum_{k=0}^n \binom{n}{k}=2^nk=0∑n​(kn​)=2n
.

☛ Déterminer un nombre de combinaisons d'éléments d'un ensemble

Énoncé
Dans une classe de
353535
élèves, de combien de manières peut-on choisir un binôme de délégués ?
Solution
Il s'agit de calculer le nombre de combinaisons de
222
éléments parmi
353535
: 
(352)=35!33!×2!=35×342=595\displaystyle \binom{35}{2} = \dfrac{35!}{33!\times 2!}=\dfrac{35\times 34}{2}=595(235​)=33!×2!35!​=235×34​=595
.
Il y a donc
595595595
manières de choisir un binôme de délégués dans cette classe.

☛ Autres exemples de calcul de nombre de combinaisons

Énoncé 1
Le tirage du Loto correspond à
666
tirages d'une boule sans remise parmi
494949
boules numérotées de 
111
à
494949
. Calculer les chances de gagner au Loto.
Solution
On peut assimiler ces tirages à un tirage simultané de
666
boules parmi
494949
.
Le nombre de combinaisons possibles est donc de 
(496)=49!6!×43!=13 983 816\displaystyle \binom{49}{6} = \dfrac{49!}{6! \times 43!} = 13\,983\,816(649​)=6!×43!49!​=13983816
.
On a donc une chance sur près de
141414
millions de gagner au Loto...
Énoncé 2
Une araignée se trouve, en
A\text AA
, sur une toile aux motifs carrés. Une mouche est immobilisée par la toile, au point
M\text MM
.
L'araignée souhaite attraper la mouche mais ne peut se déplacer que le long des filins de sa toile, vers la droite et vers le haut.
Combien de chemins différents peut prendre l'araignée pour atteindre la mouche ?
Solution
Le nombre total de cases à parcourir par l'araignée, pour atteindre la mouche, est de
555
cases horizontalement et de
333
cases verticalement.
Il s'agit donc de créer un chemin dans lequel on représente par
D\text DD
le déplacement d'une case vers la droite et par 
H\text HH
le déplacement d'une case vers le haut. Par exemple, un chemin possible est
DDHDDHHD\text {DDHDDHHD}DDHDDHHD
, représenté ci-dessous.
On doit dénombrer le nombre de chemins. On est donc amené à créer des « mots » de
5+3=85 + 3 = 85+3=8
lettres.
On se pose la question du nombre de manières de choisir les emplacements des 
555
lettres 
D\text DD
dans le « mot ». On peut choisir les
555
emplacements de
D\text DD
parmi les
888
positions possibles.
Or,
(85)=8!5!×3!=8×7×63×2×1=56\displaystyle \binom 85 = \dfrac{8!}{5!\times 3!}=\dfrac{8 \times 7\times 6}{3 \times 2 \times 1}=56(58​)=5!×3!8!​=3×2×18×7×6​=56
. Il y a donc
565656
manières de choisir les emplacements de la lettre 
D\text DD
dans les « mots ».
La manière de choisir les emplacements de la lettre 
D\text DD
dans le « mot » va induire les emplacements de la lettre 
H\text HH
dans le « mot ».
Conclusion: il existe
565656
chemins différents qui permettent à l'araignée d'atteindre la mouche.
Remarque
Par symétrie, il est équivalent de chercher à déterminer le nombre de manières de placer les 
333
lettres ​​
HHH
parmi les
888
positions possibles : 
(83)=(88−3)=(85)=56\displaystyle \binom83 = \binom{8}{8-3} = \binom 85 = 56(38​)=(8−38​)=(58​)=56
.

Triangle de Pascal - Activité préparatoire

Développement des expressions binomiales
1. Développer et réduire les expressions
(x+1)0(x+1)^0(x+1)0
,
(x+1)1(x+1)^1(x+1)1
,
(x+1)2(x+1)^2(x+1)2
et
(x+1)3(x+1)^3(x+1)3
.
On obtient alors des expressions polynomiales avec des termes de la forme
axkax^kaxk
, où 
0⩽k⩽n0 ⩽ k ⩽ n0⩽k⩽n
et 
aaa
un nombre réel.
2.Compléter le tableau suivant avec les valeurs des coefficients des termes
xkx^kxk
dans les développements précédents (pour des valeurs de
nnn
de
000
à
333
).
3. Observer les valeurs du tableau et prévoir les valeurs des lignes suivantes. Comment les obtient-on ?
4. En déduire sans calcul le développement de
(x+1)5(x+1)^5(x+1)5
.

Triangle de Pascal

DéfinitionTriangle de Pascal
Les coefficients du tableau précédent forment letriangle de Pascal, du nom du mathématicien français Blaise Pascal (1623 – 1662).
Remarque
Les coefficients apparaissant dans le tableau représentent les nombres de combinaisons de
kkk
éléments parmi
nnn
, où 
kkk
et
nnn
 sont des entiers naturels tels que
0⩽k⩽n0\leqslant k\leqslant n0⩽k⩽n
.
En effet, dans le développement de 
(x+1)5(x+1)^5(x+1)5
, le coefficient de 
x3x^3x3
 est déterminé par le choix de
333
termes
xxx
parmi les
555
facteurs
(x+1)(x + 1)(x+1)
apparaissant dans le produit. Ce coefficient sera donc 
(53)\displaystyle \binom 53(35​)
, ce qui justifie que ces nombres s'appellentcoefficients binomiaux.
Propriétés
    • SymétriePour tout
kkk
tel que 
0⩽k⩽n0 ⩽ k ⩽ n0⩽k⩽n
, on a : 
(nk)=(nn−k)\displaystyle \boxed{\binom nk = \binom{n}{n-k}}(kn​)=(n−kn​)​
.
    • Relationde PascalPour tout
kkk
tel que
0⩽k⩽n−10 ⩽ k ⩽ n - 10⩽k⩽n−1
, on a : 
(nk)=(n−1k−1)+(n−1k)\displaystyle \boxed{\binom nk = \binom{n-1}{k-1} + \binom{n-1}{k}}(kn​)=(k−1n−1​)+(kn−1​)​
.
Exemple
Dans le tableau ci-dessous, on a lesrelationssuivantes, mises en évidence en couleur : 
(30)+(31)=(41)\displaystyle \binom 30 + \binom 31 = \binom 41(03​)+(13​)=(14​)
,
(53)+(54)=(64)\displaystyle \binom 53 + \binom 54 = \binom 64(35​)+(45​)=(46​)
, 
(61)+(62)=(72)\displaystyle \binom 61 + \binom 62 = \binom 72(16​)+(26​)=(27​)
. 
Démonstration
1. Symétrie
Pour
kkk
et
nnn
entiers naturels tels que 
0⩽k⩽n0\leqslant k\leqslant n0⩽k⩽n
, on a 
(nn−k)=n!(n−k)!(n−(n−k))!=n!(n−k)!k!=(nk)\displaystyle \binom{n}{n-k} = \dfrac{n!}{(n-k)!(n-(n-k))!}=\dfrac{n!}{(n-k)!k!}=\binom{n}{k}(n−kn​)=(n−k)!(n−(n−k))!n!​=(n−k)!k!n!​=(kn​)
.
2. Relation de Pascal 
Par dénombrement
Soit
nnn
et
kkk
tel que
0⩽k⩽n−−10 ⩽ k ⩽ n -- 10⩽k⩽n−−1
.
On considère un ensemble
EEE
fini à 
nnn
éléments.
On cherche à exprimer la relation entre le nombre de partiesde
EEE
à
kkk
éléments et le nombre de parties de
EEE
à
k−1k - 1k−1
éléments.
Soit 
aaa
 un élément fixé de
EEE
. On considère les parties de
EEE
à
kkk
éléments contenant
aaa
et celles à
kkk
éléments ne le contenant pas. 
    • Pour les parties de
EEE
à
kkk
éléments qui contiennentl'élément
aaa
, les
k−1k - 1k−1
autres éléments sont choisis parmi les
n−1n - 1n−1
éléments autres que
aaa
, donc de 
(n−1k−1)\displaystyle \binom{n-1}{k-1}(k−1n−1​)
 manières.
    • Pour les parties de
EEE
à
kkk
éléments qui ne contiennent pas l'élément
aaa
, les
kkk
éléments sont choisis parmi les
n−1n - 1n−1
éléments autres que
aaa
, donc de
(n−1k)\displaystyle \binom{n-1}{k}(kn−1​)
 manières.
Comme ces parties sont disjointes, elles réalisent une partition de
EEE
.
Par le principe additif, on obtient le résultat cherché.
Par le calcul
Soit
nnn
et
kkk
tels que
0⩽k⩽n−10 ⩽ k ⩽ n - 10⩽k⩽n−1
.
\begin{array}[t]{rcl}\displaystyle \binom{n-1}{p-1}+\binom{n-1}{p} & =& \dfrac{(n-1)!}{(p-1)!(n-1-(p-1))!}+\dfrac{(n-1)!}{p!(n-1-p)!}\\ & = &\dfrac{(n-1)!}{(p-1)!(n-1-p+1)!}+\dfrac{(n-1)!}{p!(n-1-p)!}\\ &=& \dfrac{(n-1)!}{(p-1)!(n-p)!}+\dfrac{(n-1)!}{p!(n-p-1)!}\\ & =& \dfrac{(n-1)!\times p}{(p-1)!(n-p)!\times p}+\dfrac{(n-1)!\times (n-p)}{p!(n-p-1)!\times (n-p)}\\ &=& \dfrac{(n-1)!\times p}{p!(n-p)!}+\dfrac{(n-1)!\times (n-p)}{p!(n-p)!}\\ & =&\dfrac{(n-1)!\times p+(n-1)!\times (n-p)}{p!(n-p)!}\\ &=& \dfrac{(n-1)!\times [ p+(n-p)]}{p!(n-p)!}\\ &=& \dfrac{(n-1)!\times n}{p!(n-p)!}= \dfrac{n!}{p!(n-p)!}= \displaystyle \binom np\\ \end{array}

✎ Problèmes de dénombrement

Méthode