[PDF] Combinatoire Si l'arrangement est non-

View - Download Combinatoire

Previous PDF

Next PDF

ChapitreI

Combinatoire

Lacombinatoire(ou analysecombinatoire) estl'étudeet, plusenparticulier ,ledénom- brementsdesconfigurations d'unecollectionfinie d'objets.Par exemple, voici desquestions typiquesquipeuv entêtre resoluesàl'aidedelacombinatoire : -Quelestle nombrede partiesd'unensemble denélémentsayante xactementkélé- ments? -Quelestle nombredes combinaisonsde6 numérosde1 à49au Lotofrançais,a vec aumoins3 numérosg agnants? Onutiliserades résultatsde combinatoirede basepourla théoriedesprobabilités surles ensemblesfinis.

1.1.Rappelsde théoriedesensembles etdesf onctions

Nousconsideronsune approchenaïv eàla théoriedesensembles :ondiraqueunen- sembleestune collectiond'objetsque l'onappèlleélémentsdel'ensemble.Les ensembles serontnotésa vecles lettresmajusculesA,B,C...,exception faitedesensemblesdenombres naturels,entiersouréels.Sia,b,c...appartiennentàl'ensemble A,onnotera A={a,b,c...},ousimplement a,b,c2A.Onn'admet pasderépétition dansles éléments d'unensemble,par exemple lesensembles{1,1,2}et{1,2}coïncident. Onutiliserales notationsclassiquespour laréunionA[B,l'intersectionA\B,ladiffé- renceA\BetladifférencesymétriqueADB:=(A[B)\(A\B)(voirFigure1.1)dedeux en- semblesA,B.Par exemple,siA={1,2,3,4,5,6}etsiBestl'ensembledes nombresimpairs (B⇢),onaura A\B={1,3,5}etA\B={2,4,6}.Réunionet intersections'étendent à descollectionsinfinies d'ensembles. AB A[B AB A\B AB A\B AAB ADB FIGURE1.1.Réunion,inter section,différence etdifférencesymétriqued'ensembles Unepartieousous-ensembled'unensembleAestunensemble Bdontleséléments ap- partiennentàA(notéB⇢A).Deuxensembles A,Bsontégaux sietseulementsiA⇢Bet B⇢A(Aestunepartie deBetBestunepartie deA).Unensemble Acontenantunnombre finid'élémentsest ditfini,etle nombredeses éléments(son cardinal)estnotée |A|.SiAest unensemble,on appelleensembledesparties deAl'ensembleP(A)dontleséléments sont lespartiesde A.Par exemple

P({1,2,3})=

n /0,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} o

SiAestfini,|P(A)|=2

|A| (exercice).

Unefonctionf:A!Bestditeinjectivesif(a

1 )=f(a 2 )impliquea 1 =a 2 ,pourtout a 1 ,a 2

2Aetsurjectivesipourtout b2Bilexiste a2Atelquef(a)=b.Unefonction

injectiveetsurjectiveestdite bijective.SiAestBsontdesensembles finis, etf:A!Best 4 bijective,alors|A|=|B|.L'ensemble desfonctionsdeAàBestnotéB A ;siA,Bsontdes ensemblesfinis,alors |B A |=|B| |A| UnensembleAestditdénombrables'ilexiste B⇢etunefonction bijective f:A!B. Parexemple,tout ensemblefinissontdénombrables.SoitAunensemble,alors unecol- lectiondénombrableA 1 ,...,A n ...2P(A)departiesde Aestappéléeune partitionde AsiA i \A j =/0,pourtouti6=j,etA=[ i A i :=A 1 [A 2 [A n

···.Par exemple

{1,2,3},{4},{5,6,7}estunepartition (finie)de {1,2,3,4,5,6,7}. Lerésultatsui vant esttrèsimportantencombinatoireetserautilisédans laprobabilité surlesensembles finis.Ilpermet d'exprimer lecardinalde laréuniond'une collectionfinie d'ensembles,enfonction ducardinal decesensembles etdeleurs intersections. Théorème1(Principed'inclusion-exclusion) .SoientA 1 ,...,A n ensemblesfinis.Alor s |A 1 [A n n k=1 (1) k+1

1i

1 i k n |A i 1 \A i k

Leprinciped'inclusion-e xclusionpour npetit:

n=2:|A 1 [A 2 |=|A 1 |+|A 2 |A 1 \A 2 n=3:|A 1 [A 2 [A 3 |=|A 1 |+|A 2 |+|A 3 |A 1 \A 2 |A 1 \A 3 |A 2 \A 3 |+|A 1 \A 2 \A 3 Explicationpourle casn=3(eten generalpourtout n).Onv eutcalculer|A 1 [A 2 [A 3 etpourf aireçaon commenceàadditionnerlescardinaux |A 1 |+|A 2 |+|A 3 |.Enf aisantça, nousav onscompté2foischacunedesintersections2 à2,et troisfoisl'intersection 3à

3.Ensoustrayant lesintersections2 à2, onlesa donccomptésune foischacune,mais on

asoustrayé3 foisl'intersection 3à3, qu'ilfaut doncre-additionnerpour obtenirle bon résultat.

1.2.Dispositions

SoitUunensemblede cardinal|U|=n,onpeut penserpare xemple àl'ensembleU= {1,2,...,n}desnombresnaturels inférieursà n.Supposonsde devoir choisirkéléments parmilesnélémentsdeU. Onparlede dispositionsionest interessésàl' ordredesélémentschoisis. Nousfaisons unedistinctionen 2casdif férents:Dispositions sanseta vecrépétition.

1.2.1.Dispositionssans répétition

Nouschoisissonskéléméntssansrépétition(c'est-à-direqu'onne peutpaschoisir le mêmeélémentplusieurs fois)et enconsiderantl'arrangement ordonné(parex emple,les arrangements12 3et213sontdifférents). Lenombrede dispositionssansrépétition dekélémentsparmin(kn)est D n,k n! (nk)! =n·(n1)·(n2)···(nk+1). Danslaformule, lavaleur n!estappélée factorielleden;çacorresponds auproduitdes prémiersnnombresnaturels,et peutêtre définierécursiv ementcommesuit :

0!=1etn!=n·(n1)!.

5 Explication.Nousa vonsnchoixpourle prémierélément, maisseulementn1pourle deuxième(onne peutpas choisirle premierélément),n2pourle troisième,etc.pour k fois. Exemple2.Noussouhaitonss'habiller différemment pendantunesemaine, enévitantde choisirlamême couleurde chemisedansdeux joursdifférents. Nousav ons10chemises de couleursdifférentes disponibles.Ilyae xactementD 10,7 =10·9·8·7=5040dispositions possibles.? Danslelangua gedesensembles, unedispositionsansrépétitiondekélémentsd'unen- sembleU,|U|=n,estune fonctioninjectiv ed'un ensembleAdecardinalkversU,ce quicorrespondsà choisir,ouextrairekélémentsdeU.Lapropriété d'injectivité"pour tout a 1 6=a 2 dansA,f(a 1 )6=f(a 2 )"garantie lanon-répétition.

1.2.2.Dispositionsa vec répétition

Cettefois-ci,nous pouvons choisirkéléméntsavecrépétitionmaisenconsiderant encore ladisposition ordonnée.Remarquonsque dansce caskpeutêtresuperieur àn.Lenombre decesarrangements est D 0 n,k :=n k Explication.Nousa vonsnchoixpourle premier éléments,mêmechose pourledeuxième etpourtous lesautreséléments dela suite.Lasuite alongueurk,doncA n,k =n·n·n···n(k fois)=n k

Exemple3(Écritureen base

1 naveckchiffres).Combiendenombre deau pluskchiffres peut-onécrireen basen?Supposonspour simplicitéque n=2etk=3:nous nousintéres- sonsauxnombres quipeuvent s'écrireenbase 2(c-à-d.a vecsymboles0et 1)av ec3chif fres oumoins.Il ya exactement8 =2 3 =n k nombresayantcette propriété,et précisement:

0=0001=0012=0103=011

4=1005=1016=1107=111

Unedispositiona vec répétitioncorrespondsàunefonction(n'importequelle)d'unen- sembleAaveckélémentsàv aleursdansU.L'ensemble Acontientleskplacesdansl'arran- gementordonné.Du coupon retrouve|{f:A!U}|=|U A |=|U| |A| =n k

1.3.Combinaisons

Dansplusieurscas pratiques,nous sommesintéressésà dessuitesfinis d'objetssans spécifierunor dre ,eton parledansce casde combinaisons.Par exemplelesarrangements

15423et12345doivent êtreconsiderésla mêmecombinaisondespremierscinqnombres

naturels.

1.Écrireen basenuncertainnombre entierNsignifiedecomposerNensommede puissancesentières

successivesden:N=a t n t +a t1 n t1 +···+a 1 n+a 0 =a t a t1 ...a 0 .Par exempleenbase2, ona6=4+2=

1·2

2 +1·2 1 +0·2 0 =110.L'écritureestunique. 6

1.3.1.Combinaisonssans répétition

Sil'arrangementest non-ordonnéet sansrépétition,on parledecombinaison sansré- pétition.Lenombre decombinaisonssans répetitiondekélémentsparminélémentsd'un ensembleU(kn)est C n,k n k n! k!(nk)! Onextrait k=4foisune boulesansremise .Sinous nesommespas interessésàl'ordre des tirages,l'experience estequivalenteà celled'extraire ungroupede4boulesaumêmetemps. Lenombredes possiblesrésultats dutirageest lenombrede combinaisonsde4 éléménts parmi10,c'est-à-dire C 10,4 =210.? n=01 n=111 n=2121 n=31331 n=414641 n=515 101051 n=616 152015 61

FIGURE1.2.Triangle dePascal

Lenombre

n k estappélécoefficientbinomiale.Voici lespropriétésprincipalesdescoef- ficientsbinomiaux: n 0 n n =1pourtout n n k n nk (symétrie) n+1 k n k1 n k (TriangledePascal) Uneméthoderécursivepourcalculera vec lescoefficientsbinomiauxestsuggéréparla 2 (Figure 1.2).

Lecomportementsymétrique de

n k estmontréen Figure1.3 pourn=20.

1.3.2.Combinaisonsa vec répétition

Ondisposede nélémentsappartenantà unensembleU,eton souhaiteunarrangement de tailleknon-ordonné etavecrépétition,cequ'on appelleunecombina isona vecrépétition.

Lenombrede cescombinaisons est

C 0 n,k =C n+k1,k Explication.Toute combinaisondekélémentsav ecrépétitionàchoisirparminéléments a 1 ,...,a n donnéspeuts'écrire (sanspertede généralité)commesuit : a 1 ...a 1 |{z} k 1 fois ,a 2 ...a 2 |{z} k 2 fois ,...,a n ...a n |{z} k n fois

2.Leni veauest donnéparn,alorsque laprofonditédans chaqueniv eauest donnéepark:

n+1 k estdonné parlasomme descoefficients binomiauxà niveau netprofonditéketk1(enFigure 1.2,le10estlas omme de6et4). 7

05101520

0.0 0.5 1.0 1.5 2.0

·10

5

FIGURE1.3.Valeur sducoefficientbinomiale

20 k ,pourk=0,...,20. aveck 1 +···+k n =k.Celacorrespo ndàplacer kobjetsdansnboîtes,et,après, àappeler a i touslesobjets placédansla ièmeboîte.De manièreéqui valente,à placern1"cloisons" séparantskobjets: a 1 ...a 1 |{z} k 1 fois q 1 |{z} cloison a 2 ...a 2 |{z} k 2 fois q 2 |{z} cloison ...q n1 |{z} cloison a n ...a n |{z} k n fois Ducouple nombredecombinaisons avec répétitiondeséléments a 1 ,...,a n priskàkest lenombrede combinaisonsden1objetsparmi k+n1,c'est-à-direC n+k1,n1 C n+k1,k Exemple5(Nombrede monômesdede grék).Soitx=(x 1 ,...,x n )unvecteur denvariables, etsoitk2.Lenombre demonômesde degrékenxestdonnépar lenombrede combi- naisonsav ecrépétitionpriskàk,deséléments deU={x 1 ,...,x n }(combinaisonscarle produitdev ariablesétant commutatif,onnes'interessepasà l'ordre;a vecrépétition car unevariable peutapparaîtreavec puissance2).?

LapropriétéC

0 n,k =C 0 n,k1quotesdbs_dbs5.pdfusesText_9

[PDF] arrangement sans répétition exercices

[PDF] différence entre arrangement et combinaison

[PDF] arrangement avec répétition exercice corrigé

[PDF] arrangement combinaison permutation exercices corrigés

[PDF] methode arraylist java

[PDF] arraylist string java

[PDF] arraylist java example

[PDF] arraylist java open classroom

[PDF] exemple arraylist java

[PDF] créer une arraylist java

[PDF] constructeur arraylist java

[PDF] arraylist<int>

[PDF] droit d'arrestation article

[PDF] interpellation police a domicile

[PDF] arrestation enquête préliminaire