Combinatoire énumérative

I Rappels de théorie des ensembles

Combinatoire énumérative → I Rappels de théorie des ensembles

Le point de vue adopté est informel. On suppose connue une partie du vocabulaire de base sur les ensembles: appartenance, inclusion, produit cartésien, ensemble des parties.

I-1 Applications

I-2 Entiers naturels, récurrence

I-3 Le cardinal d'un ensemble

I-4 Ensembles finis

I-5 Cardinaux infinis

I-6 Relations binaires

I-1 Applications

Combinatoire énumérative → I Rappels de théorie des ensembles → I-1 Applications

Une application (ou fonction)

f

d'un ensemble

E

dans un ensemble

F

, notée

f : E \to F

, est la donnée, pour chaque élément

x

E

d'un élément

f (x)

F

. L'ensemble

E

est appelé ensemble de départ et l'ensemble

F

est l'ensemble d'arrivée. L'élément

f (x)

est l'image de

x

par

f

. On écrit aussi

f : x \mapsto f (x)

. Un exemple trivial d'application est l'application identique de

E

, notée

{Id}_{E} : E \to E

telle que

\forall x \in E, {Id}_{E} (x) = x

. Si

f : E \to F

g : F \to G

sont deux applications, l'application composée de

f

g

est

\begin{matrix} g \circ f : E & \to & G \\ x & \mapsto & g (f (x)) \end{matrix}

A

est une partie de

E

, on note

f (A)

et on nomme image de

A

par

f

la partie

{y \in F; \exists x \in A, y = f (x)}

F

formée des images dans

F

des éléments de

A

. De même, si

B

est une partie de

F

, on note

f^{- 1} (B)

et on nomme image réciproque de

B

par

f

la partie

${x \in E; f (x) \in B}$

E

formée des éléments de

E

dont l'image est dans

B

. Par extension, si

y

est un élément de

F

, on note

f^{- 1} (y)

l'image réciproque du singleton

{y}

. C'est donc l'ensemble des éléments de

E

dont l'image par

f

est

y

. Cet ensemble peut être vide. On dit que l'application

f

est surjective, ou que c'est une surjection si elle n'est vide pour aucune valeur de

y

et qu'elle est injective, ou que c'est une injection s'il n'a plus d'un élément pour aucune valeur de

y

Définition

Une application

f : E \to F

est

injective si et seulement si
$\forall x, y \in E, f (x) = f (y) \Rightarrow x = y$
surjective si et seulement si
$\forall y \in F, \exists x \in E, y = f (x)$
bijective si et seulement si elle est à la fois injective et surjective.

En résumé,

f

est bijective si et seulement si pour tout

y

F

, l'ensemble

f^{- 1} ({y})

a un élément et un seul, que l'on note encore

f^{- 1} (y)

. On voit facilement que

f^{- 1}

est alors une bijection de

F

dans

E

et que l'on a

f \circ f^{- 1} = {Id}_{F}

f^{- 1} \circ f = {Id}_{E}

. On dit que

f^{- 1}

est la bijection réciproque de

f

.
Il existe une autre notation courante pour les applications. La notation

(x_{i})_{i \in I}

désigne une famille d'éléments de

X

indexée par l'ensemble

I

. Il s'agit simplement d'une application de

I

dans

X

, où

x_{i}

est l'image de

i

par l'application.

I-2 Entiers naturels, récurrence

Combinatoire énumérative → I Rappels de théorie des ensembles → I-2 Entiers naturels, récurrence

Nous admettrons l'existence d'un ensemble

ℕ = {0, 1, 2, 3, \dots}

dit ensemble des entiers naturels muni d'une application injective

S : ℕ \to ℕ

qui à un entier

n

fait correspondre son successeur noté

n + 1

qui est telle que tout entier autre que 0 a un (unique) prédécesseur et qui vérifie le principe de récurrence:

\forall A \subset ℕ, [(0 \in A) et (\forall n \in ℕ, n \in A \Rightarrow n + 1 \in A)] \Rightarrow A = ℕ .

Ce principe est en général utilisé de la façon suivante. Soit

P

un prédicat sur

ℕ

, c'est-à-dire une propriété qui, pour chaque entier naturel, peut être vraie ou fausse. Si on a établi que

P (0)

est vrai et si pour

n

quelconque, en supposant

P (n)

on a prouvé

P (n + 1)

, alors

P (n)

est vrai pour tout

n

. On applique pour cela l'énoncé ci-dessus à la partie

A

ℕ

formée des

n

tels que

P (n)

est vrai.
On peut déduire de ce principe la

Proposition [construction par récurrence]

f : X \to X

est une application et

x

un élément de

X

, il existe une application

g : ℕ \to X

et une seule telle que

g (0) = x

\forall n \in ℕ, g (n + 1) = f (g (n))

Une famille indexée par les entiers naturels s'appelle une suite. L'application

g

ci-dessus est souvent notée sous forme de suite. On pose

x_{n} = g (n)

et on dit que la suite

(x_{n})_{n \in ℕ}

est définie par récurrence par les relations

x_{0} = x

x_{n + 1} = f (x_{n})

.
L'ensemble

ℕ

est alors muni de trois lois de composition c'est-à-dire d'applications de

ℕ \times ℕ

dans

ℕ

appelées addition, multiplication et exponentiation et notées respectivement

(a, b) \mapsto a + b

(a, b) \mapsto a . b

a b

(a, b) \mapsto a^{b}

. La construction se fait en utilisant le principe de récurrence et les relations

$a + 0 = a; a + (b + 1) = (a + b) + 1$
$a .0 = 0; a . (b + 1) = a . b + a$
$a^{0} = 1; a^{b + 1} = a^{b} . a$ .

En d'autres termes, l'addition est définie par récurrence à partir de l'application

S

, la multiplication par récurrence à partir de l'addition et l'exponentiation par récurrence à partir de la multiplication. Retenons en particulier que

0^{0} = 1

.
Si

m

n

sont deux entiers naturels, on dit que

