Combinatoire énumérative

Combinatoire énumérative




I Rappels de théorie des ensembles

II Outils de base

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


Une application (ou fonction) f d'un ensemble E dans un ensemble F, notée f:EF, 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 f:xf(x). Un exemple trivial d'application est l'application identique de E, notée Id E:EE telle que xE,Id E(x)=x. Si f:EF et g:FG sont deux applications, l'application composée de f et g est
gf:E G x g(f(x))

Si A est une partie de E, on note f(A) et on nomme image de A par f la partie
{yF;xA,y=f(x)}
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 f 1(B) et on nomme image réciproque de B par f la partie

{xE;f(x)B}

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 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:EF est

En résumé, f est bijective si et seulement si pour tout y de 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 ff 1=Id F et f 1f=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) iI 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érativeI Rappels de théorie des ensembles → I-2 Entiers naturels, récurrence

Nous admettrons l'existence d'un ensemble
={0,1,2,3,}
dit ensemble des entiers naturels muni d'une application injective S: 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:
A,[(0A) et (n,nAn+1A)]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 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 f:XX est une application et x un élément de X, il existe une application g:X et une seule telle que g(0)=x et n,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 est définie par récurrence par les relations x 0=x et x n+1=f(x n).
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 (a,b)a+b, (a,b)a.b ou ab et (a,b)a b. 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 0=1.
Si m et n sont deux entiers naturels, on dit que m est inférieur ou égal à n et on note mn s'il existe p 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

A={n;mX,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 0A. D'autre part, si nA on a n<m pour tout m dans X. Cela implique n+1m mais n+1=m impliquerait que n+1 est le plus petit élément de X. On a donc n+1<m et n+1A. En application du principe de récurrence, on a A=, donc X=, ce qui termine la preuve.

Si m et n sont deux entiers naturels, on notera

[m,n]={k;mkn}.

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

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

A 0A 0A 1A 1A 2A 2

On pose

A= nA n

et on définit une application ϕ:EF par ϕ(x)=g 1(x) s'il existe un entier n tel que xA nA n+1 et ϕ(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 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 XY 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,

XY et YXX=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 et Y deux ensembles. Les deux propriétés suivantes sont équivalentes

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

g(y)={l'unique élément de f 1(y) si yf(X) a sinon.

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

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 et p deux entiers naturels.

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]=, il y a toujours une injection de [1,0] dans [1,p] et 0p est toujours vrai. Donc P(0) est vrai. Supposons P(n) et considérons une injection f de [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,p1]. La restriction de f à [1,n], c'est-à-dire l'application de [1,n] dans [1,p1] qui coïncide avec f est une injection, et l'hypothèse de récurrence implique np1 et n+1p.
Dans le cas où a=f(n+1)<p, il existe une bijection tau de [1,p] dans lui-même qui échange a et p et laisse fixes tous les autres éléments. La composée g=τf est encore une injection de [1,n+1] dans [1,p], et vérifie g(n+1)=p. On a donc encore n+1p 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 f:XY est une application et X et 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]

Si E est un ensemble fini et F une partie de E, alors F est fini et FE. Si, de plus, on a E=F, alors E=F.

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 𝒫(X) des parties de X.

Démonstration
Soit phi une application de X dans 𝒫(X). Posons

A={xX;xϕ(x)}

Supposons qu'il existe aX tel que ϕ(a)=A. On peut donc écrire

aAaϕ(a)aA

ce qui est une contradiction. On a donc prouvé que A n'appartient pas à l'image de phi, et phi n'est pas surjective.

I-6 Relations binaires


Une relation binaire R sur un ensemble S est un prédicat sur S×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 sRt. La relation R est réflexive si et seulement si

sS,sRs.

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

s,tS,sR 1ttRs

La relation R est symétrique si et seulement si

s,tS,sRttRs

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

s,tS,(sRt et tRs)s=t.

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

s,tS,sR symt(sRt ou tRs).

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

s,t,uS,(sRt et tRu)sRu.

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

s,tS,sR rttk,(x i) i[0,k];s=x 0,t=x k,i[1,k]x i1Rx 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:ST est une application, la relation définie par

