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 , est la donnée, pour chaque élément x de E d'un élément f(x) de 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 . Un exemple trivial d'application est l'application identique de E, notée telle que . Si et sont deux applications, l'application composée de f et g est

Si A est une partie de E, on note f(A) et on nomme image de A par f la partie

de F formée des images dans F des éléments de A. De même, si B est une partie de F, on note et on nomme image réciproque de B par f la partie

de 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 l'image réciproque du singleton . 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 est

injective si et seulement si
surjective si et seulement si
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 de F, l'ensemble a un élément et un seul, que l'on note encore . On voit facilement que est alors une bijection de F dans E et que l'on a et . On dit que est la bijection réciproque de f.
Il existe une autre notation courante pour les applications. La notation 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

dit ensemble des entiers naturels muni d'une application injective 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:

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 de formée des n tels que P(n) est vrai.
On peut déduire de ce principe la

Proposition [construction par récurrence]

Si est une application et x un élément de X, il existe une application et une seule telle que g(0)=x et .

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 est définie par récurrence par les relations x₀=x et .
L'ensemble est alors muni de trois lois de composition c'est-à-dire d'applications de dans appelées addition, multiplication et exponentiation et notées respectivement , ou a b et . La construction se fait en utilisant le principe de récurrence et les relations

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⁰=1.
Si m et n sont deux entiers naturels, on dit que m est inférieur ou égal à n et on note s'il existe tel que m+p=n. On montre que c'est une relation d'ordre c'est-à-dire que l'on a

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

l'ensemble des minorants stricts de X. Comme 0 est le plus petit élément de , il ne peut appartenir à X et on a . D'autre part, si on a n<m pour tout m dans X. Cela implique mais n+1=m impliquerait que n+1 est le plus petit élément de X. On a donc n+1<m et . En application du principe de récurrence, on a , donc , ce qui termine la preuve.

Si m et n sont deux entiers naturels, on notera

En particulier, lorsque m>n, est l'ensemble vide .

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 et 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₀=E, A'₀=g(F), et . On voit par récurrence que ces parties sont ``emboîtées'':

On pose

et on définit une application par s'il existe un entier n tel que et 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é , est ce qu'ont en commun des ensembles qui sont en bijection. En d'autres termes, on dit que X et 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 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

Si X et Y sont des ensembles,

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 et 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

Si X n'est pas vide, choisissons un élément a de X. Si f existe, on définit g par

Si g existe, on définit f en choisissant pour f(x) n'importe quel élément de .

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 . S'il n'est pas fini, il est dit infini. On va voir que n est alors unique.

Théorème

Soient n et p deux entiers naturels.

[i)] Il existe une injection de dans si et seulement si .
[ii)] Il existe une surjection de sur si et seulement si ou n=p=0.
[iii)] Il existe une bijection de sur 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 . Au lieu de noter , on notera 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 , il y a toujours une injection de dans et est toujours vrai. Donc P(0) est vrai. Supposons P(n) et considérons une injection f de dans . Supposons d'abord f(n+1)=p. On a forcément p>0. Puisque f est injectif, l'image de par f est inclus dans . La restriction de f à , c'est-à-dire l'application de dans qui coïncide avec f est une injection, et l'hypothèse de récurrence implique et .
Dans le cas où a=f(n+1)<p, il existe une bijection tau

de dans lui-même qui échange a et p et laisse fixes tous les autres éléments. La composée est encore une injection de dans , et vérifie g(n+1)=p. On a donc encore 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 et 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]

Si est une application et X et Y sont des ensembles (finis) tels que , 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]

Si E est un ensemble fini et F une partie de E, alors F est fini et . Si, de plus, on a , 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 , , 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 des parties de X.

Démonstration

Soit

une application de X dans . Posons

Supposons qu'il existe tel que . On peut donc écrire

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 , 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

La relation inverse ou opposée à R est la relation telle que

La relation R est symétrique si et seulement si

c'est-à-dire . Elle est antisymétrique si et seulement si

La clôture symétrique de la relation R est la relation définie par

Elle est évidemment symétrique. La relation R est transitive si et seulement si

La clôture réflexive-transitive de la relation R est la relation définie par

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 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 est une application, la relation définie par

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 qui est une partie non vide de S. L'ensemble des classes d'équivalence, noté est une partition de S, c'est-à-dire une famille de parties non vides de S, disjointes deux à deux et dont la réunion est S. L'application 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 ou 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 est de calculer et 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 et 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'' 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]

Si A et B sont deux ensembles finis disjoints, l'ensemble est fini et l'on a

Démonstration

Par récurrence sur . Si b=0, B est vide et a bien pour cardinal . Si , il existe une bijection f de dans B. Posons c=f(b+1). La restriction de f à est une bijection de sur . On en déduit que , et, par hypothèse de récurrence, . Il y a donc une bijection g de dans . On pose et on vérifie que g devient une bijection de sur , ce qui achève la récurrence.