m

est inférieur ou égal à

n

et on note

m \leq n

s'il existe

p \in ℕ

tel que

m + p = n

. On montre que c'est une relation d'ordre c'est-à-dire que l'on a

$\forall m \in ℕ, m \leq m$
$\forall m, n \in ℕ, (m \leq n et n \leq m) \Rightarrow m = n$
$\forall m, n, p \in ℕ, (m \leq n et n \leq p) \Rightarrow m \leq p$

La relation d'ordre sur

ℕ

est un bon ordre, c'est-à-dire que l'on a:

Proposition

Toute partie non vide de

ℕ

a un plus petit élément.

Démonstration

Soit

X

une partie de

ℕ

dont on suppose qu'elle n'a pas de plus petit élément. On pose

$A = {n \in ℕ; \forall m \in X, n < m}$

l'ensemble des minorants stricts de

X

. Comme

0

est le plus petit élément de

ℕ

, il ne peut appartenir à

X

et on a

0 \in A

. D'autre part, si

n \in A

on a

n < m

pour tout

m

dans

X

. Cela implique

n + 1 \leq m

mais

n + 1 = m

impliquerait que

n + 1

est le plus petit élément de

X

. On a donc

n + 1 < m

n + 1 \in A

. En application du principe de récurrence, on a

A = ℕ

, donc

X = \emptyset

, ce qui termine la preuve.

m

n

sont deux entiers naturels, on notera

$[m, n] = {k \in ℕ; m \leq k \leq n} .$

En particulier, lorsque

m > n

[m, n]

est l'ensemble vide

\emptyset

I-3 Le cardinal d'un ensemble

Combinatoire énumérative → I Rappels de théorie des ensembles → I-3 Le cardinal d'un ensemble

L'existence d'une injection de

E

dans

F

peut être interprétée comme ``

E

est plus petit que

F

''. Le résultat suivant permet de donner un sens précis à cette intuition.

Théorème [de Cantor-Bernstein]

Soient

E

F

deux ensembles. S'il existe une injection de

E

dans

F

et une injection de

F

dans

E

, alors il existe une bijection de

E

dans

F

Démonstration

On définit par récurrence deux suites de parties de

E

par

A_{0} = E

A'_{0} = g (F)

A_{n + 1} = g \circ f (A_{n})

A'_{n + 1} = g \circ f (A'_{n})

. On voit par récurrence que ces parties sont ``emboîtées'':

$A_{0} \supset A'_{0} \supset A_{1} \supset A'_{1} \supset A_{2} \supset A'_{2} \supset \dots$

On pose

$A = \cap_{n \in ℕ} A_{n}$

et on définit une application

ϕ : E \to F

par

ϕ (x) = g^{- 1} (x)

s'il existe un entier

n

tel que

x \in A'_{n} ∖ A_{n + 1}

ϕ (x) = 0

sinon. Il reste à vérifier que

ϕ

est une bijection.

De même que la couleur bleue est simplement ce qu'ont en commun tous les objets bleus, le cardinal d'un ensemble

X

, noté

∣ X ∣

, est ce qu'ont en commun des ensembles qui sont en bijection. En d'autres termes, on dit que

X

Y

ont même cardinal si et seulement si il existe une bijection de

X

dans

Y

. On peut comparer les cardinaux: on dit que le cardinal de

X

est inférieur ou égal à celui de

Y

, et on note

∣ X ∣ \leq ∣ Y ∣

si et seulement si il existe une injection de

X

dans

Y

. Grâce au théorème de Cantor-Bernstein, on a la

Proposition

X

Y

sont des ensembles,

$∣ X ∣ \leq ∣ Y ∣ et ∣ Y ∣ \leq ∣ X ∣ \Rightarrow ∣ X ∣ = ∣ Y ∣ .$

L'énoncé précédent pourrait paraître évident, sauf que les cardinaux ne sont pas en général des nombres, au sens où on l'entend généralement. Par exemple, un cardinal peut être infini.
Plutôt que d'utiliser les injections pour comparer les ensembles, on aurait pu utiliser les surjections. En fait on a la

Proposition

Soient

X

Y

deux ensembles. Les deux propriétés suivantes sont équivalentes

Il existe une injection $f$ de $X$ dans $Y$ .
$X$ est vide ou il existe une surjection $g$ de $Y$ sur $X$

Démonstration

X

n'est pas vide, choisissons un élément

a

X

. Si

f

existe, on définit

g

par

$g (y) = {\begin{cases} l'unique élément de f^{- 1} (y) & si y \in f (X) \\ a & sinon. \end{cases}$

g

existe, on définit

f

en choisissant pour

f (x)

n'importe quel élément de

g^{- 1} (x)

I-4 Ensembles finis

Combinatoire énumérative → I Rappels de théorie des ensembles → I-4 Ensembles finis

Un ensemble

E

est dit fini s'il existe une bijection de

E

sur un intervalle entier

[1, n]

. S'il n'est pas fini, il est dit infini. On va voir que

n

est alors unique.

Théorème

Soient

n

p

deux entiers naturels.

[i)] Il existe une injection de $[1, n]$ dans $[1, p]$ si et seulement si $n \leq p$ .
[ii)] Il existe une surjection de $[1, n]$ sur $[1, p]$ si et seulement si $n \geq p > 0$ ou $n = p = 0$ .
[iii)] Il existe une bijection de $[1, n]$ sur $[1, p]$ si et seulement si $n = p$ .

En particulier, si

X

est un ensemble fini, il existe un entier naturel

n

et un seul tel que

X

est en bijection avec

[1, n]

. Au lieu de noter

∣ X ∣ = ∣ [1, n] ∣

, on notera

∣ X ∣ = n

et on dira que le cardinal de

X

est

n

.
Démonstration

Démontrons la propriété i) par récurrence sur

n

et indépendamment de

p

, c'est-à-dire appelons

P (n)

la propriété de

n

qui dit que cette assertion est vraie pour tout

p

. Comme

