Université de Rouen L1 M I EEA

De
Publié par

Niveau: Supérieur, Licence, Bac+1
Université de Rouen L1 M.I.EEA 2011–2012 Mathématiques discrètes Formules d'inclusion-exclusion Je présente ici une correction détaillée de l'Exercice 5 de la Feuille d'exercices 1, en reprenant le problème de manière plus générale. 1. RAPPELS DE COURS Tout commence en effet avec le principe d'addition donné en cours : Proposition 1 (Principe d'addition). Soit A et B deux ensembles finis et disjoints. Alors Card(A?B)=Card(A)+Card(B) . En cours, vous avez ensuite généralisé ce résultat au cas de deux ensembles non disjoints, obtenant un premier principe d'inclusion-exclusion pour la réunion de deux ensembles quelconques : Corollaire 1 (Principe d'inclusion-exclusion pour deux ensembles). Soit A et B deux ensembles finis (pas forcément disjoints). Alors Card(A?B)=Card(A)+Card(B)?Card(A?B) . Démonstration. On commence par remarquer que A?B est la réunion disjointe de A et de B \ A, donc par le principe d'addition Card(A?B)=Card(A)+Card(B \ A) . Par ailleurs, l'ensemble B peut lui s'écrire comme réunion disjointe de A ?B et B \ A, donc on a aussi, toujours grâce au principe d'addition, Card(B)=Card(A?B)+Card(B \ A) .

  • propriété d'hérédité de l'hypothèse

  • card

  • zone verte

  • hypothèse de récurrence

  • ai2 ?·· ·?

  • diagramme de venn

  • inclusion

  • ai1 ?


Publié le : mercredi 30 mai 2012
Lecture(s) : 41
Source : univ-rouen.fr
Nombre de pages : 5
Voir plus Voir moins
Universit de Rouen L1 M.I.EEA
Formules d’inclusion-exclusion
2011–2012 Mathmatiques discrtes
Je prsente ici une correction dtaille de l’Exercice 5 de la Feuille d’exercices 1, en reprenant le problme de manire plus gnrale.
1. RAPPELS DE COURS Tout commence en effet avec le principe d’addition donn en cours : Proposition 1(Principe d’addition).Soit A et B deux ensembles finis etdisjoints. Alors Card(AB)=Card(A)+Card(B) . En cours, vous avez ensuite gnralis ce rsultat au cas de deux ensembles non disjoints, obtenant un premier principe d’inclusion-exclusion pour la runion de deux ensembles quelconques : Corollaire 1(Principe d’inclusion-exclusion pour deux ensembles).Soit A et B deux ensembles finis (pas forcÉment disjoints). Alors Card(AB)=Card(A)+Card(B)Card(AB) . DÉmonstration.On commence par remarquer queABest la runion disjointe deA et deB\A, donc par le principe d’addition Card(AB)=Card(A)+Card(B\A) . Par ailleurs, l’ensembleBpeut lui s’crire comme runion disjointe deABetB\A, donc on a aussi, toujours gráce au principe d’addition, Card(B)=Card(AB)+Card(B\A) . On obtient alors la formule souhaite en liminant Card(B\A) dans les deux galits prcdentes.« DÉmonstration graphique » du Corollaire1À l’aide d’un diagramme de Venn.La Figu-re1est une reprsentation classique des deux ensemblesAetBsous la forme d’un diagramme de Venn (appel aussi communment « diagramme en patates »).
A
B
FIGURE1. Lesdeux ensemblesAetBet leur intersection (en rouge)
Cette figure permet de visualiser qu’en calculant Card(A)+Card(B), on compte bien tous les lments deAet tous les lments deB, mais on compte deux fois les lments deAB, d’oÙ la ncessit de soustraire Card(AB) pour compter chaque lment de
1
13 fvrier 2012 – Jean-Baptiste Bardet – Universit de Rouen
FORMULES DINCLUSION-EXCLUSION
2
ABune et une seule fois. Si on ne peut pas considrer que ce soit une dmonstration parfaitement rigoureuse, cette heuristique permet de bien comprendre ce qui se passe.
2. CORRIGÈ DE L’EXERCICE5 On peut ensuite gnraliser cette formule À trois ensembles : Corollaire 2(Principe d’inclusion-exclusion pour trois ensembles - Exercice 5. (a)). Soit A, B etC troisensembles finis. Alors Card(ABC)=Card(A)+Card(B)+Card(C) Card(AB)Card(AC)Card(BC)+Card(ABC) . DÉmonstration.Cette formule s’obtient aisment À partir du Corollaire1. En effet ¡ ¢ Card(ABC)=Card (AB)C ¡ ¢ =Card(AB)+Card(C)CardAB)C ¡ ¢ =Card(A)+Card(B)Card(AB)+Card(C)Card (AC)(BC) =Card(A)+Card(B)+Card(C)Card(AB)Card(AC) ¡ ¢ Card(BC)+Card (AC)(BC) =Card(A)+Card(B)+Card(C)Card(AB)Card(AC) Card(BC)+Card(ABC) « DÉmonstration graphique » du Corollaire2À l’aide d’un diagramme de Venn.Reprsentons les trois ensembles et leurs intersections :
A
B
C
FIGUREtrois ensembles2. LesA,BetCet leurs intersections
Dans ce cas, lorsque nous calculons la somme Card(A)+Card(B)+Card(C), nous comptons une fois les lments qui sont dans un seul des trois ensembles (zones en blanc), deux fois ceux qui sont exactement dans deux ensembles (zones en rouge) et trois fois ceux qui sont dans l’intersection des trois ensembles (ABC, en vert). Pour ne plus compter en double les intersections deux-À-deux, nous allons soustraire les cardinaux de celles-ci, obtenant
Card(A)+Card(B)+Card(C)Card(AB)Card(AC)Card(BC) .
13 fvrier 2012 – Jean-Baptiste Bardet – Universit de Rouen
FORMULES DINCLUSION-EXCLUSION
3
Dans cette formule, nous comptons bien exactement une fois les lments des zones blanches et rouges. En revanche, la zone verte a t compte trois fois en positif, puis trois fois en ngatif, il faut donc la rajouter une fois, d’oÙ la formule finale.Pour un nombre arbitraire d’ensembles, on peut obtenir les bornes suivantes, tou-jours À partir du Corollaire1: Corollaire 3(Exercice 5. (b)).Soit nNet A1,A2, . . . ,Andes ensembles finis. Alors à ! n nn X X¡ ¢[ X Card(Ai)CardAiAjCardAiCard(Ai) . i=1 1i<jn i=1i=1 DÉmonstration.Nous allons dmontrer ce rsultat par rcurrence sur le nombren d’ensembles. Ècrivons prcisment l’hypothse de rcurrence au rangn(mme si ce n’est rien d’autre que l’nonc...) : HypothÈse de rÉcurrence au rang n.SiA1,A2, . . . ,Ansontnensembles finis, alors à ! n nn X X¡ ¢[ X Card(Ai)CardAiAjCardAiCard(Ai) . i=1 1i<jn i=1i=1 Pour dmontrer la validit de cette hypothse pour toutnN, il faut vrifier qu’elle est valide pourn=1 (initier la rcurrence), puis vrifier que si elle est valide pour un rang donnn, elle est encore valide au rangn+1 (proprit d’hrdit). Initialisation de la rÉcurrence, pour n=1.Sin=1, la somme sur 1i<jnest vide, car on ne peut pas trouver deux entiers distincts entre 1 et 1. Par convention, on dit alors que cette somme vaut 0. L’hypothse de rcurrence au rangn=1 se rcrit donc : siA1est un ensemble fini, alors Card(A1)Card(A1)Card(A1) , ce qui est trivialement vrai. L’hypothse de rcurrence est donc valide pourn=1. PropriÉtÉ d’hÉrÉditÉ de l’hypothÈse.On suppose dsormais que l’hypothse est va-lide À un rangnarbitraire. On veut vrifier qu’elle est encore vraie au rangn+1, soit doncn+1 ensembles finisA1,A2, . . . ,An,An+1. On peut utiliser le principe d’inclusion-exclusion pour les deux ensembles1inAietAn+1: à !Ãà !! n+1n [ [ CardAi=CardAiAn+1 i=1i=1 à !Ãà !! n n [ [ =CardAi+Card(An+1)CardAiAn+1 i=1i=1 à !à ! n n [ [ (1)=CardAi+Card(An+1)Card (AiAn+1) . i=1i=1 Par hypothse de rcurrence au rangn, on sait que à ! n n [ X CardAiCard(Ai) , i=1i=1 donc aussi à ! n+1n n+1 [ XX CardAiCard(Ai)+Card(An+1)=Card(Ai) i=1i=1i=1
13 fvrier 2012 – Jean-Baptiste Bardet – Universit de Rouen
FORMULES DINCLUSION-EXCLUSION
4
(en utilisant seulement le fait que le dernier terme de (1) est ngatif). Pour l’autre ingalit, on utilise deux fois l’hypothse de rcurrence au rangn, en appliquant la minoration auxnensemblesA1,A2, . . . ,Anet la majoration auxnen-semblesA1An+1,A2An+1, . . . ,AnAn+1. On obtient donc : à ! n n [ XX ¡¢ CardAiCard(Ai)CardAiAj i=1i=1 1i<jn à ! n n [ X Card (AiAn+1)Card(AiAn+1) . i=1i=1 En insrant ces deux formules dans l’Èquation (1), on a : à ! n+1n n [ XX ¡¢ X CardAiCard(Ai)CardAiAj+Card(An+1)Card(AiAn+1) i=1i=1 1i<jn i=1 n+1n X X¡ ¢X =Card(Ai)CardAiAjCard(AiAn+1) i=1 1i<jn i=1 n+1 X X¡ ¢ =Card(Ai)CardAiAj, i=1 1i<jn+1 P ¡¢ n car le termeCard(AiAn+1) correspond bien À la somme des CardAiAjpour i=1 1i<j=n+1.
3. BONUS:POUR ALLER PLUS LOIN On peut en fait gnraliser tout ce qui a t fait prcdemment pour obtenir une formule gnrale s’appliquant À un nombre fini arbitraire d’ensembles. ThÉorÈme 1(Formule d’inclusion-exclusion, ou formule du crible).Soit nNet A1, A2, . . . ,Andes ensembles finis. Alors à ! n n [ XX CardAi=Card(Ai)Card(AiAj) i=1i=1 1i<jn à ! n X \ n+1 +Card(AiAjAk)− ∙ ∙ ∙ +(1) CardAi, 1i<j<kn i=1 ou bien, sous forme plus synthÉtique, à ! "# n n [ XX ¡¢ l+1 CardA=(1) CardAA∩ ∙ ∙ ∙ ∩A i i1i2il. i=1l=1 1i1<i2<∙∙∙<iln DÉmonstration.Cette formule gnrale se dmontre elle aussi par rcurrence sur le nombrend’ensembles. La formule tant elle-mme relativement complique, les cal-culs deviennent un peu plus difficiles À crire... Pour un seul ensemble (n=1), il n’y a que la premire somme dans le second mem-bre, et elle se rduit au terme Card(A1), donc l’galit est de nouveau triviale. Supposons que la formule est vraie À un rangnarbitraire, et considronsn+1 en-sembles finisA1,A2, . . . ,An,An+1. On utilise de nouveau l’Èquation (1), puis on ap-plique l’hypothse de rcurrence, qui est cette fois une galit, aux deux termes qui
13 fvrier 2012 – Jean-Baptiste Bardet – Universit de Rouen
FORMULES DINCLUSION-EXCLUSION
5
sont des runions denensembles, obtenant : à ! "# n n [ XX ¡¢ l+1 A=(1) iA∩ ∙ ∙ ∙ ∩Ail Card CardAi1i2 i=1l=1 1i<i<∙∙∙<in 1 2l à !" # n n [ XX ¡¢ l+1 Card (AA)=(1)A∩ ∙ ∙ ∙ ∩AA i n+1Cardi1Ai2iln+1 i=1 l=1 1i1<i2<∙∙∙<iln En remplaÇant ces termes dans (1), on obtient donc à !" # n+1n [ XX ¡¢ l+1 CardA=(1) CardA∩ ∩A+Card(A) i i1Ai2∙ ∙ ∙ ∩iln+1 i=1 l=1 1i1<i2<∙∙∙<iln " # n X X¡ ¢ l+1 (1) CardAiAi∩ ∙ ∙ ∙ ∩AiAn+1 1 2l l=1 1i1<i2<∙∙∙<iln " # n X X¡ ¢ l+1 =(1) CardAA∙ ∩A+ i1i2∩ ∙ ∙ilCard(An+1) l=1 1i1<i2<∙∙∙<in l   n+1 X X¡ ¢ l+1   +(1) CardAiAi∩ ∙ ∙ ∙ ∩Ai   1 2l l=2 1i1<i2<∙∙∙<il1n i=n+1 l " # n+1n+1 X XX ¡¢ l+1 =Card(Ai)+(1) CardAiAi∩ ∙ ∙ ∙ ∩Ai. 1 2l i=1l=2 1i1<i2<∙∙∙<in+1 l Et c’est exactement l’expression souhaite.
13 fvrier 2012 – Jean-Baptiste Bardet – Universit de Rouen
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.