COMBINAISONS, BINOME DE NEWTON

1 ) P–LISTES ET ARRANGEMENTS
Soit E un ensemble fini ayant n éléments et p un entier supérieur ou égal à 1 .
Définition et propriété
On appelle p-liste d’éléments de E, toute suite finie ( x1 , x2 , … , xp ) de p • Une p-liste est toujours ordonnée.
éléments pris dans E .
• Les éléments x1 , x2 , … , xp ne sont pas
Le nombre de p-listes d’un ensemble E ayant n éléments est n . p nécessairement distincts les uns des autres.

• On parle de suites … on utilise donc des parenthèses

Exemple : On lance un dé à 6 faces trois fois de suite .

Le résultat de l’épreuve est une 3 – liste d’éléments de l’ensemble E défini par E = { 1 ; 2 ; 3 ; 4 ; 5 ; 6 }

Par exemple la liste ( 1 ; 5 ; 4 ) indique que le premier lancé a donné 1 , le deuxième lancé a donné 5 …
Les listes ( 1 ; 5 ; 4 ) et ( 1 ; 4 ; 5 ) sont différentes.
Le nombre de 3 – listes est 6 3 = 6 × 6 × 6 =216
Ainsi le nombre de résultats possibles est 216 . ( on peut faire un arbre … )
Remarques :
• Une liste à deux éléments de E s’appelle un couple d’éléments de E .
• Une liste à trois ( quatre, cinq … ) éléments s’appelle un triplet ( quadruplet, quintuplet … )
• Plus généralement, une p-liste est aussi appelé un p-uplet.

Définition
Un arrangement de p ( avec p ≤ n ) éléments de E est une p – liste d’éléments de E deux à deux distincts .
Remarques :
• Il n’est pas possible de prendre plus de n éléments distincts dans un ensemble à n éléments … donc p ≤ n .
• Un arrangement est toujours ordonné, sans répétition possible.
Exemple :
On dispose de quatre cartons . Sur chacun d’eux, on écrit une lettre différente du mot « MATH » et on place les cartons dans une urne.
On tire successivement et sans remise trois cartons dans l’urne.
Le résultat de l’épreuve est un arrangement de 3 éléments de l’ensemble Ω , défini par Ω = { M , A , T , H }
Par exemple l’arrangement ( T , A , M ) indique que la première lettre tirée est T, la deuxième A et la troisième M .
Pour former un arrangement à 3 éléments de l’ensemble Ω , on a :
• 4 choix, pour le premier élément
• 3 choix, pour le deuxième élément ( on retire le premier carton ) x y z
• 2 choix, pour le troisième élément ( on retire les deux premiers cartons )

On obtient donc 4 × 3 × 2 = 24 arrangements possibles . Ce nombre est noté A 34 4 × 3 × 2 = 24

Propriété
p.
Le nombre d’arrangements de p éléments ( 1 ≤ p ≤ n ) d’un ensemble à n éléments se note A n

Si p = 1 , alors A 1n = n Si 1 < p ≤ n , alors A pn = n ( n –1 ) … ( n – p + 1 )

( p facteurs )

2 ) PERMUTATIONS ET NOTATION FACTORIELLE

Définition et propriété
• Une permutation d’un ensemble E ayant n éléments est un arrangement des n éléments de E .
• Pour n ≥ 2 , on appelle « factorielle n » et on note n ! , le produit de tous les entiers non nuls inférieurs ou égaux à n :
n!= n(n–1)(n–2)×…×2×1
Par convention, on pose : 0 ! = 1 et 1 ! = 1
• Le nombre de permutations d’un ensemble E à n éléments est le nombre d’arrangements des n éléments de E, c'est à
dire A nn ou encore n !

Exemple :
• ( M , T , H , A ) et ( T , M , A , H ) sont des permutations de Ω.
• ( M , A , T ) et ( M , A , H , T , A ) ne sont pas des permutations de Ω .
• Le nombre d’anagrammes du mot MATH est le nombre de permutation de l’ensemble Ω, c'est à dire 4 ! = 4 × 3 × 2 × 1 = 24

- Combinaisons, binôme de Newton - 1 / 4 -

Remarque :
Ecrire une permutation de E revient à écrire dans un certain ordre tous les éléments de E . Le nombre de permutations de E est donc égal au
nombre de classements possibles des éléments de E .
Propriété