Théorème [Produit]

Si A et B sont des ensembles finis, leur produit cartésien est fini, et l'on a

Démonstration

Par récurrence sur . Si b=0, B est vide et aussi. On a donc bien Si , on reprend les notations de la démonstration précédente. Comme est réunion disjointe de et de . Ce dernier ensemble est en bijection avec A par l'application qui à fait correspondre le couple (a,c). Il est donc de cardinal et en appliquant le théorème précédent on a , ce qui achève la démonstration.

Corollaire [Principe des bergers]

Soit B un ensemble fini, une application et n un entier naturel non nul. On suppose que

Alors A est fini et .

Démonstration

Pour chaque b dans B, numérotons de 1 à n les éléments de . L'application qui à (i,b) fait correspondre le i-ème élément de est alors une bijection de 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]

Si A et B sont des ensembles finis, alors l'ensemble A^B des applications de B dans A est fini et l'on a

Démonstration

Par récurrence sur . Si b=0, B est vide et il existe exactement une application de B dans A: à chaque élément de est associé un élément de A et ceci ne peut être fait que d'une seule façon. On a donc bien . Si , on reprend les notations de la démonstration précédente. Ë chaque application F de B dans A, faisons correspondre le couple , où G est la restriction de F à B' et a=F(c). L'application Phi

est une bijection de A^B sur . 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

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 la fonction de X dans l'ensemble définie par

Il est clair que l'application qui à A fait correspondre est une bijection de sur , la réciproque étant l'application qui à f fait correspondre . On en déduit aussitôt la

Proposition

Si , alors .

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

Proposition

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

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 (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 et c dans A, on a

a+ b= b + a,
(a+b)+c = a+(b+c),
0+a = a,
,
a b = b a,
(a b) c = a(b c),
1.0a = 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

Comme les opérations sont commutatives, on ne se préoccupe pas de l'ordre des opérandes et on peut écrire simplement ou 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 et deux familles finies d'éléments d'un anneau commutatif A. On a

la somme étant indexée par les parties de I de .

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 de et une seule, et que le terme correspondant à I est bien .
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 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

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

c'est-à-dire que le terme correspondant à ne dépend que du cardinal qui est un entier k compris entre 0 et 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 et k, on note 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]

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

De façon générale, il est clair que est nul sauf si . On peut donc convenir que pour k<0. On a alors la

Proposition

Démonstration

Posons

L'application est une bijection de B' sur B. Les ensembles C et C' coïncident, et A est réunion disjointe de B et C. On a donc

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.

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

On peut exprimer à l'aide de factorielles le nombre A(n,k) de k-arrangements ou injections de dans :

Proposition

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 et le produit vide vaut 1. L'égalité est donc vraie pour k=0. Supposons la relation vraie pour k. Ë chaque injection f de dans on fait correspondre , sa restriction à qui est une injection de dans . L'image réciproque est formée des f qui ont même valeur que g sur . Il y en a autant que de valeurs possibles pour f(k+1), c'est-à-dire n'importe quel élément de différent des k valeurs prises par g. Il y a donc éléments dans . On déduit donc du principe des bergers que

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 l'ensemble des permutations de :

Corollaire

On peut maintenant compter le nombre de k-combinaisons, c'est-à-dire de parties de cardinal k, de :

Proposition

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 de dans , faisons correspondre son image . C'est une partie de de cardinal k. Si A est une partie de de cardinal k, il existe une bijection f de sur A. L'ensemble est formé des , où sigma

parcourt . On a donc

et le principe des bergers donne

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

pour . Il reste les cas k=0 et 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 de somme n, on définit le coefficient multinomial

comme le nombre de r-uplets de parties disjointes de telles que .

Proposition

Soit un r-uplet d'éléments d'un anneau commutatif et n un entier naturel. On a

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

et dans le cas r=2, on retrouve les coefficients du binôme

Proposition

Si k₁+k₂=n, on a

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 et B sont des parties finies d'un ensemble E, leur réunion est finie et l'on a

et de même

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

Théorème [Formule du crible]

Si est une famille de n parties d'un ensemble fini E, leur réunion a pour cardinal

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

Dans l'anneau des fonctions de E dans , posons et b_i=1, de façon que , et appliquons la formule du produit:

En effet, le terme correspondant à vaut 1. On élimine ce terme et on change de signe pour obtenir

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

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 dans . Notons l'ensemble des applications de dans . On a vu que . Pour tout , notons

l'ensemble des applications de dans . La réunion des A_i est l'ensemble des applications de dans qui ne sont pas surjectives. Il y en a donc kⁿ-S(n,k). Pour tout , on a

et ne dépend que du cardinal . La formule du crible donne donc

On a donc montré la

Proposition

Explicitons le cas k=4. On a

et on vérifie bien que S(n,4)=0 pour n<4 et S(4,4)=24=4! puisqu'une surjection de 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.