s,tS,sRtf(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)={tS;sRt} 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 iI de parties non vides de S, disjointes deux à deux et dont la réunion est S. L'application π:SS/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 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 A=B est de calculer A et 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 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'' 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érativeII 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 AB est fini et l'on a

AB=A+B.


Démonstration
Par récurrence sur b=B. Si b=0, B est vide et AB=A a bien pour cardinal A=A+0. Si B=b+1, il existe une bijection f de [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, AB=A+b. Il y a donc une bijection g de [1,n+p] dans AB. On pose g(A+b+1)=c et on vérifie que g devient une bijection de [1,n+p+1] sur AB, ce qui achève la récurrence.

Théorème [Produit]

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

A×B=AB.


Démonstration
Par récurrence sur b=B. Si b=0, B est vide et A×B aussi. On a donc bien A×B=0=A.0 Si B=b+1, on reprend les notations de la démonstration précédente. Comme A×B est réunion disjointe de A×B et de A×{c}. Ce dernier ensemble est en bijection avec A par l'application h:AA×{c} qui à aA 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×B=A×B+A×{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:AB une application et n un entier naturel non nul. On suppose que

bB,f 1(b)=n.

Alors A est fini et A=nB.

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

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

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 est associé un élément de A et ceci ne peut être fait que d'une seule façon. On a donc bien A =1=A 0. Si B=b+1, on reprend les notations de la démonstration précédente. Ë chaque application F de B dans A, faisons correspondre le couple Φ(F)=(G,a), où G est la restriction de F à B et a=F(c). L'application Phi est une bijection de A B sur A B×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×A=A BA=A b.A=A b+1=A B

ce qui achève la démonstration.

II-2 Fonctions caractéristiques

Combinatoire énumérativeII 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)={1 sixA 0 sinon.
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={xX;f(x)=1}. On en déduit aussitôt la

Proposition

Si 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



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= xX1 A(x).

II-3 Sommes et produits dans un anneau commutatif

Combinatoire énumérativeII 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

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

i=1 n+1a i=( i=1 na i)+a n+1

et

i=1 n+1a i=( i=1 na 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 iIa i ou iIa 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[1,n] et (b i) i[1,n] deux familles finies d'éléments d'un anneau commutatif A. On a

i=1 n(a i+b i)= I[1,n]( iIa i)( i[1,n]Ib i)

la somme étant indexée par les parties de I de [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 de [1,n] et une seule, et que le terme correspondant à I est bien ( iIa i)( i[1,n]Ib 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 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
i=1 n+1(a i+b i) = (a n+1+b n+1) i=1 n(a i+b i) = (a n+1+b n+1) I[1,n]( iIa i)( i[1,n]Ib i) = a n+1 I[1,n]( iIa i)( i[1,n]Ib i)+b n+1 I[1,n]( iIa i)( i[1,n]Ib i) = I[1,n]( iI{n+1}a i)( i[1,n]Ib i)+ I[1,n]( iIa i)( i[1,n+1]Ib i) = J[1,n+1] n+1J( iJa i)( i[1,n+1]Jb i)+ J[1,n+1] n+1J( iJa i)( i[1,n+1]Jb i) = J[1,n+1]( iJa i)( i[1,n+1]Jb i)
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{n+1} dans la première somme et J=I dans la seconde.

II-4 La formule du binôme

Combinatoire énumérativeII 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= I[1,n]a Ib nI

c'est-à-dire que le terme correspondant à I[1,n] ne dépend que du cardinal I 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 dbinomnk 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]

n,a,bA,(a+b) n= k=0 n(nk)a kb nk.


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

(0k)={1 si k=0, 0 sinon.

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

Proposition

n,k,(n+1k)=(nk)+(nk1).


Démonstration
Posons
A = {I[1,n+1];I=k}, B = {IA;n+1I}, C = {IA;n+1I}, B = {J[1,n];J=k1}, C = {J[1,n];J=k}.
L'application JJ{n+1} 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

(n+1k)=A=B+C=B+C=(nk1)+(nk),

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.

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

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érativeII 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!= i[1,n]i={1 si n=0, n.(n1)! sinon.

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

Proposition

k,n,A(n,k)=<n> k= 0i<k(ni)={n!(nk)! sikn, 0 sinon.

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 de [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 ng([1,k])=nk éléments dans ϕ 1(g). On déduit donc du principe des bergers que

A(n,k+1)=(nk)A(n,k)=(nk) 0i<k(ni)= 0i<k+1(ni)

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

n,𝔖(n)=n!.


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

Proposition

(nk)={n!k!(nk)! si0kn, 0 sinon.


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 [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 de [1,k] sur A. L'ensemble ϕ 1(A) est formé des fσ, où sigma parcourt 𝔖(k). On a donc

ϕ 1(A)=𝔖(k)=k!

et le principe des bergers donne

A(n,k)=k!(nk)

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
(n+1k) = dbinomnk+dbinomnk1 = n!k!(nk)!+n!(k1)!(nk+1)! = n!(k1)!(nk)!(1k+1nk+1) = n!(k1)!(nk)!n+1k(nk+1) = (n+1)!k!(n+1k)!
pour 1kn. Il reste les cas k=0 et k=n+1 pour lesquels les deux membres valent 1.

II-6 Les coefficients multinomiaux

Combinatoire énumérativeII 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,,k r) de somme n, on définit le coefficient multinomial

(nk 1,k 2,,k r)

comme le nombre de r-uplets (A 1,A 2,,A r) de parties disjointes de [1,n] telles que i,A i=k i.

Proposition

Soit (a 1,a 2,,a r)𝒜 r un r-uplet d'éléments d'un anneau commutatif et n un entier naturel. On a

(a 1+a 2++a r) n= k 1+k 2++a r=n(nk 1,k 2,,k r)a 1 k 1a 2 k 2a r k r.


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

(nk 1,k 2,,k r)=n!k 1!k 2!k r!

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

Proposition

Si k 1+k 2=n, on a

(nk 1,k 2)=(nk 1)=(nk 2).

II-7 La formule du crible

Combinatoire énumérativeII 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

AB=A+BAB,

et de même

ABC=A+B+CABACBC+ABC.


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

Théorème [Formule du crible]

Si (A i) i[1,n] est une famille de n parties d'un ensemble fini E, leur réunion a pour cardinal
i=1 nA i = I[1,n] I(1) I+1 iIA i = iA i i<jA iA j+ i<j<kA iA jA k +(1) n+1A 1A 2A n

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 et b i=1, de façon que a i+b i=1 EA i, et appliquons la formule du produit:
11 i=1 nA i = 1 E i=1 nA i = 1 i=1 nEA i = i=1 n(a i+b i) = I[1,n]( iI(1 A i)) = I[1,n](1) I1 iIA i = 1+ I[1,n] I(1) I1 iIA i.
En effet, le terme correspondant à I= vaut 1. On élimine ce terme et on change de signe pour obtenir

1 i=1 nA i= I[1,n] I(1) I+11 iIA i.

Il reste à calculer la somme des valeurs de ces deux fonctions
i=1 nA i = xE1 i=1 nA i(x) = xE( I[1,n] I(1) I+11 iIA i)(x) = I[1,n] I(1) I+1 xE1 iIA i(x) = I[1,n] I(1) I+1 iIA i.

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[1,k], notons

A i={fE;if([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 nS(n,k). Pour tout I[1,k], on a

A I= iIA i={fE;f([1,n])I=}=([1,k]I) [1,n]

et A I=(kI) n ne dépend que du cardinal r=I. La formule du crible donne donc

k nS(n,k)= i[1,k]A i= I[1,k] I(1) I+1A I= r=1 k(kr)(1) r+1(kr) n

On a donc montré la

Proposition

n,k,S(n,k)= r=0 k(1) r(kr)(kr) n.


Explicitons le cas k=4. On a

S(n,4)=4 n4.3 n+6.2 n4.1 n+0 n={4 n4.3 n+6.2 n4 si n>0 14+64+1=0 sin=0


n 4 n 3 n 2 n 4 n4.3 n+6.2 n4.1 n+0 n S(n,k) 0 1 1 1 14+64+1 0 1 4 3 2 412+124 0 2 16 9 4 1636+244 0 3 64 27 8 64108+484 0 4 256 81 16 256324+964 24 5 1024 243 32 1024972+1924 240

et on vérifie bien que S(n,4)=0 pour n<4 et 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

The most recent version

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

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.