[PDF] Abrégé dAnalyse combinatoire

View - Download Abrégé dAnalyse combinatoire

Previous PDF

Next PDF

Abrege d'Analyse combinatoire

Jean Vaillant, septembre 2012

L'analyse combinatoire (ou denombrement) consiste a determiner le cardinal d'un ensemble donne, autrement dit a compter les elements appartenant a cet ensemble. Sous l'hypothese d'equiprobabilite, elle nous permet de determiner la probabilite d'un evenementAgr^ace a la formule : P(A) =Nombre de cas favorables a ANombre total de cas possibles

1 Nombre de parties d'un ensemble anelements

L'ensemble des sous-ensembles (ou parties) d'un ensemble de referenceEni est noteP(E) et verie :

SiCard(E) =n;alorsCard(P(E)) = 2n:

Bien-s^ur, l'ensemble vide;est un element deP(E) donc le nombre de parties non vides deEest 2n1.

2 Permutations sans repetition

Le nombre de permutations denelements, c'est-a-dire de facons d'ordonner ces nelements, est egal an! (lire factoriellen). n! =n(n1):::321:Par convention, 0! = 1:

3p-arrangements

Unp-arrangement d'un ensemble anelements est une suite ordonnee dep elements sans repetition. Le nombre dep-arrangements d'un ensemble an elements (pn) s'ecritApn(lireanp) et vaut: A pn=n(n1):::(np+ 1) =n!(np)!: 1

4 Combinaisons sans repetition

Une combinaison depelements pris parminest un sous-ensemble depelements pris dans un ensemble anelements. Le nombre de combinaisons sans repetition depelements dans un ensemble anelements s'ecritCpn(lirecnp) etaussin p et vaut : C pn=n p =Apnp!=n!p!(np)!=n(n1):::(np+ 1)k(p1):::21: Remarque : La derniere expression peut permettre un calcul rapide deCpn. Elle comporteptermes au numerateur etptermes au denominateur. Pour tout entier naturel non nuln, on a :C0n= 1; C1n=n; Cn1n=n; Cnn= 1. Pour tout couple d'entiers naturels (n;p) avecpn, on a : C pn=Cnpn; Cpn=Cp1 n1+Cp n1:

5p-listes

Unep-liste d'un ensemble anelements est une suite ordonnee depde cesn elements, certains eventuellement repetes. Le nombre dep-listes d'un ensemble anest :np. Remarque : C'est le nombre d'applications d'un ensemble apelements dans un ensemble anelements.

6 Permutations avec indiscernabilite intra categorie

Une permutation peut ordonnernelements appartenant akcategories ex- clusives sans distinguer ceux qui appartiennent a la m^eme categorie. Soient n

1; n2; :::; nkles cardinaux deskcategories (n1+n2+:::+nk=n). Le

nombre de telles permutations denelements repartis par categories d'elements indiscernables est : n!n

1!n2!:::nk!:

7 Combinaisons avec repetitions

Une combinaison avec repetitions dekelements choisis parmin, est une liste non ordonnee, avec repetitions eventuelles des elements. Le nombre de combinaisons avec repetition est : C n1

Remarque : Ici, on peut avoirk > n.

2

8 Situations usuelles

Les tableaux ci-dessous precisent quelques situations classiques en analyse com- binatoire.

1) Tirages dekelements parminTIRAGESordonnesnon ordonnes

sans remiseA knC knavec remisen kC n1 n+k12) Rangements dekobjets dansncasesOBJETSdiscernablesindiscernables au plus un objet dans une caseA knC kneventuellement plusieurs objets dans une casen kC n1 n+k13) Rangements denobjets dansncasesOBJETSdiscernablesindiscernables au plus un objet dans une casen!1

4) Rangements denobjets enkcategories a l'interieur desquelles ils sont

indiscernablesn!n

1!n2!:::nk!;avecn1+n2+:::+nk=n; nietant l'eectif de la categorie i3

9 Illustrations

I) Soit l'ensemble a 3 elementsE=fa;b;cg. On considere des suites a 2 elements.

1) Nombre d'arrangements sans repetition :A23= 6abacbabccacb

2) Nombre d'arrangements avec repetitions : 3

2= 9aaabacbabbbccacbcc

3) Nombre de combinaisons sans repetition :C23= 3fa,bgfa,cgfb,cg4) Nombre de combinaisons avec repetitions :C313+21=C24= 6(a,a)fa,bgfa,cg(b,b)fb,cg(c,c)

5) Nombre de permutations sans repetition : 3! = 6

abcacbbacbcacabcba II) Soit un ensembleEa 2 categories avec 3 elements dans la categorieaet 2 elements dans la categorieb. Au sein des categories, on considere que les elements sont indiscernables. On peut donc poser

E=fa1;a2;a3;b1;b2g

aveca1;a2;a3les elements de la categorieaetb1;b2ceux de la categorieb. En l'absence de distinction entre individus de m^eme categorie, le nombre de permutations n'est plus 5! = 120 mais bien5!3!2! = 10.aaabbaababaabbaabaabababaabbaabaaabbaabababaabbaaa 4quotesdbs_dbs22.pdfusesText_28

[PDF] Chapitre 1 Définition et méthodologie de l analyse comparative

[PDF] Bouchard, Durkheim et la méthode comparative positive - Érudit

[PDF] Analyse complexe - Département de mathématiques et de statistique

[PDF] Analyse complexe - Département de mathématiques et de statistique

[PDF] Analyse Complexe 2005-2006 - Exo7

[PDF] Analyse complexe Cours de L3, ENS Lyon, automne 2014

[PDF] Analyse Complexe S´eries de Fourier

[PDF] Analyse Complexe - Institut de Recherche Mathématique Avancée

[PDF] ANALYSE COMPLEXE 3M266

[PDF] L Analyse appliquée du comportement

[PDF] L Analyse appliquée du comportement

[PDF] l analyse concurrentielle - cloudfrontnet

[PDF] CONVAINCRE OU LA CONQUETE DE LA LIBERTE

[PDF] Analyse coût-bénéfices: guide méthodologique - Icsi

[PDF] L 'Analyse Coût-Bénéfices en 10 Questions - Inra