[PDF] Chap. 3 : Combinatoire élémentaire.

View - Download Chap. 3 : Combinatoire élémentaire.

Previous PDF

Next PDF

Universite Paul Sabatier

Licence L3 E (Mathematiques pour l'enseignement)

2018-2019

Alg ebre 1

Chap. 3 : Combinatoire elementaire.

Table des mati

eres

1. Arrangements avec et sans repetition 1

1.1. Parties d'un ensemble et applications 1

1.2. Arrangements, injections et bijections 1

2. Combinaisons sans et avec repetition 2

2.1. Combinaisons sans repetition et coecients binomiaux 2

2.2. Coecients multinomiaux 3

2.3. Combinaisons avec repetition 3

3. Le principe d'inclusion-exclusion (PIE) 4

3.1. Le PIE (ou formule du crible) 4

3.2. Application au calcul du nombre de surjections 4

3.3. Application au calcul de l'indicatrice d'Euler 5

4. Actions de groupes6

5. Exercices8

1.Arrangements avec et sans repetition

On suppose queXetYsont deux ensembles nis avecjXj=ketjYj=n.

1.1.Parties d'un ensemble et applications.Le cardinal de l'ensembleYXdes applications deXdansY

ne depend que de ceux deXet deY, que ces derniers soient nis ou innis (exercice facile). Les applications

def1;2;:::;kgdansYsont parfois appelees les arrangements avec repetition dekelements deY. Proposition 1.1.Le nombre d'applications deXdansY(ou d'arrangements avec repetition dekelements de

Y) est egal ank. Autrement dit :YX=jYjjXj:

Preuve :Il s'agit dekchoix independants d'une valeur parmin. Pour plus de details, voir https ://fr.wikiversity.org/wiki/Combinatoire/Arrangementsavecrepetition. Corollaire 1.2.L'ensembleP(X)des parties (ou sous-ensembles) deXa pour cardinal2k. Autrement dit : jP(X)j= 2jXj: Preuve :L'application deP(X) dansf0;1gXqui, a toute partieAdeX, associe sa fonction indicatriceA, est une bijection (revoir l'exercice du chapitre 1 sur cette bijection).

1.2.Arrangements, injections et bijections.Un arrangement est une selection d'objets qui tient compte

de l'ordre (tirage sans remise de boules distinguables dans une urne, tierces dans l'ordre, etc.) : Denition 1.3.Un arrangement (sans repetition) dekelements deYest unk-uplet d'elements distincts de Y, autrement dit : une injection def1;2;:::;kgdansY. Une permutation deYest une bijection deYdans lui-m^eme. L'ensemble des permutations deYest noteSY ou, siY=f1;2;:::;ng,Sn. Le cardinal de l'ensemble des injections deXdansYne depend que de ceux deXet deY, que ces derniers

soient nis ou innis, et idem pour les bijections deXdansY(exercices faciles). En outre, siXetYsont deux

ensemblesnisde m^eme cardinal, alors toutes les injections de l'un dans l'autre sont des bijections. 1 2 Denition 1.4.SoientjXj=ketjYj=n. Le nombre d'injections deXdansY, ou nombre d'arrangements dekelements deY, ounombre d'arrangements dekobjets parmin, est noteAkn.

Proposition 1.5.Akn=n(n1):::(nk+ 1) =(0sik > n;

n!(nk)!si0kn:

En particulier,jSnj=Ann=n!.

Preuve :Immediat sik > n. Pourkn, compter les choix successifs de l'image de 1, puis l'image de

2, etc. jusqu'akou plus formellement, faire une recurrence surk(pour les details des deux methodes, voir

https ://fr.wikiversity.org/wiki/Combinatoire/Arrangementssansrepetition).

Remarques 1.6.

1) On a determine le nombre d'injections et le nombre de bijections. Le nombre de surjections ne se calcule

pas aussi aisement (cf.x3.2).

2) Les nombresk!croissent tres vite lorsquekaugmente. La formule de Stirling donne une approximation

de l'application factorielle : n!p2nne n

Exercice : 1.

2.Combinaisons sans et avec repetition

2.1.Combinaisons sans repetition et coecients binomiaux.Une combinaison est une selection d'objets

