Cours de Combinatoire

Description

Cours de Combinatoire 5 novembre 20101 Rappels sur les ensembles Definitions Soit A et B deux ensembles. On note par :– |A| son cardinal, c.a.d. le nombre d'elements de A;– A∪B l’union de A et B, A∪B ={x :x∈A ou x∈B};– A∩B l’intersection de A et B, A∩B ={x :x∈A et x∈B};– A⊂B si pour tout x, si x∈A alors x∈B;– A\B la diff´erence de A et B, A\B ={x :x∈A et x∈/ B}– A×B l’ensemble des couples ordonn´es (x,y) tel que x∈A et y∈BA×B ={(x,y) :x∈A et y∈B}Propriet´es– |A|+|B| =|A∪B|+|A∩B|– |A×B| =|A||B|n n– |A |=|A| pour n∈N.2 Applications, fonction caract´eristique, arrangementsD´efinitions– Soit A et B deux ensembles. Une application φ de A dans B, not´ee par φ : A→ B, associea` chaque ´el´ement a∈A un unique ´el´ement de B, not´e φ(a). Formellement on peut voir uneapplication comme un sous-ensemble Φ de A×B tel que pour tout x∈A il existe un uniquey∈B tel que (x,y)∈ Φ.– Soit A⊂B, on d´efinit sa fonction caract´eristique f :B→{0,1} parA0 si a∈/ Af (a) =A 1 si a∈APropri´et´es|A|– L’ensemble des applications de A dans B a cardinalit´e |B| .Pour chaque ´el´ement de A on a|B| possibilit´es de choisir son image.n– L’ensemble des fonctions caract´eristiques sur l’ensemble B a cardinalit´e 2 ou` n =|B|.Pour chaque ´el´ement de B on a deux possibilit´es de choisir son image.Il y a une bijection directe entre l’ensemble P(B) des parties de B et l’ensemble des fonctionsncaract´eristiques sur B, donc|P(B)| = 2 , ou` n =|B|.D´efinitions– Une injection φ : A→ B ...

Informations

• Publié par: Saun
• Nombre de lectures: 27
• Langue: Français

Extrait

1

Cours de Combinatoire

5novembre2010

Rappels sur les ensembles

De´finitions SoitAetBdeux ensembles. On note par : –|A|son cardinal,c.a.d.emtndsede´’lee´rbmonelA; –A∪Bl’union deAetB,A∪B={x:x∈Aoux∈B}; –A∩Bl’intersection deAetB,A∩B={x:x∈Aetx∈B}; –A⊂Bsi pour toutx, six∈Aalorsx∈B; –A\Bdilaerff´ceendeAetB,A\B={x:x∈Aetx /∈B} –A×Beledcsuolpseroods(´ennl’ensembx, y) tel quex∈Aety∈B

A×B={(x, y) :x∈Aety∈B}

Propriete´s –|A|+|B|=|A∪B|+|A∩B| –|A×B|=|A| ∙ |B| n n –|A|=|A|pourn∈N.

2

Applications,fonctioncaracte´ristique,

arrangements

