Next PDF List

1p14x2x=1Xn=01n+ 12nnxn= 1 +x+ 2x2+ 5x3+ 14x4+ 42x5+:::Introduction a la combinatoireNotes de coursProfesseur : Francois BergeronHiver 2010Université du Québec à MontréalDépartement de mathématiquesCase postale 8888, Succursale Centre-VilleMontréal (Québec) H3C 3P82Table des matieres1 Ensembles et fonctions51.

1) Introduction51. 2) Ensembles51. 3) Fonctions121. 4) Compter les elements d'un ensemble221. 5) Multi-sous-ensembles et mon^omes311. 6) Suite et series generatrices341. 7) Exercices382 Relations et graphes452. 1) Introduction452. 2) Relations sur un ensemble452. 3) Relation d'equivalence512. 4) Bijections naturelles(). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .592. 5) Ordres602. 6) Chemins dans un graphe oriente682. 7) Arbres742. 8) Endofonctions772. 9) Exercices783 Mots, langages, automates et chemins833. 1) Introduction.833. 2) Mots843. 3) Langages863. 4) Automates903. 5) Chemins dans le reseauNN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .923. 6) Aire de chemin943. 7) Chemins de Dyck973. 8) Chemins de Dyck avec poids102iiiTABLE DES MATIERES3. 9) Exercices1024 Diverses structures combinatoires1054. 1) Introduction.1054. 2) Arbres binaires1054. 3) Arbres binaires croissants1074. 4) Arbres plans1094. 5) Triangulations d'un polygone1094. 6) Congurations de Catalan1104. 7) Fonction de stationnement1144. 8) Polyominos1184. 9) Exercices1215 Permutations et partitions1235. 1) Introduction.1235. 2) Permutations1235. 3) Partages1365. 4) Diagrammes de Ferrers1375. 5) Enumeration de partages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395. 6) Theoreme pentagonal d'Euler1425. 7) Tableaux de Young1465. 8) Formule des equerres1475. 9) Correspondance RSK1485.10 Exercices1516 Introduction a la theorie des especes1576. 1) Introduction.1576. 2) Especes de structures.1576. 3) Exemples d'especes1596. 4) Especes auxiliaires simples.1656. 5) Isomorphisme d'especes (bijections naturelles).1676. 6) Somme et produit.1686. 7) Dessins de structures generiques.1706. 8) Passage aux series.1726.

9) Exemples de calcul de series.1736.10 Substitution.1756.11 Exemples de substitutions.1766.12 L'espece des arborescences.1786.13 Derivee et pointage.1786.14 Vertebres.180TABLE DES MATIERESiii6.15 Isomorphisme de structures et types de structures.1826.16Enumeration de structures non etiquetees. . . . . . . . . . . . . . . . . . . . . . . . 1826.17 Especes a plusieurs sortes1856.18 Exercices187Appendices190A Calcul formel191A.

1) Introduction191A. 2) Theorie des ensembles et calcul formel192A. 3) Le package GFUN196A.

4) Analogues polynomiaux198B Series generatrices pour des nombres bien connus203C Notations207ivTABLE DES MATIERESIntroductionRepondre a des questions du genreQuelles sont les facons de ?Quelles sont les diverses possibilites de ?De combien de facons peut-on ?est parfois assez dicile.

Une premiere etape, essentielle a la resolution du probleme, consiste aclarier la signication des .

Mathematiser le probleme souleve demande alors de decrireprecisement un certain ensemble ni, dont les elements sont les diverses possibilites dont il estquestion dans cette partie de la question.

On cherchera alors comment enumerer (lister, classier)les elements de cet ensemble, ou plus simplement comment lescompter1.

Tres souvent, cesdeux objectifs ne vont pas l'un sans l'autre.

En eet, on ne peut ^etre certain d'avoir bien comptetoutes les possibilites, que si l'on est certain de bien savoir quelles sont ces possibilites.La situation est tres souvent la suivante.

Pour chaque entier positifn, on considere un ensembleAndecongurations, oustructures d'une certaine espece.