qui ne tient pas compte de l'ordre (tierces dans le desordre, ...). Denition 2.1.SoitjYj=n. Unecombinaison(sans repetition) dekelements deYest une partie deYak elements. Le nombre de ces \combinaisons dekelements parmin" est le coecient binomial noten k(autrefois C kn).

Proposition 2.2.

n k =Aknk!=(0sik > n; n!k!(nk)!si0kn: Preuve :Le nombreAkndek-arrangements dansYest le produit den k(nombre de parties deYakelements) park! (nombre de bijections def1;:::;kgdans une telle partie). Pour plus de details, voir https ://fr.wikiversity.org/wiki/Combinatoire/Combinaisonssansrepetition.

Remarque 2.3.On demontre tres facilement (exercice : par le calcul ou par un raisonnement combinatoire) :n

nk =n k ;n 0 =n n = 1;n 1 =n n1 =n: Proposition 2.4. Formule de PascalPour tous les entiersketntels que0< k < n1,n+ 1 k =n k +n k1

Preuve :combinatoire (on xe l'un desn+ 1 elements et l'on compte separement les parties akelements qui

le contiennent et celles qui ne le contiennent pas) ou calculatoire (on utilise les expressions avec des factorielles),

cf. respectivement, sur https ://fr.wikiversity.org/wiki/Sommation/ : Exercices/Sommationdecombinaisons#Exercice6-3 et Formuledubin^ome#Lemmepreliminaire). Les coecients binomiaux apparaissent ainsi dans letriangle de Pascal:

1 1 1 1 1

1 2 3 4

1 3 6 1 4 1 qui se construit aisement en utilisant la formule de la Proposition 2.4.

Theoreme 2.5. Formule du bin^ome de Newton.n

kest le coecient dexkynkdans le developpement du polyn^ome(x+y)n. Autrement dit, (x+y)n=nX k=0 n k x kynk:1. Ou plus generalement, pour tous entiers relatifsnetk, avec la conventionn k= 0 sik <0 ouk > n. 3 Preuve :par recurrence en utilisant la proposition 2.4 (cf. https ://fr.wikiversity.org/wiki/

ou par simple observation du developpement de (x+y)n(cf. \Formule du bin^ome de Newton" sur Wikipedia).

Exercices : 2, 3, 4, 5.

2.2.Coecients multinomiaux.On a vu quen

k=n nkest le nombre de couples (A;B) de parties d'un ensembleYanelements, complementaires l'une de l'autre et telles quejAj=k(doncjBj=nk). Plus

generalement, on peut s'interesser aux \partitions calibrees" (ce sont presque des partitions, sauf que certaines

parties peuvent ^etre vides, et que les parties sont numerotees) :

Proposition 2.6.

Etant donnesrentiers naturelsk1;:::;krde sommen=jYj, le nombre der-uplets (A1;:::;Ar)de parties deY, disjointes deux a deux et telles quejAij=ki, est le coecient multinomialn k

1;:::;kr

:=n!k

1!:::kr!:

Preuve :On choisit successivementA1Yde cardinalk1,A2YnA1de cardinalk2, etc. doncn k

1;:::;kr

=n k 1 nk1 k 2 :::nk1 kn1 k n Apres expression en termes de factorielles et simplication, on obtient la formule annoncee.

On peut alors generaliser la formule du bin^ome (en procedant, comme pour cette derniere, par recurrence ou

examen direct) :

Proposition 2.7.

(X1++Xr)n=X k i0;Pki=n n k

1;:::;kr

X k11:::Xkrr: Remarque 2.8.En developpant(1+1++1)n, cette formule du multin^ome donnern=P k i0;Pki=n n k

1;:::;kr.

Puisque

n k

1;:::;krest le nombre d'applicationsfdeYdansZ:=f1;:::;rgtel que1aitk1antecedents, ...,

raitkrantecedents et qu'on fait la somme sur toutes les possibilites(k1;:::;kr)(veriant necessairementPki=f1(Z)=jYj=n), on retrouve ainsi la formule de la proposition 1.1 :jZjjYj=ZY.

Exercice : 6.

2.3.Combinaisons avec repetition.Une combinaison avec repetition dekobjets pris dans un ensembleY

denobjets discernables est une maniere de piocherkfois de suite un objet dansY, sans tenir compte de l'ordre

deskchoix et \avec remise", un m^eme objetypouvant donc ^etre selectionnef(y) fois, avecf(y)2N: Denition 2.9.Unek-combinaison avec repetition dans l'ensembleYest un multiensemble dekelements de

Y(non ordonnes, et comptes avec leurs repetitions eventuelles), autrement dit : une applicationf:Y!Ntelle

queP y2Yf(y) =k.

Une telle combinaison peut aussi ^etre vue comme une repartition dekobjets indiscernables parminbo^tes

discernables (distribution dekbonbons anenfants).

Theoreme 2.10.Soientm;n;kentiers. On supposen1.

1) Le nombre den-uplets d'entiersstrictement positifsde sommemest egal am1

n1.

2) Le nombre den-uplets d'entierspositifs ou nulsde sommekest egal an+k1