[1, 0] = \emptyset

, il y a toujours une injection de

[1, 0]

dans

[1, p]

0 \leq p

est toujours vrai. Donc

P (0)

est vrai. Supposons

P (n)

et considérons une injection

f

[1, n + 1]

dans

[1, p]

. Supposons d'abord

f (n + 1) = p

. On a forcément

p > 0

. Puisque

f

est injectif, l'image de

[1, n]

par

f

est inclus dans

[1, p - 1]

. La restriction de

f

[1, n]

, c'est-à-dire l'application de

[1, n]

dans

[1, p - 1]

qui coïncide avec

f

est une injection, et l'hypothèse de récurrence implique

n \leq p - 1

n + 1 \leq p

.
Dans le cas où

a = f (n + 1) < p

, il existe une bijection tau

[1, p]

dans lui-même qui échange

a

p

et laisse fixes tous les autres éléments. La composée

g = τ \circ f

est encore une injection de

[1, n + 1]

dans

[1, p]

, et vérifie

g (n + 1) = p

. On a donc encore

n + 1 \leq p

et P(n+1) est vrai, ce qui achève de démontrer le i). Mais le ii) est exactement équivalent à i) en échangeant

n

p

. Enfin i) et ii) donnent iii).

Le théorème précédent justifie la notation geq

employée en deux sens différents, l'un pour les entiers, l'autres pour les cardinaux. Ces deux acceptions sont compatibles. On peut reformuler le théorème précédent de plusieurs manières.

Théorème [principe des tiroirs]

f : X \to Y

est une application et

X

Y

sont des ensembles (finis) tels que

∣ X ∣ > ∣ Y ∣

, alors

f

n'est pas injective.

Si on a plus d'objets que de tiroirs, quel que soit le rangement on est obligé de ranger deux objets dans le même tiroir.