Ici, l'entiernmesure latailledesstructures considerees, qui est souvent le nombred'atomesa partir desquels ces structures sontconstruites.

Le probleme typique consiste alors a trouver uneformulepour le nombre d'elementsdeAn, en fonction de la taillen.

On dit alors qu'on a enumere les elements des ensemblesAn.Une des principales strategies employees pour s'attaquer a ce probleme d'enumeration consiste adecomposer les structures etudiees en amalgames de structures plus simples.

On espere ainsi seramener a compter le nombre d'elements d'ensembles plus simples.Bien entendu, l'inter^et d'un probleme donne depend de l'importance d'enumerer les objets conside-res, soit dans un contexte mathematique, soit pour les besoins d'une autre science comme la phy-sique, la biologie ou l'informatique.

Historiquement, la combinatoire est percue par plusieurs commeliee au calcul de probabilites via une formule du genre :probabilite de gagner =nombre de congurations gagnantesnombre total de congurations:1.

Les guillemets sont utilises dans ce texte pour souligner que l'on utilise informellement un terme qui auraitavantage a ^etre deni precisement.

Une partie de notre travail consistera a degager clairement de bonnes denitionspour ces termes, ou d'autres mieux adaptes aux problemes consideres.12TABLE DES MATIERESPar exemple, on calcule que 1=6 est la probabilite d'obtenir un total de 7 en lancant deux des,puisque c'est16jDjouDest l'ensemble des 36 resultats possible :D={}Cependant, il y a une multitude d'autres situations interessantes (dans de nombreuses spheresd'activite) qui soulevent des problemes d'enumeration importants.

Ainsi, pour comparer la perfor-mance de certains algorithmes informatiques, il est necessaire de compter le nombre de structuresintervenant dans les programmes qui mettent en oeuvre ces algorithmes.

D'autre part, en phy-sique statistique on ramene l'etude des changements de phase (par exemple de liquide a solide)a l'enumeration de congurations d'un certain genre.

De plus, en biologie, un grand nombre deconcepts de la combinatoire jouent un r^ole crucial dans l'etude de la structure de genomes, Enn,pour ne citer rapidement que quelques exemples de nature mathematiques, des problemes pro-fonds de la theorie de la representation des groupes, de la theorie des nombres, ou de la geometriealgebrique, soulevent des problemes d'enumeration diciles dont certains n'ont pas encore de so-lution satisfaisante.De facon complementaire a l'etude de la decomposition de structures complexes en structures plussimples (entre autres pour en faciliter l'enumeration), il est tout a fait naturel de chercher a mieuxcomprendre les mecanismes qui permettent de combiner des structures simples pour en former desplus complexes.

On est tente ici de faire le parallele avec l'etude de la construction de molecules apartir d'atomes, ou d'organismes a partir de cellules.

Mais un parallele encore plus profond peut^etre fait avec une des composantes essentielles de la programmation en informatique, a savoir laconstruction de structures de donnees complexes a partir des structures de donnees de base (dansle langage de programmation utilise).Tout comme pour les langages de programmation, les plus simples des mecanismes de combinaisonde la combinatoire font appel aux constructions de base de la theorie des ensembles : sous-ensembles,union, intersection, produit cartesien, etc.

Voila pourquoi nous allons commencer par etudier cer-TABLE DES MATIERES3tains aspects de la theorie (nave2) des ensembles, tout en soulignant comment lier les constructionsconsiderees a l'enumeration.

Nous allons ensuite repertorier les structures combinatoires les pluscourantes, celles qui jouent un r^ole plus important parce qu'elles interviennent plus frequemmentdans toutes sortes de situations.

Notre but est de degager une vue d'ensemble qui (a la n du cours)culminera avec une petite introduction a la theorie deespeces de structures, qui permet d'avoirun point de vue global pour la construction de structures complexes a partir des elements d'unensemble consideres comme atomes de base.L'approche de ce texte consiste a d'abord developper une description systematique des structurescombinatoires dans le contexte de la theorie des ensembles.

Les constructions sont decrites defacon a ^etre facilement programmables dans un systeme de calcul formel tel que Sage, Maple ouMathematica, est des exercices a cet eet sont prevus.

Les sections ou les exercices plus dicilessont marques d'une etoile.2.

Dans notre contexte les ensembles sont essentiellement des ensembles nis, et il n'y a pas de problemes aproceder ainsi.

4) TABLE DES MATIERESChapitre 1Ensembles et fonctions1.

