[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 =Xquotesdbs_dbs31.pdfusesText_37

[PDF] allèle rhésus positif

[PDF] td la productivité du travail corrigé

[PDF] exercice calcul productivité

[PDF] les facteurs de production et leur combinaison la productivité

[PDF] jeu de dames exercices de style pdf

[PDF] astuce jeux de dame

[PDF] livre de jeu de dames gratuit

[PDF] cours jeux de dames

[PDF] deplacement des pions au jeu de dames par les grands maitres

[PDF] jeu de dame stratégie

[PDF] exercice jeu de dames

[PDF] combinaison linéaire système

[PDF] combinaison linéaire divisibilité

[PDF] composition linéaire

[PDF] exercice combinaison linéaire