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

n

un entier naturel. On appelle factorielle de

n

, le nombre entier noté

n!

qui est égale au produit de tous les entiers de

1

jusqu'à

n

, si

n\geq1

, ou qui vaut

1

n=0

0!

=

1

5!

=

5\times

4

\times

3

\times

2

\times

1

=

120

. 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}$ .

$\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$ .

Les deux algorithmes ci-dessous permettent de calculer la factorielle de n'importe quel nombre entier.
Algorithme n°1
def facto(n): f = 1 if n > 1: for i in range(2,n+1): f = f*i return f print(facto(5))
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.
def facto(n): f = 1 if n > 1: f = n*facto(n-1) return f print(facto(5))

Triangle de Pascal Compléter le tableau suivant :

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

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. Ce tableau s'appelle "le triangle de Pascal".

Cardinal d'ensembles
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 de

E

. On le note

\text{card}(E)

. 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)

. 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

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

On dit que deux ensembles

A

B

sont disjoints si

A\cap B

=

\varnothing

.
Soient

A

B

deux ensembles disjoints. On a alors :

\text{card}(A\cup B)

=

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

. 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

.
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)

. On pourrait démontrer cette propriété par récurrence.

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)$ .

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)

.
Soient

A

B

deux ensembles. Le produit cartésien de

E

F

, noté

E\times F

, est l'ensemble des couples

(e\,;f)

avec

e

f

des éléments respectifs de

E

F

.
Soient

E

F

deux ensembles finis. On a :

\text{card}(E\times F)

=

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

. 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

.
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)

. On note

A^2

l'ensemble

A\times A

, ou encore

A^3

l'ensemble

A\times A\times A

etc.

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

A

un ensemble fini et

k

un entier naturel non nul. On appelle

k

-uplet de

A

un élément de

A^k

. Un mot formé de

8

lettres est un

8

-uplet de l'alphabet. 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

.
Une partie d'un ensemble

E

est un ensemble formé d'éléments de

E

. 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

.
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}

Soient

A

un ensemble non vide de cardinal

n

k

un entier naturel inférieur ou égal à

n

.
Un arrangement de

k

éléments de

A

est un

k

-uplet d'éléments distincts de

A

. 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

.
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)!}

Soit

A

un ensemble fini non vide de cardinal

n

.
Une permutation de

A

est un

n

-uplet d'éléments distincts de

A

. 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)

.
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 de

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!

Combinaisons d'un ensemble fini
Soit

A

un ensemble fini de cardinal

n

k

un entier naturel tel que

k\leq n

.
Une combinaison de

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}

. 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.
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)!}

. 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}$ .

${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$ .

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}$ .

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 }

.
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}$ .

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

ou 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}}$ .

Cette formule justifie la construction du triangle de Pascal.
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.