1) IntroductionOn developpe dans ce chapitre les constructions de base de la theorie des ensembles, en particuliercelles qui concernent les fonctions, en m^eme temps que certains outils de base pour l'enumerationdes elements des ensembles consideres.1.

2) EnsemblesTout au cours de ce texte, on vise a construire explicitementdesstructures combinatoiresa partir des elements d'en-sembles nis donnes, comme l'ensemble[n] :=fi2Nj1ing;ou l'ensemble des lettres de l'alphabetA:=fa;b;c;d; ::: ;zg;ou encore les ensemblesf;;g;ouf|;};~;g:Informellement, on peut penser que les elements de cesen-sembles de basesont des atomes avec lesquels on entendconstruire les structures considerees.Georg Cantor(1845{1918)56CHAPITRE 1.

ENSEMBLES ET FONCTIONSLa theorie des ensembles a ete introduite par Georg Cantor.

Bien qu'il soit necessaire d'en donnerune axiomatique rigoureuse pour eviter les paradoxes, nous n'aurons pas trop besoin d'insisterla-dessus, etant donne que les ensembles consideres sont soit nis, soit des ensembles classiquescommeN=f0;1;2;3;:::g,Z=f:::;2;1;0;1;2;:::g, l'ensembleQdes nombres rationnels, oul'ensembleRdes nombres reels.

Rappelons que deux ensembles sont egaux si et seulement si ils ontles m^emes elements.

Ainsi, on a les presentations equivalentesfa;b;cg=fc;a;bg=fa;b;a;b;c;a;b;ag;d'un m^eme ensemble qui contient trois elements :a,betc.

Pour des ensembles decrits sous la formeA=fx2SjP(x)g;etB=fx2SjQ(x)g;(1.1)avecP(x) etQ(x) des proprietes formulees en terme d'enonces logiques, on a l'egaliteA=Bsiet seulement siP(x) etQ(x) sont logiquement equivalent.

On denote;, l'ensemble vide, qui necontient aucun element.Le nombre d'elements (distincts) d'un ensembleA(oucardinal), est denotejAj.Operations de base sur les ensembles.Une premiere operation de base sur les ensemblesest celle d'intersection,A\B, de deux ensemblesAetB.

C'est l'ensemble des elements qui sontcommuns a ces deux ensembles.

Plus precisement on aA\B:=fxjx2A;etx2Bg:(1.2)Par exemple, on afa;b;c;dg \ f1;b;3;dg=fb;dg:D'autre part, l'uniondeAetBest l'ensembleA[B:=fxjx2A;oux2Bg:(1.3)Par exemplefa;b;c;dg [ f1;b;3;dg=fa;b;c;d;1;3g:On verie facilement que les egalites suivantes sont valables en general, quel que soient les ensemblesA,B, etC:(i)A\ ;=;;(i)0A[ ;=A;(ii)A\B=B\A;(ii)0A[B=B[A;(iii)A\(B\C) = (A\B)\C;(iii)0A[(B[C) = (A[B)[C;(iv)A\(B[C) = (A\B)[(A\C);(iv)0A[(B\C) = (A[B)\(A[C):(1.4)1.2.

ENSEMBLES7LorsqueA\B=;, on dit queA[Best uneunion disjointe, et on ecrit alorsA+Bpour designercette union.

Voir l'exercice1.2p ource qui concerne les propri etesde l'union d isjointe1.Ladierence,AnB, de deux ensemblesAetB, est l'ensemble des elements deAqui ne sont pasdansB, c.-a-d. :AnB:=fx2Ajx62Bg:(1.5)Sous-ensembles.Si tous les elements deBsont aussi des elements deA, on dit queBestunsous-ensembledeA, et on ecritBA.

On dit aussi parfois queBest unepartiedeA.

Sedonner un sous-ensembleB, dekelements d'un ensembleAde cardinaln, correspond donc achoisirkelements parmin.L'inclusion d'ensembles possede les proprietes suivantes.

Pour toutA,BetC, on aa); A;b)AA;c) siABetBA;alorsA=B;d) siABetBC;alorsAC:(1.6)LorsqueAetBsont decrit comme en (1.1), on aBAsi et seulement si l'enonce logiqueQ(x) =)P(x) est vrai.