D´efinitions – SoitAetBdeux ensembles. Une applicationφdeAdansB,reeapon´tφ:A→B, associe `achaquee´le´menta∈Aununique´el´emnedteBn,toe´φ(a). Formellement on peut voir une application comme un sousensemble Φ deA×Btel que pour toutx∈Ail existe un unique y∈Btel que (x, y)∈Φ. – SoitA⊂Boitcracnstinnofaqutiet´aciser,ond´efif A :B→ {0,1}par  0 sia∈/ A f A (a) = 1 sia∈A

Propri´et´es |A| –L’ensemble des applications deAdansBanid´tilearac|B|. Pourchaque´el´ementdeAon a|B|.gemanisoopisrssiohcedse´tilibi n –stiq´eriractnscatcoifsnoeledesbmenL’esneelbmsseu’lruBital´ecaainrd2`oun=|B|. Pourchaque´el´ementdeBssibiliotnadeuxposiriosine´dsceohgema. Il y a une bijection directe entre l’ensembleP(B) des parties deBet l’ensemble des fonctions n caracte´ristiquessurB, donc|P(B)|=2,o`un=|B|. De´finitions – Une injectionφ:A→Bpalputenoitncitaqu’`elleque´achatneme´leedesBcorrespond au plusune´l´ementdeAay’ndsapdtnelitiAu.emtremmiga.enoltmaeˆmentsquieux´el´e – Un arrangement denimrapstneme´le´meeedno´neordlisttune,esne´em´ledstnitsistcnnu’d ensemble`amemtn.s´´eel

1

Proprie´t´es –L’ensemble des injections deAdansBtilae´acanidrm(m−1). . .(m−n+ 1)o`u|A|=net |B|=m. On amisirechoagedl’imimrepuermenee´´letdbissopdse´tiliA,m−1sspoilibe´ticedssiohri l’imagedudeuxi`eme,etc. n –Le nombreAd’arrangements denirmpatseneml´´emestm(m−1). . .(m−n+ 1). m De´finition – Une surjectionφ:A→Bqe’ua`hcitnoetllementdeaque´el´ppeacalieunstBcorrespond au moinsun´ele´mentdeA.deentsl´emes´eamisdsegbmesedelittdenl’trAuenemAparφest B. – Une bijectionφ:A→Best une application : – injective avec|A|=|B|, – ou encore injective et surjective. D´efinition – Une permutation d’un ensembleE`anendiol´em´eutsestnetcejibenEdaem.ˆiemluns Propri´ete´ –t´egal`aationsesepedtumroneLerbmn! = 1∙2∙3∙ ∙ ∙n. L’ensembledespermutationseste´gala`l’ensembledesinjectionsdeEdansE.

3

Double comptage et combinaisons

Principe du double comptage :e´le´selu’dstnemenmeˆenmdelembseedxuSioncompte manie`resdiff´erentesontrouvelemeˆmer´esultat. ` Exercice :pmiarnnmorbieelqu’unumain`aqualtnerresiuqsnegderembnolee,agrinuamA de fois est pair. Solution :Soitx i le nombre de fois que la personneiseamairrelqleuqa`ntenu’uyle nombre P totaldepoign´eesdemain.Pard´efinitionx i = 2y. Supposons que le nombre de gens qui serrent i la main un nombre impair de fois est impair. Alors la somme desx i correspondants est impaire. Comme lesx i ontpairsestantssotatelerl,samoemriapmietsepenteere´trˆeuta2e`alegy. Il y a doncunecontradictionetlasuppositionpr´ece´denteestfausse:lenombredegensquiserrentla main un nombre impair de fois est pair.

D´efinition – Une combinaison dekraimel´me´espntnest un sousensemble de cardinalkd’un ensemble   k n de cardinaln. On noteCou le nombre de combinaisons dektsenrmpa´eieml´n. n k   n Par convention = 0 sin <0,k <0 ouk > n. k Proprie´te´s   n n ! –Valeur du coefficiant binomial := . k k!(n−k)! k k Par double comptage des arrangements :k!C=A.     n n n n – = . k n−k       n n−1n−1 – = + . k k k−1

3.1Laformuledubinoˆme SoitAun anneau eta, b∈Atel queab=baetn∈N. On a : n   X n n n −k k (a+b) =a b . k k=0 On va le montrer combinatoirement et par induction.

2

  n n Preuve combinatoire.(slanDlove´eeddtnemepptiudorpua+be)onafa¸ocsnedafrbqieulr k n−nk k −k k termea b: en effet parmi lesnfacteurs (a+b), il faut choisirkfoisbpour obtenira b.

Preuve par induction 0 0 – Cas de base : (a+b) =C 0 P   n n n n−nk k +1 – Induction : On suppose que (a+b) =a b, on veut montrer que (a+b) = k=0 k P   n+1 n+1 n+1−k k a b. k=0 k n   X n n+1n n−k k (a+b) = (a+b)∙(a+b) = (a+b)a b k k=0 n   n   X X n n n+1−nk k −k k+1 =a b+a b k k k=0k=0 n   n+1   X X n n n+1−k k n+1−k k =a b+a b k k−1 k=0k=1 n    n+1   X X n n n+ 1 n+1−k k n+1−k k =a n+1 +b n+1 + +a b=a b . k k−1k k=1k=0

Onautilise´larelationdutriangledePascal:       n n n+ 1 + =. k k−1k

Exercices p    X n n−q q –CalculerS= (−1)pour0≤p≤n. q p−q q=0   p     X       n p n n n− p p q q n On remarque = . De sorte queS= (−1) = (1−1) = 0. q p−qq p p q q q=0 n p    X X n p n−p n−p+k p−k –CalculerS= (−1)t(1−3t). p k p=0 k=0 n   p   X X n p n−p n−pp k −k S= (−1)t t(1−3t) p k 1 p=0 k=0 n   X n n−np p 1 = (−t) (1−2t(1) = −3t). p p=0

3.2 Coefficients multinomiaux D´efinition   n Etantdonne´sn 1 +. . .+n k =n´efinestdiimlas,leitifspostieritonmtluicneocffienesed n 1 ,...,n k par   n n! =. n 1 , . . . , n k n 1 !n 2 !∙ ∙ ∙n k !

  n Remarquons que sin 1 +n 2 =nalors = n 1 ,n 2 binomiaux. Propri´ete´

3

    n n = , on retrouve les coefficients n 1 n 2