n1=n+k1 k.

3) Le nombre dek-combinaisons avec repetition dans ensemble ni de cardinalnest aussi egal an+k1

k.

Preuve :

1) Cesn-uplets sont en bijection avec les parties de cardinaln1 de l'ensemblef1;2;:::;m1g, par

l'application qui a (x1;:::;xn) associe l'ensemblefx1;x1+x2;x1+x2+x3;:::;x1+x2++xn1g.

2) Cesn-uplets (z1;:::;zn) sont en bijection avec lesn-uplets (x1;:::;xn) d'entiers strictement positifs de

sommen+k, en posantxi=zi+ 1. Ce point resulte donc du precedent.

3) Sans perte de generalite, l'ensemble de cardinalnconsidere estf1;2;:::;ng. Ce point resulte donc du

precedent. Pour plus de details, voir https ://fr.wikiversity.org/wiki/Combinatoire/Combinaisonsavecrepetition.

Exercices : 7, 8, 9.

4

3.Le principe d'inclusion-exclusion (PIE)

3.1.Le PIE (ou formule du crible).Leprincipe d'inclusion-exclusionde De Moivre est aussi appeleformule

du crible. Le cardinal deX[Yse deduit des cardinaux deX,YetX\Y: jX[Yj=jXj+jYj jX\Yj:

Le principe est simple : on compte les elements deX, ceux deYet l'on enleve ceux de l'intersection (pour ne

pas les compter deux fois). Le principe se generalise au cas de trois ensembles : on compte les elements deX,

ceux deYet ceux deZpuis on enleve ceux qu'on a comptes deux fois mais il faut alors rajouter ceux qu'on

avait initialement comptes trois fois (c.-a-d. ceux qui sont dans les trois ensembles) : jX[Y[Zj=jXj+jYj+jZj jX\Yj+jX\Zj+jY\Zj+jX\Y\Zj:

Plus generalement :

Theoreme 3.1.Soientnensembles nisA1;:::;An. Pour tout ensemble d'indicesI f1;:::;ng, notons A I:=\ i2IA i:

Alors,

n i=1A i =X ?6=If1;:::;ng(1)jIj1jAIj=nX k=1(1)k1X

If1;:::;ng

jIj=kjAIj: Preuve :La fonction (denie surA:=[Aia partir des fonctions indicatrices desAi) (1A1)(1A2)(1An)

est identiquement nulle car pour toutx2A, au moins l'un desAi(x) est egal a 1. En developpant ce produit,

on en deduit que 0 =X

If1;:::;ng(1)jIjAI= 1 +X

?6=If1;:::;ng(1)jIjAI; soit 1 =X ?6=If1;:::;ng(1)jIj1AI:

On conclut en faisant, de part et d'autre de cette egalite de fonctions, la somme des valeurs quand la variable

parcourtA.

Remarques 3.2.

| L'enonce du theoreme reste valide pourn= 0, puisqu'une union indexee par?est vide et qu'une somme indexee par?est nulle. | SiA1;:::;Ansont des parties d'un ensemble ni de cardinalNdont les elements sont consideres comme equiprobables, on obtient, en divisant l'egalite du theoreme parN: p n[ i=1A i! =X ?6=If1;:::;ng(1)jIj1p(AI) =nX k=1(1)k1X

If1;:::;ng

jIj=kp(AI): Cette formule est en fait valide pour un nombre ni d'evenementsA1;:::;And'un espace probabilise quelconque(la demonstration est analogue a celle du theoreme ci-dessus).

3.2.Application au calcul du nombre de surjections.

Proposition 3.3.Soientpetqdeux entiers tels que0qp. Le nombreSp;qde surjections d'un ensemble apelements dans un ensemble aqelements est donne par : S p;q=qX k=0(1)qkq k k p:

Preuve :Supposons quejXj=petjYj=q.

Pour touty2Y, soitAyl'ensemble des applications deXdansYqui ne prennent jamais la valeury(ce n'est

pas utile pour la suite mais entra^nez-vous a l'ecrire formellement { solution en note en bas de cette page :

2) . Une surjection deXsurYest alors une application deXdansYqui n'est dans aucunAy. On a donc S p;q=YXn [y2YAy=qp j[y2YAyj:2.Ay=ff2YXjf1(fyg) =?g. 5

Or d'apres la formule du crible,

j[ y2YAyj=qX k=1(1)k1X ZY jZj=kjAZj; ouAZ:=\y2ZAyest l'ensemble des applications deXdansYpour lesquelles aucun element deZn'a d'antecedent. Il y en a autant que d'applications deXdansYnZ, c'est-a-dire : jAZj= (q jZj)p et en reportant : j[ y2YAyj=qX k=1(1)k1X ZY jZj=k(qk)p qX k=1(1)k1(qk)pjfZYj jZj=kgj qX k=1(1)k1q k (qk)p puis S p;q=qp j[y2YAyj =qpqX k=1(1)k1q k (qk)p qX k=0(1)kq k (qk)p qX j=0(1)qjq qj j p qX j=0(1)qjq j j p:

Remarques 3.4.

| Pourq= 0, cette formule donneSp;0= 0p. Eectivement,S0;0= 1(l'unique application de?dans?est bien surjective) etSp;0= 0psip >0(il n'y a pas d'application d'un ensemble non vide dans?). | Pourq=p, les surjections sont les bijections doncSp;p=p!. | Les Sp;qq!sont appeles les nombres de Stirling de seconde espece. C'est le nombre, pour un ensemble de

cardinalp, de partitions enqsous-ensembles ou, ce qui revient au m^eme, de relations d'equivalence ayant

qclasses.

3.3.Application au calcul de l'indicatrice d'Euler.Pour un entiern1, on note'(n) le nombre d'entiers

de [1;n] premiers avecn. L'application'est appeleeindicatrice d'Euler. Theoreme 3.5.SoitPl'ensemble des diviseurs premiers den. Alors, '(n) =nY p2P 11p 6

Preuve :Pour toutp2P, notonsApl'ensemble des entiers de [1;n] divisibles parp. Le principe d'inclusion-

exclusion nous dit que : '(n) =n j[p2PApj =nX ?6=QP(1)jQj1j\p2QApj =n+X ?6=QP(1)jQjnQ p2Qp =nX

QP(1)jQjQ

p2Qp =nX QPY p2Q1p =nY p2P 11p

Exercices : 10, 11, 12.

4.Actions de groupes

La derniere section de ce cours n'a aucunement l'ambition d'echafauder ne serait-ce que les premieres bribes

de la theorie des groupes, mais seulement de la \regarder fonctionner" sur quelques exemples, qui nourriront

l'intuition lors d'un futur cours sur cette theorie. On se limitera donc (comme les premiers explorateurs de ce

vaste domaine) a des groupes de permutations d'un ensemble niX. Denition 4.1.Ungroupe de permutationsdeXest un ensembleGSXde permutations deXtel que : |idX2G |8f;g2G gf2G; |8g2G g12G.

Le cardinaljGjdeGest appele l'ordrede ce groupe.

Unsous-groupedeGest un groupe de permutations deXinclus dansG. L'orbited'un elementx2X\pour l'action deGsurX" (c.-a-d. : relativement aG) est l'ensemble

Gx:=G(x) =fg(x)jg2Gg X:

Lestabilisateurdexest le sous-groupe deGconstitue des permutations qui xentx: G x:=fg2Gjg(x) =xg G: Remarque 4.2.L'ensembleSXlui-m^eme est le \plus gros" groupe de permutations deXet le singletonfidXg est le \plus petit" (on les appelle les \sous-groupes triviaux" deSX). Dans toute la suite, on suppose queGest un groupe de permutations d'un ensemble niX. Exemple 4.3.Les groupes de permutations deX=f1;2;3g, c.-a-d. les sous-groupes du \groupe symetrique

d'indice3" (S3), sont (outre les deux sous-groupes triviaux) : le \groupe alterne"A3, constitue de l'identite et

des deux permutations circulaires(123)et(123)1= (321)et, pour chacune des trois transpositions= (12),

(13)ou(23), le groupefidX;g. Le groupeS3(d'ordre3! = 6) a donc un sous-groupe d'ordre 6, un d'ordre 3,

trois d'ordre 2 et un d'ordre 1. On remarque que les ordres des sous-groupes sont tous des diviseurs de l'ordre

du groupe. C'est un fait general (theoreme de Lagrange) qui ne nous sera utile que dans le cas ou le sous-groupe

considere est un stabilisateur : Theoreme 4.4. Formule des classes.Pour toutx2X, l'ordre du stabilisateurGxdivise l'ordre du groupe G, et le quotient de ces deux ordres est le cardinal de l'orbiteGx: jGxj=jGjjGxj: Preuve :Considerons la relation d'equivalenceRsurGassociee a la surjectionG!Gx; g7!g(x). Calculons la classe d'equivalencegd'une permutationg2G: f2g,fRg,f(x) =g(x),g1f(x) =x,g1f2Gx, 9h2Gxf=gh:

L'applicationh7!ghrealise donc une surjection deGxdansg. Cette application etant par ailleurs injective

(cargest simpliable a gauche), on en deduit quejgj=jGxj. Ainsi, toutes les classes ont m^eme cardinal (l'ordre

deGx) donc (lemme des bergers) jGj=jG=Rj jGxj: 7 Or par denition deR, la surjectionG!Gx; g7!g(x) passe au quotient et donne une bijectionG=R !

Gx;g7!g(x), doncjG=Rj=jGxj. On peut conclure :

jGj=jGxj jGxj: Exemple 4.5.PourX=f1;2;3;4getG=fg2S4jg(4) = 4g(d'ordre6, commeS3),G1=fidX;(23)get

G1 =f1;2;3g.

Remarque 4.6.On deduit de la formule des classes que si deux points sont dans une m^eme orbite!, alors leurs

stabilisateurs ont m^eme ordre :jGj=j!j. En regardant les choses d'un peu plus pres, on peut en fait expliciter

une bijection tres naturelle entreGxetGg(x)(exercice ...).

Theoreme 4.7. Formule \de Burnside".Notons

P(X)l'ensemble des orbites et pour toute permutation g2G,Fix(g)l'ensemble despoints xesdeg:

Fix(g) =fx2Xjg(x) =xg X:

Alors, lenombre d'orbitesest :

j j=1jGjX g2GjFix(g)j:

Remarque 4.8.En particulier si l'action deGsurXest \transitive", c'est-a-dire si pour tout couple de points

x;y2X, il existe une permutationg2Gtelle quey=g(x), alorsP g2GjFix(g)j=jGj(cf. exercices 2 et 14).

Preuve :En utilisant le fait que les orbites forment une partition deX(ce sont les classes d'equivalence de \x

est en relation avecysi l'on peut passer de l'un a l'autre en appliquant une permutation appartenant aG"),

puis la formule des classes, on obtient :X g2GjFix(g)j=jf(g;x)2GXjgx=xgj X x2XjGxjquotesdbs_dbs33.pdfusesText_39

[PDF] probabilité combinaison exercices corrigés

[PDF] dénombrement exercices corrigés mpsi

[PDF] denombrement math premiere

[PDF] exercices dénombrement première pdf

[PDF] probabilité dénombrement cours

[PDF] exercices dénombrement mpsi

[PDF] formule dénombrement microbiologique

[PDF] p uplet

[PDF] p liste arrangement combinaison

[PDF] n-uplet definition

[PDF] formule arrangement

[PDF] p liste exercice

[PDF] arrangement combinaison permutation

[PDF] m=m/na

[PDF] que veut dire ci après dénommé