Théorème [principe d'inclusion]

E

est un ensemble fini et

F

une partie de

E

, alors

F

est fini et

∣ F ∣ \leq ∣ E ∣

. Si, de plus, on a

∣ E ∣ = ∣ F ∣

, alors

E = F

I-5 Cardinaux infinis

Combinatoire énumérative → I Rappels de théorie des ensembles → I-5 Cardinaux infinis

Proposition

Pour tout ensemble infini

E

, il existe une injection de

ℕ

dans

E

On dit que

E

est dénombrable s'il a même cardinal que

ℕ

. C'est le plus petit infini possible:
Certains ensembles classiques sont dénombrables, comme

ℤ

ℕ \times ℕ

, l'ensemble

ℚ

des nombres rationnels, ou l'ensemble des parties finies de

ℕ

.
Mais il existe des cardinaux infinis plus grands. Par exemple, l'ensemble

ℝ

des nombres réels n'est pas dénombrable.
Il est facile de montrer qu'il y a une infinité de cardinaux infinis distincts à l'aide du théorème suivant.

Théorème

Soit

X

un ensemble. Il n'y a pas d'application surjective (donc pas de bijection) de

X

dans l'ensemble

𝒫 (X)

des parties de

X

Démonstration

Soit

une application de

X

dans

𝒫 (X)

. Posons

$A = {x \in X; x \notin ϕ (x)}$

Supposons qu'il existe

a \in X

tel que

ϕ (a) = A

. On peut donc écrire

$a \in A \Leftrightarrow a \in ϕ (a) \Leftrightarrow a \notin A$

ce qui est une contradiction. On a donc prouvé que

A

n'appartient pas à l'image de phi

, et

n'est pas surjective.

I-6 Relations binaires

Combinatoire énumérative → I Rappels de théorie des ensembles → I-6 Relations binaires

Une relation binaire

R

sur un ensemble

S

est un prédicat sur

S \times S

, c'est-à-dire une propriété que possède ou ne possède pas chaque couple

(s, t)

d'éléments de

S

. S'il possède la propriété, on dit que

s

est en relation avec

t

et on note

s R t

. La relation

R

est réflexive si et seulement si

$\forall s \in S, s R s .$

La relation inverse ou opposée à

R

est la relation

R^{- 1}

telle que

$\forall s, t \in S, s R^{- 1} t \Leftrightarrow t R s$

La relation

R

est symétrique si et seulement si

$\forall s, t \in S, s R t \Leftrightarrow t R s$

c'est-à-dire

R^{- 1} = R

. Elle est antisymétrique si et seulement si

$\forall s, t \in S, (s R t et t R s) \Rightarrow s = t .$

La clôture symétrique de la relation

R

est la relation

R^{sym}

définie par

$\forall s, t \in S, {sR}^{sym} t \Leftrightarrow (s R t ou t R s) .$

Elle est évidemment symétrique. La relation

R

est transitive si et seulement si

$\forall s, t, u \in S, (s R t et t R u) \Rightarrow s R u .$

La clôture réflexive-transitive de la relation

R

est la relation

R^{rt}

définie par

$\forall s, t \in S, s R^{rt} t \Leftrightarrow \exists k \in ℕ, (x_{i})_{i \in [0, k]}; s = x_{0}, t = x_{k}, \forall i \in [1, k] x_{i - 1} R x_{i}$

c'est-à-dire que l'on peut passer de

s

t

en un nombre fini d'étapes, chaque élément étant en relation avec le suivant le long du chemin. La relation

R^{rt}

est bien sûr réflexive et transitive.
La relation

R

est une relation d'ordre si et seulement si elle est réflexive, antisymétrique et transitive. C'est une relation d'équivalence si elle est réflexive, symétrique et transitive.
Si

f : S \to T

est une application, la relation définie par

$\forall s, t \in S, s R t \Leftrightarrow f (s) = f (t)$

est une relation d'équivalence. En fait, toute relation d'équivalence est obtenue de cette manière. Si

R

est une relation d'équivalence sur

S

, on associe à chaque

s

sa classe d'équivalence

π (s) = {t \in S; s R t}

qui est une partie non vide de

S

. L'ensemble des classes d'équivalence, noté

S / R

est une partition de

S

, c'est-à-dire une famille

S_{i \in I}

de parties non vides de

S

, disjointes deux à deux et dont la réunion est

S

. L'application

π : S \to S / R

redonne

R

par le procédé décrit au début de ce paragraphe.

II Outils de base

Combinatoire énumérative → II Outils de base

On a vu qu'une des propriétés les plus fondamentales d'un ensemble fini est son cardinal, un entier naturel. L'objet général de la combinatoire énumérative est de ``calculer'' ce cardinal pour des ensembles particuliers. La plupart du temps, l'ensemble considéré dépend d'un ou plusieurs paramètres, et il s'agit d'exprimer ce cardinal comme fonction de ces paramètres. Nous serons ainsi amenés à définir certaines fonctions de

ℕ

ℕ \times ℕ

dans

ℕ

, en commençant avec les opérations de base définies plus haut.
Un autre but naturel de cet étude est de montrer que certains ensembles finis ont même cardinal. Une méthode pour prouver que

∣ A ∣ = ∣ B ∣

est de calculer

∣ A ∣

∣ B ∣

séparément, puis de comparer les résultats. C'est ce que l'on appelle une preuve par le calcul, ou calculatoire. Il est aussi souvent possible de construire explicitement une bijection entre

A

B

. On a dans ce cas une preuve combinatoire. De manière générale les mathématiciens préfèrent les preuves combinatoires pour deux raisons en fait liées: elles donnent en général une idée de ``la raison pour laquelle''

∣ A ∣ = ∣ B ∣

alors que les preuves calculatoires suggèrent rarement des idées nouvelles, et elles sont souvent plus satisfaisantes d'un point de vue esthétique.

II-1 Les opérations de base sur les cardinaux

II-2 Fonctions caractéristiques

II-3 Sommes et produits dans un anneau commutatif

II-4 La formule du binôme

II-5 Arrangements, permutations et combinaisons

II-6 Les coefficients multinomiaux

II-7 La formule du crible

II-8 Surjections

II-1 Les opérations de base sur les cardinaux

Combinatoire énumérative → II Outils de base → II-1 Les opérations de base sur les cardinaux

Théorème [Union disjointe]

A

B

sont deux ensembles finis disjoints, l'ensemble

A \cup B

est fini et l'on a

$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ .$

Démonstration

Par récurrence sur

b = ∣ B ∣

. Si

b = 0

B

est vide et

A \cup B = A

a bien pour cardinal

∣ A ∣ = ∣ A ∣ + 0

. Si

∣ B ∣ = b + 1

, il existe une bijection

f

[1, b + 1]

dans

B

. Posons

c = f (b + 1)

. La restriction de

f

[1, b]

est une bijection de

[1, b]

sur

B' = f ([1, b]) = B ∖ {c}

. On en déduit que

∣ B' ∣ = b

, et, par hypothèse de récurrence,

∣ A \cup B' ∣ = ∣ A ∣ + b

. Il y a donc une bijection

g

[1, n + p]

dans

A \cup B'

. On pose

g (∣ A ∣ + b + 1) = c

et on vérifie que

g

devient une bijection de

[1, n + p + 1]

sur

A \cup B

, ce qui achève la récurrence.

Théorème [Produit]

A

B

sont des ensembles finis, leur produit cartésien

A \times B

est fini, et l'on a

$∣ A \times B ∣ = ∣ A ∥ B ∣ .$

Démonstration

Par récurrence sur

b = ∣ B ∣

. Si

b = 0

B

est vide et

A \times B

aussi. On a donc bien

∣ A \times B ∣ = 0 = ∣ A ∣ .0

∣ B ∣ = b + 1

, on reprend les notations de la démonstration précédente. Comme

A \times B

est réunion disjointe de

A \times B'

et de

A \times {c}

. Ce dernier ensemble est en bijection avec

A

par l'application

h : A \to A \times {c}

qui à

a \in A

fait correspondre le couple

(a, c)

. Il est donc de cardinal

∣ A ∣

et en appliquant le théorème précédent on a

∣ A \times B ∣ = ∣ A \times B' ∣ + ∣ A \times {c} ∣ = ∣ A ∣ . b + ∣ A ∣ = ∣ A ∣ . (b + 1) = ∣ A ∣ . ∣ B ∣

, ce qui achève la démonstration.

Corollaire [Principe des bergers]

Soit

B

un ensemble fini,

f : A \to B

une application et

n

un entier naturel non nul. On suppose que

$\forall b \in B, ∣ f^{- 1} (b) ∣ = n .$

Alors

A

est fini et

∣ A ∣ = n ∣ B ∣

Démonstration

Pour chaque

b

dans

B

, numérotons de 1 à

n

les éléments de

f^{- 1} (b)

. L'application qui à

(i, b)

fait correspondre le

i

-ème élément de

f^{- 1} (b)

est alors une bijection de

[1, n] \times B

sur

A

Ce principe est souvent appliqué pour calculer le cardinal de

B

. À chaque élément d'un ensemble

A

de pattes, on fait correspondre le mouton du troupeau

B

auquel elle est attachée. Comme chaque mouton a (en principe) 4 pattes, on peut en déduire qu'il y a 4 fois plus de pattes que de moutons, ou 4 fois moins de moutons que de pattes. Cela peut être pratique si l'on voit les pattes mais pas les moutons.

Théorème [Ensemble puissance]

A

B

sont des ensembles finis, alors l'ensemble

A^{B}

des applications de

B

dans

A

est fini et l'on a

$∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣} .$

Démonstration

Par récurrence sur

b = ∣ B ∣

. Si

b = 0

B

est vide et il existe exactement une application de

B

dans

A

: à chaque élément de

\emptyset

est associé un élément de

A

et ceci ne peut être fait que d'une seule façon. On a donc bien

∣ A^{\emptyset} ∣ = 1 = ∣ A ∣^{0}

. Si

∣ B ∣ = b + 1

, on reprend les notations de la démonstration précédente. Ë chaque application

