Next PDF List

Combinatoire énumérativeIgor Kortchemski-Introduction-La Combinatoire est un sous-art des mathématiques qui consiste à compter et à étudierdes structures finies.

De nombreux problèmes difficiles sont formulés de manière très simple(mais la résolution nécessite des outils avancés).

Le but de ce cours est de présenter quelquesréflexes et idées de bases pouvant être utiles dans la résolution d"exercices de combinatoirede type olympiades.On parlera de coefficients binomiaux, double-comptage, injections, surjections, bijections.

1) Coef ficientsbinomiaux1.

1) DéfinitionsOn rappelle qu"un ensembleEest une collection d"éléments dont l"ordre n"a pas d"impor-tance (ainsi, les ensemblesf2,3getf3,2gsont les mêmes ensembles) et comptés sans multipli-cité (par exemple, 2,2=2).

On notex2Asixappartient à l"ensembleA.

SiAetBsont deuxensemble, on écritABet on dit queAest inclus dansBsi chaque élément deAappartient àB.

L"ensemble vide, qui ne contient aucun élément, est noté;. On note Card(A)(on prononce" cardinal deA») le nombre d"éléments deA.

On dit queAest infini si Card(A) =1, finisinon.Définition 1.Pour des entiers 06k6n, on notenk(et on prononce "kparmin») le nombrede manières de choisir un sous-ensemble àkéléments d"un ensemble ànéléments différents.Pourk > n, on posenk=0.Il est clair que dans la définition précédente,nkne dépend pas de l"ensemble ànélémentsdifférents considéré.Exemple 2.On a42=6, car les sous-ensembles à 2 éléments def1,2,3,4gsontf1,2g,f1,3g,f1,4g,f2,3g,f3,4get il y en a 6Pour un entiern>1, rappelons la notationn!=123 (n-1)n.

On lit "nfactorielle".Proposition 3.Le nombre de manières d"ordonnernéléments estn!.Démonstration.Nous avonsnpossibilités pour choisir le premier élément,n-1 possibilitéspour le deuxième, et ainsi de suite jusqu"au dernier élément pour lequel nous avons une seulepossibilité.

Le résultat en découle.

1) Proposition 4.Pour des entiers 06k6n, on a :nk=n!(n-k)!k!.Démonstration.Utilisons le principe dedouble-comptage, très important en combinatoire.

Ilconsiste à établir une égalité en comptant de deux manières différentes une certaines quan-tité.

Ici, comptons le nombre de suites àkéléments qu"on peut créer en utilisant lesnélémentsd"un ensemble ànéléments différents.D"une part, comme pour la proposition précédente, nous avonsnchoix pour le premierterme de la suite;n-1 choix pour le deuxième, et ainsi de suite jusqu"auk-ième élément pourlequel nous avonsn-k+1 choix.

Finalement, il y a en toutn(n-1)(n-k+1) =n!(n-k)!suites àkéléments.D"autre part, pour créer une suite àkéléments, on peut commencer par choisir leskélé-ments qui vont constituer la suite (nkpossibilités), puis les ordonner (k! manières possiblesde les ordonner).

Il y a donc en toutk!nksuites àkéléments.1.

2) Propriétés combinatoiresExercice 1Pour des entiers 06k6n, on a :nk=nn-kSolution de l"exercice 1Première méthode :On utilise la formulenk=n!(n-k)!k!et le résultaten découle immédiatement.Deuxième méthode :On remarque que choisirkéléments parminrevient à sélectionner lesn-kéléments qu"on ne choisira pas.L"exercice précédent, bien que facile, est assez représentatif des exercices ayant pour butde prouver des relations d"égalité entre coefficients binomiaux.

Très souvent, il y a toujours(au moins) deux approches possibles : remplacer les coefficients binomiaux par leur formuleet ramener le problème à un exercice de manipulation de relations algébriques, ou bien inter-préter de manière combinatoire les deux termes de part et d"autre de l"égalité et prouver qu"ilssont égaux.