D'autre part, quel que soient les ensemblesAetB, on a toujoursA\BA;etAA[B:(1.7)De plus, SiBest un sous-ensemble deA, alors on aA\B=BetA[B=A:(1.8)On denoteP[S] l'ensemble de tous les sous-ensembles deS:P[S] :=fAjASg:(1.9)On dit aussi queP[S] est l'ensemble des partiesdeS.

Par exemple,P[fa;b;cg] =f;;fag;fbg;fcg;fa;bg;fa;cg;fb;cg;fa;b;cgg:1.

LorsqueAetBne sont pas disjoints (A\B6=;), on peut tout de m^eme considerer leur union disjointe enforcantAetBa ^etre disjoints.

Plus precisement, on poseA+B= (f0g A)[(f1g B):On donne ainsi descouleursdistinctes aux elements deAet deB.

8) CHAPITRE 1.

ENSEMBLES ET FONCTIONSPour un ensembleSxe, lecomplementdeAdansS, denoteA, est l'ensembleA:=fx2Sjx62Ag;des elements deSqui ne sont pas elements deA(on ecritx62A).

Ainsi, pourS=fa;b;c;d;e;fgetA=fb;c;eg, on aA=fa;d;fg.

SiA=fx2SjP(x)g, alors on aA=fx2Sj :P(x)g.Quel que soientAetBdes sous-ensembles deS(donc des elements deP[S]), les identites suivantessont valables(i)A=A;(ii)A\A=;;(ii)0A[A=S;(iii)A\B=A[B;(iii)0A[B=A\B:(1.10)Supposons que pour chaque elementid'un ensembleI, on choisisse un sous-ensembleAideS.

Ondit alors qu'on a unefamilled'ensembles indexee par les elements deI, et on denotefAigi2Icettefamille d'ensembles (c'est simplement un ensemble d'ensembles).

On a souvent la situationI= [n],et alors la famille est l'ensemblefA1;A2;A3;:::;Ang:Gr^ace aux associativites (1.4, (iii) et (iii)'), on peut etendre sans probleme les notions d'union etd'intersection a de telles familles, en posant\i2IAi:=fxjpour touti2I; x2Aig;et(1.11)i2IAi:=fxjil existei2I; x2Aig:(1.12)Ainsi, pourI= [n], on ecrit aussii2[n]Ai=n\i=1Ai;et[i2[n]Ai=n[i=1Ai;et pourn= 3 on a3i=1Ai=A1\A2\A3;et3[i=1Ai=A1[A2[A3:On a les identitesk2I[JAk= \i2IAi!\0j2JAj1A;et(1.13)k2I[JAk= [i2IAi![0j2JAj1A:(1.14)1.2.

ENSEMBLES9On doit cependant prendre la precaution d'avoir pose par convention2quei2;Ai:=S;et[i2;Ai:=;:De facon tout a fait similaire, on etend la notion d'union disjointe aux familles d'ensembles deux adeux disjoints.

On utilise alors le symbole deP, et on ecrit doncXi2IAi:=[i2IAi;(1.15)pour l'union en question.

En particulier, on a les deux ecritures equivalentesnXi=1Ai=A1+A2+:::+An;tout comme d'habitude.Pour chaque 0k, on considere aussi l'ensemble desparties ak-elementsdeS:Pk[S] :=fAjAS;jAj=kg:C'est doncl'ensemble des possibilites de choix dekelements parmin.Ainsi, on aP0[S] =f;g, puisP1[S] =ffxg jx2Sg;et encoreP2[S] =ffx;yg jx;y2S;etx6=yg;et ainsi de suite jusqu'aPn[S] =fSg, pournegal au cardinal deS.

Ainsi, siS=fa;b;cg, alors onaP0[S] =f;g;P1[S] =ffag;fbg;fcgg;P2[S] =ffa;bg;fa;cg;fb;cgg;P3[S] =ffa;b;cgg:Ces ensembles contiennent donc respectivement 1, 3, 3, et 1 elements, et leur union disjointe donnel'ensemble a 8 elementsP[S] vus plus haut.

En fait,P[S] est toujours l'union disjointe des ensemblesPk[S], c.-a-d. :P[S] =1Xk=0Pk[S]:(1.16)2.

On voit ici la necessite d'avoir choisit lesAicomme etant tous sous-ensemble d'un m^emeuniversS.10CHAPITRE 1.

ENSEMBLES ET FONCTIONSCommePk[S] =;, sikest plus grand que le cardinal deS, cette sommation est en fait nie.

Ona donc ici deux descriptions du m^eme ensemble, et nous allons voir plus loin qu'il en resulte uneidentite interessante (voir (1.72On peutcalculerrecursivement (voir les exercices1.10 et 1.20 ) l'ensemble des parties akelements d'un ensemble via la formulePk[S+fyg] =Pk[S] +nB+fyg jB2P k1[S]o;(1.17)ouyn'est pas element deS.

On a evidemment les conditions initiales :Pk[S] =(;si; k >jSj;fSgsi; k=jSj:(1.18)Pour illustrer comment l'identite (1.18) permet de calculer eectivement, considerons le casP2[fa;b;cg].On debute avecS=fa;bgety=c, et le calcul se deroule comme suitP2[fa;b;cg] =P2[fa;bg] +nB+fcg jB2P 1[fa;bg]o=ffa;bgg+nB+fcg jB2 ffag;fbgg]o=ffa;bgg+ffa;cg;fb;cgg=ffa;bg;ffa;cg;fb;cgg]gPour des ensembles disjointsA(de cardinaln) etB(de cardinalk), on a aussi la bijectionPk[A+B]!kXi=0Pi[A]P ki[B];(1.19)qui envoie une partieCdeA+Bsur le couple (C\A;C\B), pour lequel on a clairementC= (C\A) + (C\B).

On en deduit l'identite de l'exercice1.10 , c)Produit cartesien.Avant de decrire la prochaine construction, rappelons que deux couples(a;b) et (c;d) sont egaux, si et seulement si on a les deux egalitesa=cetb=d.

LeproduitcartesiendeAetBest l'ensemble de tous les couples (x;y), avecxelement deAetyelement deB. Autrement formule, on aAB=f(x;y)jx2Aety2Bg:1.2.

ENSEMBLES11Si l'un des ensemblesAouBest vide, alors le produit cartesienABest vide, c.-a-d. :A ;=; B=;:(1.20)Une illustration du produit cartesien estfa;b;c;dg f1;2;3g=f(a;1);(b;1);(c;1);(d;1);(a;2);(b;2);(c;2);(d;2);(a;3);(b;3);(c;3);(d;3)g:Il est facile de verier que, pour tout ensembleA,BetC(avecBetCdisjoints), on aA(B+C)= ( AB) + (AC);(1.21)(A+B)C=( AC) + (BC);(1.22)Pour un ensemble ni d'indicesI, denotons par (ai)i2Iles suites indexees par les elements deI.Rappelons que l'on a l'egalite(ai)i2I= (bi)i2I;si et seulementai=bipour toutidansI.

Si (Ai)i2Iest une suite d'ensembles indexes parI. Ondit deaique c'est lai-iemecoordonneede la suite.

Le produit cartesien generalise est l'ensembleYi2IAi:=f(ai)i2Ij(8i2I)ai2Aig:(1.23)Par convention, le produit videQk2;Akest un ensemble a un element :fg(unsingleton).

Onverie alors que3Yk2I+JAk! Yi2IAi!0Yj2JAJ1A:(1.24)Le cas particulier qui correspond a choisirI= [n] donne la construction du produit cartesienA1A2 An=f(a1;a2;:::;an)jai2Ai;1ing;et lorsqueAi=B, pour tous lesi, on obtient lapuissance cartesiennen-ieme,Bn:=BB B|{z}ncopies;de l'ensembleB, avecB0:=fg.

On a alors les identites suivantes (modulo les bijections naturellesnecessaires)(i)BnBk!Bn+k;et (iii)( Bn)k!Bnk:(1.25)3.A strictement parler, les elements des ensembles compares ici ne sont pas egaux.

Plut^ot qu'une egalite, on aune bijection naturelle entre les deux ensembles, ce qui signie qu'on doit transformer legerement les elements pourpouvoir les comparer (voir Exercice1.312CHAPITRE 1.

ENSEMBLES ET FONCTIONSRelations.UnerelationR, allant d'un ensembleAvers un ensembleB, est simplement unsous-ensemble du produit cartesienAB, c.-a-d. :RAB.

Larelation transposeedeBversA, denoteeRT, est donnee par le sous-ensembleRT:=f(y;x)j(x;y)2RgdeBA.

Par exemple, pourA=fa;b;c;dgetB=f1;2;3g, on a la relationR=f(a;1);(a;2);(b;3);(c;2);(d;1)g;dont la transposee est la relationRT=f(1;a);(1;d);(2;c);(2;a);(3;b)g:On designe parRel[A;B] l'ensemble des relations deAversB.

Observons que, par denition, on aRel[A;B] =P[AB]:(1.26)SiA=fa;bg, etB=f1;2g, l'ensembleRel[A;B] contient les 16 elements :Rel[A;B] =f; ;f(a;1)g;f(a;2)g;f(b;1)g;f(b;2)g;f(a;1);(a;2)g;f(a;1);(b;1)g;f(a;1);(b;2)g;f(a;2);(b;1)g;f(a;2);(b;2)g;f(b;1);(b;2)g;f(a;1);(a;2);(b;1)g;f(a;1);(a;2);(b;2)g;f(a;1);(b;1);(b;2)g;f(a;2);(b;1);(b;2)g;f(a;1);(a;2);(b;1);(b;2)gg :On denoteRelk[A;B] l'ensemble des relations deAversBcontenantkcouples.

Clairement, on aRel[A;B] =Xk0Relk[A;B]:(1.27)1.

3) FonctionsBien que la notion de fonction soit l'une des plus importantes en mathematiques, ce n'est qu'ala n du dix-neuvieme siecle qu'elle a pris la forme moderne4qu'on lui conna^t.

Unerelation4. On ne sait trop qui doit ^etre credite pour cela.1.3.

FONCTIONS13fonctionnellef, de l'ensembleAvers l'ensembleB, est une relationfAB, qui possede lapropriete que :pour toutx2A, il y a un et un seuly2Btel que (x;y)2f:(1.28)Autrement dit, l'elementxdansAcaracterise uniquement l'element correspondantydansB.

Il esthabituel de designer parf(x) cet element, et on a doncf(x) =yssi (x;y)2f:(1.29)Formellement parlant, unefonctiondeAversBest un triple (f;A;B), avecfun relation fonc-tionnelle deAversB.

Il est habituel d'ecriref:A!Bpour ce triple.

Ainsi, on a la fonctionf:fa;b;c;dg ! f1;2;3g, telle quef=f(a;1);(b;3);(c;2);(d;1)g:(1.30)Elle peut aussi se decrire en ecrivant que :f(a) = 1; f(b) = 3; f(c) = 2;etf(d) = 1:On ecrit aussi parfoisx7!f(x);pour signier que le couple (x;f(x)) fait partie de la relation fonctionnellef.

Ceci est parti-culierement utile lorsquefest decrite par une formule.

On peut penser a une fonction commeetant un processusfquichoisit un elementf(x) deBpour chaque elementxdeA.Pour une fonctionf:A!B,