Terminale ∼ Spécialité mathématique
Combinatoire et dénombrement 1Factorielle d'un entier et triangle de Pascal 1.1Factorielle d'un entier Definition 1
Soit

n

un entier naturel. On appelle

factorielle

n

le nombre entier noté

n!

qui est égale

au produit

de tous les entiers de

1

jusqu'à

n

n\geq1

, ou qui vaut

1

n=0

Exemple 1

0!

=

1

5!

=

5\times

4

\times

3

\times

2

\times

1

=

120

Exercice 1 Simplifier les expressions suivantes :

$\dfrac{8!}{6!}$

$\dfrac{20!}{17!}$

$\dfrac{n!}{(n-1)!}$ , pour $n\in\mathbb{N}^*$ .

$\dfrac{(n+2)!}{n!}$ , pour $n\in\mathbb{N}$ .

Correction

$\dfrac{8!}{6!}$ $=$
$\dfrac{8\times7\times6\times5\times4\times3\times2\times1}{6\times5\times4\times3\times2\times1}$

$=$

$\dfrac{8\times7\times6!}{6!}$

$=$

$8\times7$

$=$

$56$ .

$\dfrac{20!}{17!}$ $=$
$\dfrac{20\times19\times18\times17!}{17!}$

$=$

$20\times19\times18$

$=$

$6\,840$ .

$\dfrac{n!}{(n-1)!}$ $=$
$\dfrac{n\times(n-1)!}{(n-1)!}$

$=$

$n$ .

$\dfrac{(n+2)!}{n!}$ $=$
$\dfrac{(n+2)\times(n+1)n!}{n!}$

$=$

$(n+2)(n+1)$

$=$

$n^2+3n+2$ .

Exemple 2 Les deux algorithmes ci-dessous permettent de calculer la factorielle de n'importe quel nombre entier.
Algorithme n°1

xxxxxxxxxx
 
def facto(n):
    f = 1
    if n > 1:
        for i in range(2,n+1):
            f = f*i
    return f
    
print(facto(5))
​

Exécuter

Algorithme n°2 récursif. Un algorithme

récursif

est un algorithme qui résout un problème en calculant des solutions à partir de versions plus petites du même problème. Il s'agit d'un concept fondamental en informatique.

xxxxxxxxxx
 
def facto(n):
    f = 1
    if n > 1:
        f = n*facto(n-1)
    return f
    
print(facto(5))
​

Exécuter

2 1

1.2Triangle de Pascal Exercice 2 Compléter le tableau suivant :

1	1
1	2	1
1	3	3	1
1	4	...	...	1
1	...	...	...	...	...

Correction

1	1
1	2	1
1	3	3	1
1	4	6	4	1
1	5	10	10	5	1

On complète les cases vides en additionnant le nombre de la case juste au dessus avec celui-ci de celle qui est juste à gauche de cette dernière.
Le 6 est par exemple obtenu en additionnant les deux 3 qui sont juste au-dessus.

Remark 1 Ce tableau s'appelle "le triangle de

Pascal

3 1

2Cardinal d'ensembles Definition 2
Soit

n

un entier naturel et

E

un ensemble possèdant

n

éléments.
On dit alors que

E

est un

ensemble

fini

et son nombre d'éléments est appelé

cardinal

E

. On le note

\text{card}(E)

Exercice 3 Soit

C

l'ensemble des codes à quatre chiffres et

D

l'ensemble des codes à quatre chiffres sans répétition (tous les chiffres du code sont distincts).
Déterminer

\text{card}(C)

\text{card}(D)

Correction

Lorsqu'on compose un code à quatre chiffres on a

dix

choix pour chacun des chiffres. Ainsi,

\text{card}(C)

=

10\times10\times10\times10

=

10^4

=

10\,000

Lorsque les quatre chiffres sont distincts on a

10

possibilités pour le premier chiffre, puis

9