La deuxième approche est bien sûr bien plus élégante et fournit très souvent despreuves courtes, mais requiert davantage d"ingéniosité.Proposition 5.(formule de Pascal) Soientnet 06k6ndes entiers (avec(k,n)6= (0,0)).Alors :nk=n-1k+n-1k-12Démonstration.Pr emièreméthode : On utilise la formule :n-1k+n-1k-1=(n-1)!k!(n-1-k)!+(n-1)!(k-1)!(n-k)!(n-1)!(k-1)!(n-1-k)!1k+1n-k(n-1)!(k-1)!(n-1-k)!nk(n-k)n!k!(n-k)!Secondeméthode:Démontronscerésultatdemanièrecombinatoire.Considéronsl"ensemblef1,2, ,nget dénombrons ses sous-ensembles àkéléments.

On distingue les ensembles quicontiennent l"élémentnet les ensembles qui ne le contiennent pas.

Il y an-1kensembles quine contiennent pasn(on choisitkéléments dansf1,2, ,nget il y en an-1k-1qui contiennentn.

Au total on a doncn-1k+n-1k-1manières de choisir noskéléments parmi nosnentiers,d"où le résultat.La formule de Pascal nous permet ensuite de construire le triangle de Pascal, que vousconnaissez peut-être déjà.

La case située dans lak-ième colonne de lan-ième ligne contient lecoefficient binomialn-1k-1.

D"après la formule de Pascal, on obtient donc chaque case commela somme des deux cases qui sont au-dessus.111121133114641151010511615201561172135352171Onconstatequ"ilyaunlienentrelan-ièmelignedutriangledePascaletledéveloppementde(x+y)n:Proposition 6(Formule du binôme de Newton).Soientx,ydes nombres réels etn>1 unentier.

Alors :nXk=0nkxkyn-k= (x+y)n.Notation.Avant de démontrer cette formule, un petit rappel de notation :3Lorsqu"on veut faire une grosse somme de termes qui peuvent s"exprimer selon un entier,souvent noték(ouimais cela n"a pas d"importance), qui varie entre deux valeurs, on utilisele symboleP.

Par exemple :nXk=01=1+1+ +1=n+1nXk=0k=0+1+2+ +n=n(n+1)2nXk=0nk=n0+n1+ +nn-1+nnPour un produit on utilise de la même manière le symboleQ.

Par exemple :nYk=1k=n!Démonstration.Pr emièreméthode : par récurrence surn(s"entraîner à le faire).Seconde méthode :lorsqu"on développe(x+y)(x+y)(x+y), pour trouver le coefficientdevantxkyn-k, parmi lesntermes(x+y), il faut en choisirkpour lesquels on garde lexetqui vont donner un termexk, et lesn-kautres termes pour lesquels on sélectionney(et quisont fixés par le choix deskpremiers) vont donner le termeyn-k.

Le résultat s"ensuit.Exercice 2Pour tout entiern>1, on anXk=0nk=2n.Exercice 3Pour 06k6n, on a :knk=nn-1k-1Exercice 4Quel est le cardinal moyen d"un sous-ensemble def1,2, ,ng?Exercice 5Prouver que pour 06m6n:nXk=0nkkm=nm2n-m.Exercice 6Combien y a-t-il de chemins surZ2issus de(0,0), faisant des pas+(1,0)ou+(0,1),et finissant en(m,n), oùm,n>0?Exercice 7De combien de manières peut-on placer 5 pièces identiques dans 3 poches diffé-rentes?4Solution de l"exercice 2Première méthode :Si on n"a pas d"idée comment commencer de ma-nière astucieuse, on peut essayer de procéder par récurrence surn.

Pourn=1, le résultat estclair.

Supposons le résultat acquis au rangnet montrons-le au rangn+1 en écrivant, avec laformule de Pascal :n+1Xk=0n+1k=1+n+1Xk=1nk+nk-1nXk=1nk+nXk=0nk=2n+2n(par hypothèse de récurrence)=2n+1,Seconde méthode :Démontrons ce résultat de manière combinatoire en comptant le nombreNde sous-ensembles def1,2, ,ng.

D"une part, pour un entier 06k6n, il y anksous-ensembles àkéléments.

En sommant le tout, on voit queN=Pnk=0nk.Mais, pour construire un sous-ensemble def1,2, ,ng, on a le choix de choisir 1 ou non,2 ou non, et ainsi de suite jusqu"àn.

On a doncnchoix à faire entre deux possibilités et ceschoix sont indépendants (le choix de prendrekou non n"influence pas le choix de prendrek0ou non sik6=k0), d"oùN=2n, ce qui permet de conclure.En particulier, la solution précédente montre qu"il existe 2nsous-ensembles d"un ensembleànéléments.Troisième méthode :On utilise la formule du binôme de Newton avecx=y=1.Solution de l"exercice 3Première méthode :On utilise la formule exprimantnk(on vous laissele faire).Seconde méthode :Démontrons ce résultat de manière combinatoire en comptant de deuxmanières différentes le nombre de sous-ensembles def1,2, ,ngde cardinalkayant un élé-ment distingué (qu"on appellera chef).D"une part, il suffit de choisir un sous-ensemble de cardinalk(nkchoix), puis de choisirun chef (kchoix indépendants).

On obtient donc en toutknkpossibilités.D"autre part, on peut d"abord choisir un chef (nchoix) puis compléter lesk-1 éléments àchoisir dansf1,2, ,ngprivé du chef (donc un ensemble àn-1 éléments).

Il y a alorsnn-1k-1éléments.Solution de l"exercice 4Première méthode (d"après une idée d"élèves) :On regroupe un ensemble avec son complémen-taire.

SiAf1,2, ,ng, on noteAcl"ensemble des entiers def1,2, ,ngqui ne sont pas dansA. NotonsNce cardinal moyen.

Alors :N=12nXAf1,2, ,ngCard(A) =12nXAf1,2, ,ngCardA+Card(Ac)212nXAf1,2, ,ngn2=12nn22n=n2Autre méthodes :Il faut évaluer la sommeSn=12nnXk=0knk5Si on ne sait pas commencer, il faut étudier les premiers cas :n=1,2, On trouve toujoursSn=n=2.

Essayer donc de démontrer cela.Seconde méthode :Si on n"a pas d"idée, on peut procéder par récurrence surn.Troisième méthode, plus avancée.

On utilise le résultat de la proposition6 . Considérons lepolynômePn(x) =Pnk=0nkxk.

D"après la formule du binôme de Newton,Pn(x) = (1+x)n.Dérivons cette égalité par rapport àx:nXk=0knkxk-1=n(1+x)n-1.Évaluons alors cette quantité enx=1 :nXk=0knk=n2n-1.Le résultat en découle.Solution de l"exercice 5On remarque d"abord que seuls lesktels quek>mcontribuentde manière non nulle.

On va procéder à un double comptage en comptant le nombreNdesous-ensemblesA,Bdef1,2, ,ngtels queABet Card(A) =m.

En effet, d"une part, pourconstruireA,Bon peut d"abord choisirAde cardinalm(nmchoix), puis rajouter un sous-ensemble quelconque de l"ensemblef1,2, ,ngprivé des éléments deA, qui an-méléments(et donc 2n-mchoix indépendants).

En ainsi,N=nm2n-m.D"autre part, pour construireA,Bon peut d"abord choisirBde cardinal quelconque entremetn(siBest de cardinalk,nkchoix), puis choisirAde cardinalmcomme sous-ensembledeB(kmchoix siBest de cardinalk).

Ainsi,N=Pnk=0nkkm.Solutiondel"exercice6Untelchemindoitfairem+npas,dontmfois+(1,0)etnfois+(0,1).Il suffit donc de choisir parmi lesm+npas possibles la position desmqui font+(1,0).

Lenombre total vaut doncm+nm.Solution de l"exercice 7Considérons la figure suivante (avec deux barres) :Remplaçons chaque rond soit par une pièce, soit par une barre de sorte qu"il y ait en tout 2barreset5pièces.Lespiècesentrelesdeuxpremièresbarresserontcontenuesdanslapremièrepoche,lespiècesentreladeuxièmebarreetlatroisièmebarreserontcontenuesdanslasecondepoche, et finalement les pièces entre la troisième barre et la quatrième barre seront contenuesdans la troisième poche.Ainsi, placer 5 pièces identiques dans 3 poches différentes, revient à choisir la position des2 barres parmi 7 positions possibles.

La réponse est donc72=21.Plus généralement, en procédant de la même façon, on voit qu"il y aa+b-1b-1=a+b-1amanières de placerapièces identiques dansbpoches différentes.62Principe d"Inclusion-ExclusionOn sait que siAetBsont deux ensembles finis, alors Card(A[B) =Card(A)+Card(B)-Card(A\B).

La formule suivante, dite d"inclusion-exclusion, généralise cela au cas où nousen avons un nombre quelconque.Proposition 7(Formule d"inclusion-exclusion).SiA1, ,Ansont des ensembles finis, alors :Card(A1[A2[ [An) =nXk=1(-1)k+1X16i1<

Ils reviennent et prennent un t-shirt complètement au hasard.Quelle est la probabilité que personne ne se retrouve avec son t-shirt?Solution de l"exercice 8Trouvons plutôt le nombre d"entiers strictement positifs inférieursou égaux à 120 divisibles par 3, 5, ou 7.

NotonsA(respectivementBetC) l"ensemble desnombres entiers strictement positifs divisibles par 3 (respectivement 5 ou 7).

On a :jAj=1203=40(1)jBj=1205=24(2)jCj=1207=17(3)jA\Bj=12035=8(4)jB\Cj=12057=3(5)jC\Aj=12073=4(6)jA\B\Cj=120357=1(7)D"où d"après la formule d"inclusion-exclusion,jA[B[Cj=40+24+17-8-5-3+1=66.Ainsi, le nombre cherché vaut 120-66=54.Solution de l"exercice 9On assigne à chaque stagiaire un chiffre différent entre 1 etn, et onnotexile numéro de l"élève prenant lei-ième t-shirt.

Ainsi,(x1, ,xn)est une permutation7de(1, ,n).

Calculons plutôt la probabilité qu"au moins une personne retrouve son t-shirten vue d"utiliser le principe d"inclusion-exclusion.

Pour 16i6n, soitAil"ensemble despermutations telles quexi=i.

Il est clair que pour 16i1<< ik6n, on a :Card(Ai1[ [Aik)= (n-k)!.Ainsi, d"après la formule d"inclusion-exclusion :Card(A1[A2[ [An) =nXk=1(-1)k+1X16i1<

3) Injections, surjections, bijectionsDéfinition 8.Uneapplicationf:E!Fpermet d"associer à tout élémentxde l"ensembleEununique élément, notéf(x)de l"ensembleF.On dit queEest l"ensemble de départ,Fl"ensemble d"arrivée.

Sif(x) =y, on dit quexestl"antécédentdeyetyl"imagedex.3.

1) Injections et surjectionsDéfinition 9.SoientE,Fdeux ensembles etf:E!Fune application.(i)On dit que festinjectivesi pour tousx,y2Eavecx6=y,f(x)6=f(y).(ii)On dit que festsurjectivesi pour touty2F, il existex2Etel quef(x) =y.Pour montrer quef:E!Fest injective, on montre très souvent que six,y2Esont telsquef(x) =f(y), alorsx=y(voir le cours sur les équations fonctionnelles).On introduit la notation[n] =f1,2, ,ngpour un entiern>1.Proposition 10.Il existe une injection[m]![n]si, et seulement si,m6n.

Il existe unesurjection de[m]![n]si, et seulement si,m>n.

8) Démonstration.Exercice.En pratique, on utilise la proposition précédente en combinatoire comme suit : pour mon-trer quea6b, on construit deux ensemblesA,Btels que Card(A) =a, Card(B) =b, ainsiqu"une injection deAdansB.

Ou encore, pour montrer quea>b, on construit deux en-semblesA,Btels que Card(A) =a, Card(B) =b, ainsi qu"une surjection deAdansB.Exercice 10(Olympiades Balkaniques de Mathématiques 199.

7) Soientm,n >1 des entiers.SoitSun ensemble de cardinalnetA1,A2, ,Amdes sous-ensembles deS. On suppose quepour tous élémentsx6=ydeS, il existe 16i6mtel quex2Aiety62Ai, ou bienx62Aiety2Ai. Prouver quen62m.Exercice 11(i)Combien ex iste-t-ilde fonctions de [m]![n]?(i)On suppose m6n. Combien existe-t-il d"injections de[m]![n]?(ii)On suppose m>n.

Combien existe-t-il de surjections de[m]![n]?Solution de l"exercice 10À tout élémentx2S, on associe lem-uplet(x1, ,xm)oùxi=0six62Aietxi=1 six2Ai.

Cette application est définie surS, et son ensemble d"arrivéeestf0,1gm. Par hypothèse, six6=y, alorsf(x)6=f(y). Ainsi,fest injective.

Le cardinal del"ensemble de départ est donc inférieur ou égal au cardinal de l"ensemble d"arrivée.Solution de l"exercice 11Pour (i), il y en a clairementnm(nchoix pour chacun desmentiersau départ)Pour (ii), on anchoix pour l"image de 1,n-1 choix pour l"image de 2, et ainsi de suitejusqu"àmpour lequel on an-m+1 choix pour son image.

La réponse est doncn!(n-m)!.Pour(iii),onvautiliserleprinciped"inclusion-exclusionetcompterlenombredefonctions[m]![n]qui ne sont par surjectives. À cet effet, pour 16i6n, notonsAil"ensemble desfonctions[m]![n]telles quein"est pas atteint par la fonction.

Il est clair que pour des entiers16i1<< ik6n, on a Card(Ai1\ Aik) = (n-k)m, car chaque élément de[m]peutêtre envoyé sur un desn-kentiers de[n]autorisés.

Ainsi, d"après le principe d"inclusionexclusion, si on notes(m,n)le nombre de surjections de[m]![n], on a :nm-s(m,n) =Card(A1[A2[ [An)nXk=1(-1)k+1X16i1<

2) Preuves par bijections en combinatoireDéfinition 11.SoientE,Fdeux ensembles etf:E!Fune application.

On dit quefestbijectivesi elle est à la fois injective et à la fois surjective.Proposition 12.SoientAetBdeux ensembles finis.

AlorsAetBont même cardinal si, etseulement si, il existe une bijection entreAetBDémonstration.ExerciceEn combinatoire, cette proposition est souvent utilisée de la manière suivante.

Si on veutmontrer quea=b, oùa,b>0 sont des entiers, il suffit de trouver deux ensembles finisAetBtels que Card(A) =aet Card(B) =b, et de construire une bijection entreAetB.Pour vérifier qu"une fonction est bijective, il est parfois pratique d"exhiber la fonction réci-proque.

Plus précisément :Proposition 13.Sif:A!Betg:B!Asont deux fonctions telles quef(g(b)) =bpourtoutb2Betg(f(a)) =apour touta2A, alorsfetgsont des bijections (on dit qu"elles sontréciproques, ouinverses, l"une de l"autre).Démonstration.Montrons d"abord quefest surjective.

Soitb2B. On sait quef(g(b)) =b,ainsig(b)est un antécédent deb, de sorte quefest surjective. Pour montrer l"injectivité,soientx,y2Etels quef(x) =f(y)et montrons quex=y. On ax=g(f(x)) =g(f(y)) =y. Lafonctionfest donc injective, et comme elle est surjective, elle est bien bijective. Par symétrie,gest aussi bijective.Exercice 12(Canada 200.

5) Soit un triangle équilatéral dont le côté est de longueurn, divisé entrianglesunitairestelqu"illustré.Soitf(n)lenombredecheminsallantdutriangledelarangéeduhautjusq"autriangleaucentredelarangéedubas,defaçonàcequedestrianglesadjacentspartagent une arête commune et que le chemin ne repasse jamais par le même triangle et qu"iln"aille jamais vers le haut (d"une rangée inférieure à une rangée supérieure).

Un tel cheminest illustré ci-après avecn=5.

Déterminer la valeur def(2012).Solution de l"exercice 12L"application qui à un chemin associe un(n-1)-uplet(x1, ,xn-1)oùxiest l"entierxtel que le chemin traverse lai-ième ligne horizontale en partant du haut aux-ième segment en partant de la gauche.

Cette application est clairement une bijection entrel"ensemble des chemins considérés et l"ensemble[1][2] [n-1], qui est de cardinal(n-1)!.

Ainsi,f(2012) =2011!.10