Pour tout entier naturel n non nul, et pour tout entier p tel que 1 ≤ p ≤ n , on a : p=
An n!
(n-p)!
Preuve :
Pour n et p vérifiant n ≥ 1 et 1 ≤ p ≤ n , on a :
A pn = n × ( n – 1 ) × … × ( n – p + 1 ) = n × ( n – 1 ) × … × ( n – p + 1 ) × ( n – p ) × ( n – p – 1 ) × … × 2 × 1 = n!
( n – p ) × ( n – p – 1) × … × 2 × 1 (n-p)!
3 ) COMBINAISONS
Soit E un ensemble fini ayant n éléments et p un entier vérifiant 1 ≤ p ≤ n .
Définition
On parle de sous-ensembles … on
Une combinaison de p éléments de E est une partie (ou un sous-ensemble )
utilise donc des accolades .
{ a 1 ; a 2 ; … ; a p } constituée de p éléments pris parmi les n éléments de E .

Remarques :
• Une combinaison étant une partie de E, tous ses éléments sont distincts et un élément de E intervient au plus une fois.
• Une combinaison est donc une partie non ordonnée et sans répétition de p éléments de E.
Exemple :
• { M ; T ; A } et { M ; T ; H } sont deux combinaisons de 3 éléments de Ω.
• { A }est une combinaison d’un élément de Ω .
• { M ; T ; A } et { M ; A ; T }sont deux écritures de la même combinaison.
Propriété
n
Le nombre de combinaisons de p éléments, noté   ( ou C pn ) , d’un ensemble à n éléments est :
p
p
n= An
= n!
p p! p!(n–p)!
Preuve :
n
• Si p = 0 , on a  = 1 , et p ! = 0 ! = 1 et n! =1
0 0!(n–0)!
• Si p ≠ 0 , à tout arrangement de p éléments de E correspond une seule combinaison.
Pour toute combinaison de p éléments de E, par permutation de ces p éléments, on peut former p ! arrangements de p éléments de E.
En procédant comme précédemment, deux combinaisons distinctes donnent deux ensembles disjoints de p ! arrangements.
Ainsi, le nombre d’arrangements de p éléments est p ! fois le nombre de combinaisons de p éléments.
n
Donc , A pn = p !  
p
Remarque :
• L’ensemble E possède deux sous-ensembles particuliers : ∅ et lui-même . E possède donc une combinaison à 0 élément et une
n n
combinaison à n éléments . Ainsi   = 1 et   = 1
n 0
n
• Dans l’ensemble E à n éléments, il y a n parties à un seul élément . Ainsi   = n
1
n
• Pour p ≥ 2 , on a :   = n × ( n – 1 ) × … × ( n – p + 1 )
p p×(p–1)×…×2×1
n
C'est à dire   est égal au produit des p entiers consécutifs décroissants à partir de n, divisé par p ! .
p
Exemple :
On prend simultanément 6 cartes d’un jeu de 32 cartes . On obtient une main de 6 cartes, sans répétition ni ordre . Il s’agit donc d’une
combinaison de 6 éléments pris parmi 32 éléments.
32
Le nombre de mains possibles est :   = 32 × 31 × 30 × 29 × 28 × 27 = 906192
6 6×5×4×3×2×1

- Combinaisons, binôme de Newton - 2 / 4 -

 n
4 ) PROPRIETES DES   ET TRIANGLE DE PASCAL
p
Propriétés
n
• = n 
Pour tout entier naturel n, et pour tout entier p tel que 0 ≤ p ≤ n , on a : 
p n-p
n+1 n n
• De plus, si n ≥ 1 et 1 ≤ p ≤ n – 1 , alors :  =  + 
p+1 p p+1

Preuve :

•  n = n! = n! = n
n-p (n-p)!(n-(n-p))! (n-p)!p! p
• Soit E un ensemble à n + 1 éléments et a un élément de E.
n+1
Dénombrons les parties de E à p + 1 éléments   en considérant les parties qui contiennent a et celles qui ne contiennent pas a.
p+1
Une partie de E à p + 1 éléments de E contenant a contient p éléments choisis parmi les n éléments de E autres que a.

n
Le nombre de ces parties est donc  .
p
Une partie de E à p + 1 éléments de E ne contenant pas a contient p + 1 éléments choisis parmi les n éléments de E autres que a.
n
Le nombre de ces parties est donc  .
p+1
n+1
On en déduit que :  = n+ n 
p+1 p p+1

LE TRIANGLE DE PASCAL