pour le deuxième,

8

pour le troisième et

7

pour le quatrième. Ainsi :

\text{card}(D)

=

10\times9\times8\times7

=

5\,040

Remark 2

$\text{card}(\varnothing)$ $=$
$0$ .
Certains ensembles ne sont pas finis. Par exemple l'ensemble
$\mathbb{N}$
des entiers naturels, l'intervalle
$[0\,;1[$ ,
etc.

Definition 3
On dit que deux ensembles

A

B

sont

disjoints

A\cap B

=

\varnothing

Property 1
Soient

A

B

deux ensembles disjoints. On a alors :

\text{card}(A\cup B)

=

\text{card}(A)+\text{card}(B)

Exemple 3 Soit

P

l'ensemble des nombres premiers inférieurs à

30

Q

l'ensemble des multiples de

4

inférieurs à

30

. On a :

\text{card}(P\cup Q)

=

\text{card}(P)+\text{card}(Q)

=

10

+

7

=

17

Property 2
Soit

n

un entier naturel non nul, et

A_1

A_2

\dots

A_n

des ensembles finis, deux à deux

disjoints.

On a :

\operatorname{card}\left(A_{1} \cup A_{2} \cup \ldots \cup A_{n}\right)

=

\operatorname{card}\left(A_{1}\right)+\operatorname{card}\left(A_{2}\right)+\dots+\operatorname{card}\left(A_{n}\right)

Remark 3 On pourrait démontrer cette propriété par

récurrence.

4 0

Definition 4

Un
couple
de deux éléments $a$ et $b$ d'un ensemble $E$ est la donnée de ces deux éléments dans un
ordre
particulier. On le note
$(a\,;b)$ .
Un
triplet
de trois éléments $a$ , $b$ et $c$ d'un ensemble $E$ est la donnée de ces trois éléments dans un
ordre
particulier. On le note
$(a\,;b\,;c)$ .

Exemple 4 Soit

E=

⟦

0;9

⟧. L'ensemble des couples de

E

est de cardinal de

100

car par exemple le couple

(2\,;1)

est différent du couple

(1\,;2)

Definition 5
Soient

A

B

deux ensembles. Le

produit cartésien

E

F

, noté

E\times F

est l'ensemble des

couples

(e\,;f)

avec

e

f

des éléments respectifs de

E

F

Property 3
Soient

E

F

deux ensembles finis. On a :

\text{card}(E\times F)

=

\text{card}(E)\times\text{card}(F)

Exemple 5 Soit

E

un semble de couleurs possibles pour un maillot.

E=\{ \text{R}\,; \text{V}\, ; \text{B} \}

, pour rouge, vert et bleu.
Soit

F

l'ensemble des numéros possibles que peuvent porter ces maillots.

F=\{1 ; 2 ; 3 ; 4 ;5 \}

.
L'ensemble des maillots possibles (couleurs + numéros) est :

E\times F

=

\{ (\text{R}\,;1)

;

(\text{R}\,;2)

;

(\text{R}\,;3)

;

(\text{R}\,;4)

;

(\text{R}\,;5)

;

(\text{V}\,;1)

;

(\text{V}\,;2)

;

(\text{V}\,;3)

;

(\text{V}\,;4)

;

(\text{V}\,;5)

;

(\text{B}\,;1)

;

(\text{B}\,;2)

;

(\text{B}\,;3)

;

(\text{B}\,;4)

;

(\text{B}\,;5)

\}

Son cardinal est de

3\times5

=

15

Property 4
Soit

n

un entier naturel non nul, et

A_1

A_2

\dots

A_n

des ensembles finis. On a :

\operatorname{card}\left(A_{1} \times A_{2} \times \ldots \times A_{n}\right)

=

\operatorname{card}\left(A_{1}\right)\times\operatorname{card}\left(A_{2}\right)\times\dots\times\operatorname{card}\left(A_{n}\right)

Remark 4 On note

A^2

l'ensemble

A\times A

ou encore

A^3

l'ensemble

A\times A\times A

etc.

1 0

3k-uplets ∼ Parties d'un ensemble ∼ Arrangements ∼ Permutations Definition 6
Soit

A

un ensemble fini et

k

un entier naturel non nul. On appelle

k

-uplet

A

un élément de

A^k

Exemple 6 Un mot formé de

8

lettres est un

8

-uplet

de l'alphabet. Remark 5 Soit

k\in\mathbb{N}

. Si

A

est un ensemble fini de cardinal

n

, alors en appliquant la formule du cardinal d'un produit cartésien, il existe

n^k

k

-uplet de

A

.
En effet,

\text{card}(E^k)

=

\text{card}(E\times\dots\times E)

=

\text{card}(E)\times\dots\times\text{card}(E)

=

n\times\dots\times n

=

n^k

Definition 7
Une

partie

d'un ensemble

E

est un

ensemble

formé

d'éléments de

E

Remark 6 Pour

E= \{ a\,; b\,; c\}

les parties de

E

sont :

\varnothing

\{ a \}

\{ b \}

\{ c \}

\{ a\,;b \}

\{ a\,;c \}

\{ b\, ; c\}

\{ a\,; b\,; c\}

Le nombre de parties de

E

est ici de

8

Property 5
Soit

E

un ensemble fini de cardinal

n\in\mathbb{N}

. Le nombre de parties de

E

est de

2^n

Preuve
On note

e_{1}

e_{2}

\dots

e_{n}

les éléments de

E

.
On associe à chaque partie

P

de E un unique

n

-uplet de l'ensemble

\{0 ; 1\}

de la manière suivante : pour tout entier

i

entre

1

n

, on note

1

e_{i}

est

dans

P

0

sinon.

Par exemple, on associe à

\left\{e_{1}, e_{5}\right\}

n

-uplet

\{1\, ; 0\, ; 0\, ;0\, ; 1\, ; 0\, ; \ldots ; 0\}

Ainsi, le nombre de parties de

E

est égal au nombre de

n

-uplets

de l'ensemble

\{0\, ; 1\}

c'est-à-dire

2^{n}

1 3

Definition 8
Soient

A

un ensemble non vide de cardinal

n

k

un entier naturel inférieur ou égal à

n

.
Un

arrangement

k

éléments de

A

est un

k

-uplet

d'éléments

distincts

A

. Exemple 7 Si

A=\{ a\,; b\, ; c \, ; d\}

alors

(a\,;c\,;d)

( d\,; a\,; b)

sont des

arrangements

de trois éléments de

A

.
Par contre

(a\,;b\,; b)

n'est pas un arrangement

d'éléments de

A

. Property 6
Soient

A

un ensemble fini non vide à

n

elements et

k

un entier naturel tel que

k \leq n

.
Le nombre de

k

-arrangements de

A

est égal à :

\mathcal{A}_{n}^{k}

=

n \times(n-1) \times \dots \times(n-k+1)

=

\dfrac{n !}{(n-k) !}

Preuve
Pour construire un

k

-uplet de

A

, on a

n

choix pour le premier élément, puis

n-1

choix pour le deuxième, etc, jusqu'à

n-k+1

choix pour le

k

-ième

élément.
Ainsi, le nombre d'arrangement de

k

éléments de

A

est :

n\times(n-1)\times\dots\times(n-k+1)

=

\dfrac{n!}{(n-k)!}

1 1

Definition 9
Soit

A

un ensemble fini non vide de cardinal

n

.
Une

permutation

A

est un

n

-uplet

d'éléments

distincts

A

. Exemple 8 Si

A=\{1\, ; 2\, ; 3\},

les permutations de

A

sont

(1\, ; 2\, ; 3 )

(1\, ; 3\, ; 2)

(2\, ; 1\, ; 3)

(2\, ; 3\, ; 1)

(3\, ; 1\, ; 2)

(3\, ; 2\, ; 1)

Property 7
Le nombre de permutations sur un ensemble de cardinal est de

n!

Preuve
D'après la propriété précédente, une permutation étant un

arrangement

n

éléments sur un ensemble de

n

éléments, leur nombre est de :

\mathcal{A}_n^n

=

\dfrac{n!}{(n-n)!}

=

\dfrac{n!}{0!}

=

n!

0 1

4Combinaisons d'un ensemble fini Definition 10
Soit

A

un ensemble fini de cardinal

n

k

un entier naturel tel que

k\leq n

.
Une

combinaison

k

éléments de

A

est une

partie de

A

de cardinal

k

Le nombre de combinaisons de

k

éléments parmi

n

est noté

{n \choose k}

Remark 7 Dans une combinaison il n'y a pas de notion

d'ordre.

Par exemple les combinaisons de deux éléments de

E=\{a\, ; b\, ; c\}

sont :

\{a\, ; b \}

\{a\, ; c \}

\{ b\, ; c\}

On remarque donc que

{3 \choose 2}

=

3

On peut d'ailleurs voir que

{3 \choose 0}

=

1

l'ensemble vide étant la seule partie d'un ensemble ne possédant

aucun élément.

Property 8
Soient

n

k

deux entiers naturels tels que

k \leq n

. Le nombre de combinaisons de

k

éléments d'un ensemble de cardinal

n

vérifie :

\displaystyle{ {n \choose k} }

=

\dfrac{n!}{k!(n-k)!}

Preuve
Dans un ensemble de

n

éléments il y a

\dfrac{n!}{(n-k)!}

arrangements de

k

éléments (ou

k

-uplets sans

répétition

).
Or, dans un

k

-uplet l'ordre compte. Cependant il y a

k!

façons de permuter

k

éléments. Donc on peut

regrouper

les

k

-uplet par paquets de

k!

pour ne les compter qu'une seule fois pour correspondre à une combinaison (puisque pour une combinaison l'ordre

ne compte pas

).
Ainsi, le nombre de combinaison de

k

éléments parmi

n

vérifie :

\displaystyle{ n \choose k }

=

\dfrac{\mathcal{A}_n^k}{k!}

=

\dfrac{n!}{(n-k)!}\times\dfrac{1}{k!}

=

\dfrac{n!}{k!(n-k)!}

Exercice 4 Déterminer :

${2 \choose 0}$ , ${2 \choose 1}$ et ${2 \choose 2}$ .

${3 \choose 0}$ , ${3 \choose 1}$ , ${3 \choose 2}$ et ${3 \choose 3}$ .

Correction

${2 \choose 0}$ $=$
$\dfrac{2!}{0!(2-0)!}$

$=$

$\dfrac{2}{1\times2}$

$=$

$1$ .

${2 \choose 1}$ $=$
$\dfrac{2!}{1!(2-1)!}$

$=$

$2$ .

${2 \choose 2}$ $=$
$\dfrac{2!}{2!(2-2)!}$

$=$

$1$ .

${3 \choose 0}$ $=$
$\dfrac{3!}{0!3!}$

$=$

$1$ .

${3 \choose 1}$ $=$
$\dfrac{3!}{1!(3-1)!}$

$=$

$3$ .

${3 \choose 2}$ $=$
$\dfrac{3!}{2!(3-2)!}$

$=$

$1$ .

${3 \choose 3}$ $=$
$\dfrac{3!}{3!0!}$

$=$

$1$ .

Property 9
Soit

n\in\mathbb{N}

$\displaystyle{n \choose 0}$

$=$

$1$ ,
si $n\geq1$ ,
$\displaystyle{n \choose 1}$

$=$

$n$ ,

si $n\geq2$ ,
$\displaystyle{n \choose 2}$

$=$

$\dfrac{n(n-1)}{2}$ .

Preuve

$\displaystyle{n \choose 0}$

$=$

$\dfrac{n!}{0!(n-0)!}$

$=$

$1$ .

si $n\geq1$ ,
$\displaystyle{n \choose 1}$

$=$

$\dfrac{n!}{1!(n-1)!}$

$=$

$n$ .

si $n\geq2$ ,
$\displaystyle{n \choose 2}$

$=$

$\dfrac{n!}{2!(n-2)!}$

$=$

$\dfrac{n\times(n-1)\times(n-2)!}{2(n-2)!}$

$=$

$\dfrac{n(n-1)}{2}$ .

Property 10ROC
Soient

n

k

deux entiers naturels tels que

k \leq n

. On a alors :

\displaystyle{ n \choose k }

=

\displaystyle{ n \choose n-k }

Preuve

\displaystyle{ n \choose n-k }

=

\dfrac{n!}{(n-k)!(n-(n-k))!}

=

\dfrac{n!}{(n-k)!k!}

=

\displaystyle{ n \choose k }

Property 11
Soient

n

k

deux entiers naturels tels que

1\leq k \leq n-1

. On a alors :

\displaystyle{ n \choose k }

=

\displaystyle{ n-1 \choose k-1 }+\displaystyle{ n-1 \choose k }

Preuve n°1

$\displaystyle{{n-1 \choose k-1}+{n-1 \choose k}}$	$=$	$\dfrac{(n-1)!}{(k-1)!(n-1-(k-1))!}+\dfrac{(n-1)!}{k!(n-1-k)!}$
	$=$	$\dfrac{(n-1)!}{(k-1)!(n-k)!}+\dfrac{(n-1)!}{k!(n-1-k)!}$ .

On remarque alors que :

$k!=(k-1)!\times k$ ,
$(n-k)!=(n-k)\times(n-1-k)!$ .

Le dénominateur commun dans

\dfrac{(n-1)!}{(k-1)!(n-k)!}+\dfrac{(n-1)!}{k!(n-1-k)!}

est donc

k!(n-k)!

Il faut donc :

multiplier le numérateur et le dénominateur de $\dfrac{(n-1)!}{(k-1)!(n-k)!}$ par
$k$ ,
multiplier le numérateur et le dénominateur de $\dfrac{(n-1)!}{k!(n-1-k)!}$ par
$(n-k)$ .

On a alors :

$\displaystyle{{n-1 \choose k-1}+{n-1 \choose k}}$	$=$	$\dfrac{(n-1)!}{(k-1)!(n-k)!}+\dfrac{(n-1)!}{k!(n-1-k)!}$
	$=$	$\dfrac{k(n-1)!}{k(k-1)!(n-k)!}+\dfrac{(n-k)(n-1)!}{k!(n-1-k)!(n-k)}$
	$=$	$\dfrac{k(n-1)!}{k!(n-k)!}+\dfrac{(n-k)(n-1)!}{k!(n-k)!}$
	$=$	$\dfrac{k(n-1)!+(n-k)(n-1)!}{k!(n-k)!}$
	$=$	$\dfrac{k(n-1)!+n(n-1)!-k(n-1)!}{k!(n-k)!}$
	$=$	$\dfrac{n(n-1)!}{k!(n-k)!}$
	$=$	$\dfrac{n!}{k!(n-k)!}$
	$=$	$\displaystyle{n \choose k}$ .

1 2

Preuve n°2
Soit

E

un ensemble de cardinal

n

et soit

a

un élément de

E

On définit les ensembles suivants :

$A$ l’ensemble
des parties de $E$ à $k$ éléments,
$B$ l'ensemble
des parties à $k$ éléments de $E$ contenant $a$ ,
$C$ l’ensemble
des parties à $k$ éléments de $E$ ne contenant pas $a$ .

Le cardinal de

A

est

n \choose k

L'ensemble

B

contenant

a

pour le construire il faut donc choisir

k-1

éléments (puisqu'on

a

est

déjà choisi

) parmi les

n-1

restants (tous les éléments de

E

sauf

a

). Le cardinal de

B

est donc

{n-1 \choose k-1}

De même, pour construire

C

il nous faut choisir

k

éléments parmi

n-1

(tous les éléments de

E

sauf

a

). Son cardinal est donc

n-1 \choose k

Remarquons que

B

C

sont disjoints (c'est-à-dire

B\cap C=\varnothing

).
Par ailleurs une partie à

k

éléments de

E

contient

a

ne le contient pas.

Ainsi :

A=B\cup C

et :

$\text{card}(A)$	$=$	$\text{card}(B)+\text{card}(C)$
$\displaystyle{{n \choose k}}$	$=$	$\displaystyle{{n-1 \choose k-1}+{n-1 \choose k}}$ .

0 2

Remark 8 Cette formule justifie la construction du triangle de Pascal. Property 12ROC
Pour tout entier

n

\displaystyle{\sum_{k=0}^n{n \choose k}}

=

2^n.

Preuve.
Soit

E

un ensemble de cardinal

n

.
Pour tout entier

k

inférieur à

n

, le nombre

\displaystyle{{n \choose k}}

correspond au nombre de

parties de

E

possédant

k

éléments.

Ainsi, la somme

\displaystyle{\sum_{k=0}^n{n \choose k}}

correspond

au nombre de parties de

E

possédant aucun élément

plus

le nombre de parties de

E

possédant un élément,

plus le nombre de parties à deux éléments,

etc. jusqu'au nombre de parties à

n

éléments.

Cette somme vaut donc

le nombre total de parties de

E

soit

2^n

Illustration dans le cas où

n=3

.
On note

E=\{ e_1 ; e_2 ; e_3 \}

un ensemble à trois éléments.
Pour déterminer l'ensemble des parties de

E

on peut parcourir l'arbre ci-dessous, la notation

\overline{e_1}

voulant dire que l'on ne choisit pas l'élément

e_1

Il y a

2^3=8

chemins possibles dans cet arbre qui sont respectivement :

\{ e_1 ; e_2 ; e_3 \}

\{ e_1 ; e_2 ; \overline{e_3} \}

=

\{ e_1;e_2 \}

\{ e_1 ; \overline{e_2} ; e_3 \}

=

\{ e_1;e_3 \}

\{ e_1 ; \overline{e_2} ; \overline{e_3} \}

=

\{ e_1 \}

\{ \overline{e_1} ; e_2 ; e_3 \}

=

\{ e_2;e_3 \}

\{ \overline{e_1} ; e_2 ; \overline{e_3} \}

=

\{ e_2 \}

\{ \overline{e_1} ; \overline{e_2} ; e_3 \}

=

\{e_3 \}

\{ \overline{e_1} ; \overline{e_2} ; \overline{e_3} \}

=

\varnothing

Il y a

{3 \choose 0} =1

partie à

0

élément qui est :

\varnothing

Il y a

{3 \choose 1} =3

parties à

1

élément qui sont :

\{ e_1 \}

\{ e_2 \}

\{ e_3 \}

Il y a

{3 \choose 2} =3

parties à

2

éléments qui sont :

\{ e_1;e_2 \}

\{ e_1;e_3 \}

\{ e_2;e_3 \}

Il y a

{3 \choose 3} =1

parties à

3

éléments qui est :

\{ e_1 ; e_2 ; e_3 \}

Dans cette illustration nous avons bien :

{3 \choose 0}+{3 \choose 1}+{3 \choose 2}+{3 \choose 3}

=

2^3

Dans la démonstration on a généralisé cet exemple à un arbre contenant

2^n

chemins possibles en rassemblant les chemins par

nombres d'éléments.

2 2