F

B

dans

A

, faisons correspondre le couple

Φ (F) = (G, a)

, où

G

est la restriction de

F

B'

a = F (c)

. L'application Phi

est une bijection de

A^{B}

sur

A^{B'} \times A

. En appliquant successivement le théorème précédent, l'hypothèse de récurrence et la définition de l'exponentiation, on trouve bien

$∣ A^{B} ∣ = ∣ A^{B'} \times A ∣ = ∣ A^{B'} ∥ A ∣ = ∣ A ∣^{b} . ∣ A ∣ = ∣ A ∣^{b + 1} = ∣ A ∣^{∣ B ∣}$

ce qui achève la démonstration.

II-2 Fonctions caractéristiques

Combinatoire énumérative → II Outils de base → II-2 Fonctions caractéristiques

Soit

X

un ensemble et

A

une partie de

X

. On appelle fonction caractéristique de

A

et on note

1_{A}

la fonction de

X

dans l'ensemble

{0, 1}

définie par

1_{A} (x) = {\begin{cases} 1 & si x \in A \\ 0 & sinon . \end{cases}

Il est clair que l'application qui à

A

fait correspondre

1_{A}

est une bijection de

𝒫 (X)

sur

{0, 1}^{X}

, la réciproque étant l'application qui à

f

fait correspondre

A = {x \in X; f (x) = 1}

. On en déduit aussitôt la

Proposition

∣ X ∣ = n

, alors

∣ 𝒫 (X) ∣ = 2^{n}

Les opérations d'intersection, de passage au complémentaire et de réunion se traduisent naturellement en termes de fonctions caractéristiques:

Proposition

$1_{A \cap B} = 1_{A} 1_{B}$ ,
$1_{X ∖ A} = 1 - 1_{A}$ ,
$1_{A \cup B} = 1_{A} + 1_{B} - 1_{A} 1_{B}$ .

Nous verrons plus loin une généralisation de cette dernière formule. Le cardinal d'une partie finie peut s'écrire en termes de fonctions caractéristiques:

Proposition

Pour toute partie

A

d'un ensemble (fini)

X

, on a

$∣ A ∣ = \sum_{x \in X} 1_{A} (x) .$

II-3 Sommes et produits dans un anneau commutatif

Combinatoire énumérative → II Outils de base → II-3 Sommes et produits dans un anneau commutatif

Soit

A

un anneau commutatif, c'est-à-dire un ensemble muni de deux lois de composition interne notées et

\cdot

(ou sans aucun signe) qui sont associatives et commutatives, admettant chacune un élément neutre noté respectivement 0 et 1, et dans lequel on a l'existence d'un opposé et la relation de distributivité. En d'autres termes, pour tout

a

b

c

dans

A

, on a

$a + b = b + a$ ,
$(a + b) + c = a + (b + c)$ ,
$0 + a = a$ ,
$\exists a'; a + a' = 0$ ,
$a b = b a$ ,
$(a b) c = a (b c)$ ,
$1.0 a = a$ ,
$a (b + c) = a b + a c$ .

Dans un anneau commutatif, on peut définir la somme ainsi que le produit d'une famille finie d'éléments: une somme vide vaut 0 et un produit vide vaut 1, puis, par récurrence, on définit

$\sum_{i = 1}^{n + 1} a_{i} = (\sum_{i = 1}^{n} a_{i}) + a_{n + 1}$

$\prod_{i = 1}^{n + 1} a_{i} = (\prod_{i = 1}^{n} a_{i}) a_{n + 1} .$

Comme les opérations sont commutatives, on ne se préoccupe pas de l'ordre des opérandes et on peut écrire simplement

\sum_{i \in I} a_{i}

\prod_{i \in I} a_{i}

dès lors que l'ensemble d'indices

I

est fini. On peut dans ce cadre ``développer un produit'':

Proposition [Formule du produit]

Soient

(a_{i})_{i \in [1, n]}

(b_{i})_{i \in [1, n]}

deux familles finies d'éléments d'un anneau commutatif

A

. On a

$\prod_{i = 1}^{n} (a_{i} + b_{i}) = \sum_{I \subset [1, n]} (\prod_{i \in I} a_{i}) (\prod_{i \in [1, n] ∖ I} b_{i})$

la somme étant indexée par les parties de

I

[1, n]

L'idée de cette proposition est que si l'on utilise autant de fois que possible la relation de distributivité pour développer le produit, on se retrouve avec une somme de termes. Chacun de ces termes est produit de

n

facteurs, un facteur provenant de chacune des sommes

(a_{i} + b_{i})

et valant donc soit

a_{i}

soit

b_{i}

. En notant

I

l'ensemble des indices pour lesquels on a choisi

a_{i}

plutôt que

b_{i}

, on voit que chaque terme correspond a une partie

I

[1, n]

et une seule, et que le terme correspondant à

I

est bien

(\prod_{i \in I} a_{i}) (\prod_{i \in [1, n] ∖ I} b_{i})

.
La preuve suivante est là seulement pour respecter le règlement...
Démonstration

Par récurrence sur

n

. Pour

n = 0

, il suffit de voir que

\emptyset

est l'unique partie de emptyset

. La somme de droite a donc exactement un terme, qui est un produit vide comme la partie gauche de l'équation. On est donc ramené à

1 = 1

qui est vrai.
En supposant la relation vraie pour

n

, on a

\begin{matrix} \prod_{i = 1}^{n + 1} (a_{i} + b_{i}) & = & (a_{n + 1} + b_{n + 1}) \prod_{i = 1}^{n} (a_{i} + b_{i}) \\ = & (a_{n + 1} + b_{n + 1}) \sum_{I \subset [1, n]} (\prod_{i \in I} a_{i}) (\prod_{i \in [1, n] ∖ I} b_{i}) \\ = & a_{n + 1} \sum_{I \subset [1, n]} (\prod_{i \in I} a_{i}) (\prod_{i \in [1, n] ∖ I} b_{i}) + b_{n + 1} \sum_{I \subset [1, n]} (\prod_{i \in I} a_{i}) (\prod_{i \in [1, n] ∖ I} b_{i}) \\ = & \sum_{I \subset [1, n]} (\prod_{i \in I \cup {n + 1}} a_{i}) (\prod_{i \in [1, n] ∖ I} b_{i}) + \sum_{I \subset [1, n]} (\prod_{i \in I} a_{i}) (\prod_{i \in [1, n + 1] ∖ I} b_{i}) \\ = & \sum_{\begin{array}{c} J \subset [1, n + 1] \\ n + 1 \in J \end{array}} (\prod_{i \in J} a_{i}) (\prod_{i \in [1, n + 1] ∖ J} b_{i}) + \sum_{\begin{array}{c} J \subset [1, n + 1] \\ n + 1 \notin J \end{array}} (\prod_{i \in J} a_{i}) (\prod_{i \in [1, n + 1] ∖ J} b_{i}) \\ = & \sum_{J \subset [1, n + 1]} (\prod_{i \in J} a_{i}) (\prod_{i \in [1, n + 1] ∖ J} b_{i}) \end{matrix}

ce qui constitue la relation pour

n + 1

et achève la preuve par récurrence. Le passage de la quatrième ligne à la cinquième se fait en posant

J = I \cup {n + 1}

dans la première somme et

J = I

dans la seconde.

II-4 La formule du binôme

Combinatoire énumérative → II Outils de base → II-4 La formule du binôme

Un cas particulier important de la formule du produit est celui où tous les

a_{i}

sont égaux entre eux et tous les

b_{i}

de même. la formule devient

$(a + b)^{n} = \sum_{I \subset [1, n]} a^{∣ I ∣} b^{n - ∣ I ∣}$

c'est-à-dire que le terme correspondant à

I \subset [1, n]

ne dépend que du cardinal

∣ I ∣

qui est un entier

k

compris entre

0

n

. Il est alors naturel de regrouper entre eux les termes correspondant à la même valeur de

k

. Cela amène à définir les coefficients binômiaux. Pour tout couple d'entiers naturels

n

k

, on note

dbinom nk

et on prononce ``

k

parmi

n

'' le nombre de parties à

k

éléments dans un ensemble à

n

éléments. On a donc la

Proposition [formule du binôme]

$\forall n \in ℕ, \forall a, b \in A, (a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k} .$

Il est utile de pouvoir calculer ces coefficients. Pour

n = 0

, il s'agit de compter les parties de l'ensemble vide. Il y en a une seule, et son cardinal est 0. On a donc

$(\binom{0}{k}) = {\begin{cases} 1 & si k = 0, \\ 0 & sinon. \end{cases}$

De façon générale, il est clair que

dbinom n k

est nul sauf si

0 \leq k \leq n

. On peut donc convenir que

dbinom n k = 0

pour

k < 0

. On a alors la

Proposition

$\forall n \in ℕ, \forall k \in ℤ, (\binom{n + 1}{k}) = (\binom{n}{k}) + (\binom{n}{k - 1}) .$

Démonstration

Posons

\begin{matrix} A & = & {I \subset [1, n + 1]; ∣ I ∣ = k}, \\ B & = & {I \in A; n + 1 \in I}, \\ C & = & {I \in A; n + 1 \notin I}, \\ B' & = & {J \subset [1, n]; ∣ J ∣ = k - 1}, \\ C' & = & {J \subset [1, n]; ∣ J ∣ = k} . \end{matrix}

L'application

J \mapsto J \cup {n + 1}

est une bijection de

B'

sur

B

. Les ensembles

C

C'

coïncident, et

A

est réunion disjointe de

B

C

. On a donc

$(\binom{n + 1}{k}) = ∣ A ∣ = ∣ B ∣ + ∣ C ∣ = ∣ B' ∣ + ∣ C' ∣ = (\binom{n}{k - 1}) + (\binom{n}{k}),$

et les coefficients du binôme peuvent se calculer par récurrence.

En pratique, la méthode ci-dessus est celle qui est employée pour calculer les coefficients du binôme et construire ce qu'on appelle le triangle de Pascal, c'est-à-dire une table de ces coefficients, généralement arrangée comme ci-dessous.

$\begin{matrix} k = 0 & k = 1 & k = 2 & k = 3 & k = 4 & k = 5 & k = 6 & k = 7 & k = 8 \\ n = 0 & 1 \\ n = 1 & 1 & 1 \\ n = 2 & 1 & 2 & 1 \\ n = 3 & 1 & 3 & 3 & 1 \\ n = 4 & 1 & 4 & 6 & 4 & 1 \\ n = 5 & 1 & 5 & 10 & 10 & 5 & 1 \\ n = 6 & 1 & 6 & 15 & 20 & 15 & 6 & 1 \\ n = 7 & 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 \\ n = 8 & 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 \end{matrix}$

chaque terme étant somme de celui qui est immédiatement au dessus et de celui qui est à gauche de celui-là. Les cases vides contiennent la valeur 0.

II-5 Arrangements, permutations et combinaisons

Combinatoire énumérative → II Outils de base → II-5 Arrangements, permutations et combinaisons

La factorielle d'un entier

n

est définie (par récurrence) par la formule

n! = \prod_{i \in [1, n]} i = {\begin{cases} 1 & si n = 0, \\ n . (n - 1)! & sinon. \end{cases}

On peut exprimer à l'aide de factorielles le nombre

A (n, k)

k

-arrangements ou injections de

[1, k]

dans

[1, n]

Proposition

\forall k, n \in ℕ, A (n, k) = < n >_{k} = \prod_{0 \leq i < k} (n - i) = {\begin{cases} \frac{n!}{(n - k)!} & si k \leq n, \\ 0 & sinon. \end{cases}

Démonstration

La deuxième égalité étant évidente, prouvons la première par récurrence sur

k

. Il y a une seule injection de l'ensemble vide dans

[1, n]

et le produit vide vaut 1. L'égalité est donc vraie pour

k = 0

. Supposons la relation vraie pour

k

. Ë chaque injection

f

[1, k + 1]

dans

[1, n]

on fait correspondre

g = ϕ (f)

, sa restriction à

[1, k]

qui est une injection de

[1, k]

dans

[1, n]

. L'image réciproque

ϕ^{- 1} (g)

est formée des

f

qui ont même valeur que

g

sur

[1, k]

. Il y en a autant que de valeurs possibles pour

f (k + 1)

, c'est-à-dire n'importe quel élément de

[1, n]

différent des

k

valeurs prises par

g

. Il y a donc

n - ∣ g ([1, k]) ∣ = n - k

éléments dans

ϕ^{- 1} (g)

. On déduit donc du principe des bergers que

$A (n, k + 1) = (n - k) A (n, k) = (n - k) \prod_{0 \leq i < k} (n - i) = \prod_{0 \leq i < k + 1} (n - i)$

d'où le résultat.

Le cas particulier

k = n

mérite d'être considéré à part. On appelle permutation d'un ensemble

X

une bijection de

X

dans lui-même. Pour tout entier naturel

n

, on note

𝔖 (n)

l'ensemble des permutations de

[1, n]

Corollaire

$\forall n \in ℕ, ∣ 𝔖 (n) ∣ = n! .$

On peut maintenant compter le nombre de

k

-combinaisons, c'est-à-dire de parties de cardinal

k

, de

[1, n]

Proposition

$(\binom{n}{k}) = {\begin{cases} \frac{n!}{k! (n - k)!} & si 0 \leq k \leq n, \\ 0 & sinon. \end{cases}$

Démonstration

Nous allons donner deux preuves distinctes de cette importante relation. La première est une application du principe des bergers. Ë chaque injection

f

[1, k]

dans

[1, n]

, faisons correspondre son image

ϕ (f) = A = f ([1, k])

. C'est une partie de

[1, n]

de cardinal

k

. Si

A

est une partie de

[1, n]

de cardinal

k

, il existe une bijection

f

[1, k]

sur

A

. L'ensemble

ϕ^{- 1} (A)

est formé des

f \circ σ

, où

parcourt

𝔖 (k)

. On a donc

$∣ ϕ^{- 1} (A) ∣ = ∣ 𝔖 (k) ∣ = k!$

et le principe des bergers donne

$A (n, k) = k! (\binom{n}{k})$

d'où la proposition. L'autre démonstration est par récurrence sur

n

. Le cas

n = 0

est immédiat. Un calcul simple donne

\begin{matrix} (\binom{n + 1}{k}) & = & dbinom n k + dbinom n k - 1 \\ = & \frac{n!}{k! (n - k)!} + \frac{n!}{(k - 1)! (n - k + 1)!} \\ = & \frac{n!}{(k - 1)! (n - k)!} (\frac{1}{k} + \frac{1}{n - k + 1}) \\ = & \frac{n!}{(k - 1)! (n - k)!} \cdot \frac{n + 1}{k (n - k + 1)} \\ = & \frac{(n + 1)!}{k! (n + 1 - k)!} \end{matrix}

pour

1 \leq k \leq n

. Il reste les cas

k = 0

k = n + 1

pour lesquels les deux membres valent 1.

II-6 Les coefficients multinomiaux

Combinatoire énumérative → II Outils de base → II-6 Les coefficients multinomiaux

Il est facile de généraliser la formule du binôme au cas d'un trinôme, etc. Pour chaque

r

-uplet d'entiers naturels

(k_{1}, k_{2}, \dots, k_{r})

de somme

n

, on définit le coefficient multinomial

$(\binom{n}{k_{1}, k_{2}, \dots, k_{r}})$

comme le nombre de

r

-uplets

(A_{1}, A_{2}, \dots, A_{r})

de parties disjointes de

[1, n]

telles que

\forall i, ∣ A_{i} ∣ = k_{i}

Proposition

Soit

(a_{1}, a_{2}, \dots, a_{r}) \in 𝒜^{r}

r

-uplet d'éléments d'un anneau commutatif et

n

un entier naturel. On a

$(a_{1} + a_{2} + \dots + a_{r})^{n} = \sum_{k_{1} + k_{2} + \dots + a_{r} = n} (\binom{n}{k_{1}, k_{2}, \dots, k_{r}}) a_{1}^{k_{1}} a_{2}^{k_{2}} \dots a_{r}^{k_{r}} .$

On a pour ces coefficients une formule analogue à celle des coefficients binomiaux

$(\binom{n}{k_{1}, k_{2}, \dots, k_{r}}) = \frac{n!}{k_{1}! k_{2}! \dots k_{r}!}$

et dans le cas

r = 2

, on retrouve les coefficients du binôme

Proposition

k_{1} + k_{2} = n

, on a

$(\binom{n}{k_{1}, k_{2}}) = (\binom{n}{k_{1}}) = (\binom{n}{k_{2}}) .$

II-7 La formule du crible

Combinatoire énumérative → II Outils de base → II-7 La formule du crible

Il est relativement simple de prouver que, si

A

B

sont des parties finies d'un ensemble

E

, leur réunion est finie et l'on a

$∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣,$

et de même

$∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣ .$

Dans le cas général, on a la formule du crible.

Théorème [Formule du crible]

(A_{i})_{i \in [1, n]}

est une famille de

n

parties d'un ensemble fini

E

, leur réunion a pour cardinal

\begin{matrix} ∣ \cup_{i = 1}^{n} A_{i} ∣ & = & \sum_{\begin{array}{c} I \subset [1, n] \\ I \neq \emptyset \end{array}} (- 1)^{∣ I ∣ + 1} ∣ \cap_{i \in I} A_{i} ∣ \\ = & \sum_{i} ∣ A_{i} ∣ - \sum_{i < j} ∣ A_{i} \cap A_{j} ∣ + \sum_{i < j < k} ∣ A_{i} \cap A_{j} \cap A_{k} ∣ - \dots \\ \dots + (- 1)^{n + 1} ∣ A_{1} \cap A_{2} \cap \dots \cap A_{n} ∣ \end{matrix}

Ce théorème est aussi appelé principe d'inclusion-exclusion.
Démonstration

Dans l'anneau

𝒜

des fonctions de

E

dans

ℤ

, posons

a_{i} = - 1_{A_{i}}

b_{i} = 1

, de façon que

a_{i} + b_{i} = 1_{E ∖ A_{i}}

, et appliquons la formule du produit:

\begin{matrix} 1 - 1_{\cup_{i = 1}^{n} A_{i}} & = & 1_{E ∖ \cup_{i = 1}^{n} A_{i}} \\ = & 1_{\cap_{i = 1}^{n} E ∖ A_{i}} \\ = & \prod_{i = 1}^{n} (a_{i} + b_{i}) \\ = & \sum_{I \subset [1, n]} (\prod_{i \in I} (- 1_{A_{i}})) \\ = & \sum_{I \subset [1, n]} (- 1)^{∣ I ∣} 1_{\cap_{i \in I} A_{i}} \\ = & 1 + \sum_{\begin{array}{c} I \subset [1, n] \\ I \neq \emptyset \end{array}} (- 1)^{∣ I ∣} 1_{\cap_{i \in I} A_{i}} . \end{matrix}

En effet, le terme correspondant à

I = \emptyset

vaut 1. On élimine ce terme et on change de signe pour obtenir

$1_{\cup_{i = 1}^{n} A_{i}} = \sum_{\begin{array}{c} I \subset [1, n] \\ I \neq \emptyset \end{array}} (- 1)^{∣ I ∣ + 1} 1_{\cap_{i \in I} A_{i}} .$

Il reste à calculer la somme des valeurs de ces deux fonctions

\begin{matrix} ∣ \cup_{i = 1}^{n} A_{i} ∣ & = & \sum_{x \in E} 1_{\cup_{i = 1}^{n} A_{i}} (x) \\ = & \sum_{x \in E} (\sum_{\begin{array}{c} I \subset [1, n] \\ I \neq \emptyset \end{array}} (- 1)^{∣ I ∣ + 1} 1_{\cap_{i \in I} A_{i}}) (x) \\ = & \sum_{\begin{array}{c} I \subset [1, n] \\ I \neq \emptyset \end{array}} (- 1)^{∣ I ∣ + 1} \sum_{x \in E} 1_{\cap_{i \in I} A_{i}} (x) \\ = & \sum_{\begin{array}{c} I \subset [1, n] \\ I \neq \emptyset \end{array}} (- 1)^{∣ I ∣ + 1} ∣ \cap_{i \in I} A_{i} ∣ . \end{matrix}

II-8 Surjections

Combinatoire énumérative → II Outils de base → II-8 Surjections

Grâce à la formule du crible, on peut compter le nombre

S (n, k)

de surjections de

[1, n]

dans

[1, k]

. Notons

E = [1, k]^{[1, n]}

l'ensemble des applications de

[1, n]

dans

[1, k]

. On a vu que

∣ E ∣ = k^{n}

. Pour tout

i \in [1, k]

, notons

$A_{i} = {f \in E; i \notin f ([1, n])}$

l'ensemble des applications de

[1, n]

dans

[1, k]

. La réunion des

A_{i}

est l'ensemble des applications de

[1, n]

dans

[1, k]

qui ne sont pas surjectives. Il y en a donc

k^{n} - S (n, k)

. Pour tout

I \subset [1, k]

, on a

$A_{I} = \cap_{i \in I} A_{i} = {f \in E; f ([1, n]) \cap I = \emptyset} = ([1, k] ∖ I)^{[1, n]}$

∣ A_{I} ∣ = {(k - ∣ I ∣)}^{n}

ne dépend que du cardinal

r = ∣ I ∣

. La formule du crible donne donc

$k^{n} - S (n, k) = ∣ \cup_{i \in [1, k]} A_{i} ∣ = \sum_{\begin{array}{c} I \subset [1, k] \\ I \neq \emptyset \end{array}} (- 1)^{∣ I ∣ + 1} ∣ A_{I} ∣ = \sum_{r = 1}^{k} (\binom{k}{r}) (- 1)^{r + 1} (k - r)^{n}$

On a donc montré la

Proposition

$\forall n, k \in ℕ, S (n, k) = \sum_{r = 0}^{k} (- 1)^{r} (\binom{k}{r}) (k - r)^{n} .$

Explicitons le cas

k = 4

. On a

$S (n, 4) = 4^{n} - {4.3}^{n} + {6.2}^{n} - {4.1}^{n} + 0^{n} = {\begin{cases} 4^{n} - {4.3}^{n} + {6.2}^{n} - 4 & si n > 0 \\ 1 - 4 + 6 - 4 + 1 = 0 & si n = 0 \end{cases}$

$\begin{matrix} n & 4^{n} & 3^{n} & 2^{n} & 4^{n} - {4.3}^{n} + {6.2}^{n} - {4.1}^{n} + 0^{n} & S (n, k) \\ 0 & 1 & 1 & 1 & 1 - 4 + 6 - 4 + 1 & 0 \\ 1 & 4 & 3 & 2 & 4 - 12 + 12 - 4 & 0 \\ 2 & 16 & 9 & 4 & 16 - 36 + 24 - 4 & 0 \\ 3 & 64 & 27 & 8 & 64 - 108 + 48 - 4 & 0 \\ 4 & 256 & 81 & 16 & 256 - 324 + 96 - 4 & 24 \\ 5 & 1024 & 243 & 32 & 1024 - 972 + 192 - 4 & 240 \end{matrix}$

et on vérifie bien que

S (n, 4) = 0

pour

n < 4

S (4, 4) = 24 = 4!

puisqu'une surjection de

[1, 4]

dans lui-même est automatiquement une bijection.

...
: combinatorics, interactive mathematics, interactive math, server side interactivity

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.