n
La deuxième formule permet de calculer les nombres   de proche en proche en formant le tableau suivant appelé triangle de Pascal .
p
p 0 1 2 3 4 5 6
n
0 1
•  n  n’est défini que pour p ≤ n ; on ne remplit donc pas les cases
1 1 1 p
situées au-dessus de la diagonale.
2 1 2 1
• Tous les nombres de la diagonale sont obtenus en utilisant le
n
résultat   = 1 .
3 1 3 + 3 1
= n
4 1 4 6 4 1
• Tous les nombres de la première colonne sont obtenus en utilisant
n
5 1 5 10 10 5 1 la formule   = 1 .
0
6 1 6 15 20 15 6 1
• Tous les autres nombres sont obtenus en utilisant le résultat :
n+1= n+ n 
p+1 p p+1
« tout nombre du tableau est la somme du nombre placé au-
dessus de lui et du nombre précédant ce dernier dans le tableau »

- Combinaisons, binôme de Newton - 3 / 4 -

 5 ) BINOME DE NEWTON
Soit a et b deux nombres réels ( ou complexes ) .
On a ( a + b ) ² = a ² + b ² + 2 a b et ( a + b ) 3 = a 3 + 3 a ² b + 3 a b ² + b 3
Les coefficients des termes des membres de droite sont respectivement ( 1 ; 2 ; 1 ) et ( 1 ; 3 ; 3 ; 1 ) .
On retrouve la deuxième ligne et la troisième ligne du triangle de Pascal. Ce résultat est général et se traduit par le théorème suivant.
Propriété
Soit a et b deux réels ( ou complexes ) et n un entier naturel non nul . On a :
p=n n n n n
( a + b ) n = ∑   a n–p bp = a n +   a n–1 b 1 +   an–2 b 2 + … +  ab n–1
+bn
p=0  p   1   2   n - 1 
Preuve :
p=n n
∑
On considère la proposition P(n) : ( a + b ) n =   an-p bp
p=0p
Pour n = 1 , on a :
p=1 1
 1  = 1 et  1  = 1 , donc ∑   a1-p bp =  1  a1b0 +  1  a0b1 = a + b = (a + b)1
0 1 p=0p 0 1
La proposition P(1) est donc vérifiée.
p=n n
∑
Supposons que P(n) est vraie pour un entier n fixé, n ≥ 1. On a alors ( a + b ) n =   an-p bp
p=0p
On peut écrire

(a + b)n+1 = (a + b)(a + b)n p=n n i=nn

p = n  n  an-p bp
= an+1 + ∑  p  an+1-p bp + ∑  i-1  an-i+1 bi + bn+1
= (a + b)  ∑  p=1 i=1
p = 0  p   ( en remplaçant p par i - 1 )
p=n n p=n
p=n n
  an-p bp + b
p=n n
  an-p bp = an+1 + ∑   an+1-p bp + ∑  n  an+1-p bp + bn+1
= a ∑ ∑ p=1p p = 1  p-1 
p = 0  p   p = 0  p  
p=n n p=n n ( en remplaçant i par p )
∑   an+1-p bp + ∑   an-p bp+1 p=n
=
  ∑  n  +  n  an+1-p bp + bn+1
p p=0p = an+1 +
p = 1  p   p-1 
p=0
p=n n p = n-1 n
= an+1 + ∑   an+1-p bp + ∑   an-p bp+1 + bn+1 p = n n+1
∑   an+1-p bp + bn+1
p=1p p=0 p = an+1 +
p=1 p 

p = n+1 n+1
On obtient alors (a + b)n+1 = ∑   an+1-p bp c'est-à-dire que P(n+1) est vraie.
p=0  p 
On a donc démontré que la proposition P(n) est vérifiée pour tout entier n ≥ 1.

Exemples :
• Calcul de ( a + b ) 6
En lisant les valeurs des coefficients dans la ligne numéro 6 du triangle de Pascal, on obtient :
( a + b ) 6 = a 6 + 6 a 5 b +15 a 4 b 2 + 20 a 3 b 3 + 15 a 2 b 4 + 6 a b 5 + b 6
La somme des exposants de a et b dans chaque terme est toujours égale à 6 .

n
• Lorsque a = b = 1 , on a pour tout entier n non nul : 2 n = ( 1 + 1 )n =  +n+ n+…+ n +n
0 1 2 n-1 n
C’est le nombre de parties d’un ensemble E à n éléments.
n n
En effet, pour p variant de 0 à n, il y a   parties de p éléments ; d’où la somme des  .
p p
On retrouve un résultat vu en première …

- Combinaisons, binôme de Newton - 4 / 4 -