Mathématiques pour physiciens : TD n˚1 Probabilités - I 1 Formule
Mathématiques pour physiciens : TD n˚1. Probabilités - I. Amir Kashani-Poor & Sylvain Nascimbene. 1 Formule de Poincaré. On consid`ere deux événements A1 et A2
Crible de Poincaré et application aux calculs du nombre de
Crible de Poincaré et application aux calculs du nombre de dérangements Théorème (formule du crible de Poincaré) : Soit E E un ensemble fini
Formule du crible/Définition — Wikiversité
23 oct. 2021 La formule du crible est aussi connue sous le nom de formule de Poincaré. ... Formule du crible/Définition » n'a pu être restituée correctement ...
Note sur le théorème dit de Poincaré et ses généralisations dites de
Camille JORDAN comme professeur (en fonction) durant toute sa scolarité. Il n'est donc pas surprenant qu'il ait été informé par son auteur de la fameuse formule
Formule du crible de Poincaré : définition et explications
En combinatoire la formule du crible de Poincaré ou formule de Poincaré Soient A1
Chapitre 9 : Dénombrement
14 janv. 2014 La formule de Poincaré étant assez peu lisible voici ce que ça ... On se contentera de prouver la formule pour n = 3 en partant de la ...
Problème : formule de Poincaré et applications 1. La formule de
Une application concrète Au cours d'une soirée n personnes déposent dans un chapeau une carte portant leur nom (aucune personne ne portant le même nom
Corrigé du devoir 2 mai 2006
Exprimer B à l'aide des Aj. 5) Utiliser la formule de Poincaré pour calculer PN (B) et sa limite quand N tend vers l'infini. Correction . Cet exercice
Principe dinclusion-exclusion — Wikipédia
formule du crible de Poincaré formule de Poincaré
Démonstrations capes - Probabilités
Formule de Poincaré. Soit AB A
Chapitre 9 : Dénombrement
2014. jan. 14. (?1)k+1
Le théorème de probabilité de Poincaré généralisé au cas de
en n épreuves (v= 1 2
Caracteristiques DEuler-Poincare Fonctions Zeta Locales et
la formule pour les modifications analytiques (Theoreme (6.1)). (3.3.3.4) Des resultats concernant la conjecture (3.3.2) pour n = 3 sont.
Mathématiques pour physiciens : TD n?1 Probabilités - I 1 Formule
1 Formule de Poincaré. On consid`ere deux événements A1 et A2. En déduire la formule ... 3. Soient n ? N et A1...
Mathématiques pour physiciens : TD n?1 Probabilités - I 1 Formule
1 Formule de Poincaré. On consid`ere deux événements A1 et A2. En déduire la formule ... 3. Soient n ? N et A1...
Problème : formule de Poincaré et applications 1. La formule de
3. Une application concrète Au cours d'une soirée n personnes déposent dans un chapeau une carte portant leur nom (aucune personne ne portant le même
Corrigé du devoir 2 mai 2006
3) On fixe k entiers i1 < i2 < ··· < ik entre 1 et N. Dénombrer toutes les permu- n. ? j=1. Aj. 5) En appliquant la formule de Poincaré à l'union n.
On the local solution of the tangential Cauchy-Riemann equations
Annales de l'I. H. P. section C
General relativistic celestial mechanics of binary systems. II. The
Ann. Inst. Henri Poincaré. Vol. 44
General relativistic celestial mechanics of binary systems. II. The
Ann. Inst. Henri Poincaré. Vol. 44
[PDF] TD n?1 Probabilités - I 1 Formule de Poincaré - Physique ENS
Mathématiques pour physiciens : TD n?1 Probabilités - I Amir Kashani-Poor Sylvain Nascimbene 1 Formule de Poincaré On consid`ere deux événements A1 et
[PDF] Problème : formule de Poincaré et applications
(b) Démontrer la formule de Poincaré : Si n ? 2 pour toute suite finie (Ai)1?i?n d'éléments de A alors : p( n ? i=1 Ai) = n ? k=1 ((?1)k?1 ?
[PDF] Combinatoire et dénombrement - ENS Rennes
On va montrer ici la formule du crible de Poincaré Toute ou une partie de cette section peut constituer un développement 1 1 La formule Soit E un ensemble et
[PDF] Formule du crible (ou de Poincaré) - Free
n ? On a la formule dite du crible ou de Poincaré : Supposons l'égalité vérifiée à l'ordre n Montrons la à l'ordre 2 n ? 3) Soit ( ) 1 i i n
[PDF] Chapitre 5 Probabilités élémentaires
Pour calculer la probabilité d'une union on utilise la formule du crible de Poincaré Proposition 4 (Probabilité d'une union: formule du crible de Poincaré)
[PDF] Chapitre 9 : Dénombrement - Normale Sup
14 jan 2014 · On se contentera de prouver la formule pour n = 3 en partant de la proposition précédente : A?B ?C = (A ? B) ? C = A ? B + C?(A
[PDF] Problème : Formule de Poincaré et applications
Dans cette partie on fixe E un ensemble fini et n un entier naturel non nul 1 Donner la formule de Poincaré pour deux sous-ensembles de E 2 Soit I une
[PDF] Td2Capes10pdf
La formule de Poincaré vue en cours a été démontrée par récurrence a) Vérifiez directement cette formule dans le cas n = 3 en développant le produit
[PDF] Dénombrement
3 Propriétés élémentaires des probabilités Formule de Poincaré 4 Probabilité conditionnelle formule des probabiliés totales formule de Bayes
[PDF] DM 21 : autour de la formule du crible
3) Somme des évaluations d'une fonction caractéristique : a) Soit A ? E : que vaut x?E ?A(x) b) Soit E un ensemble de cardinal n Déduire de la formule
Chapitre 9 : Dénombrement
PTSI B Lycée Eiffel
14 janvier 2014
Toute chose est nombre.
Pythagore.
Il y a trois sortes de mathématiciens :
ceux qui savent compter et ceux qui ne savent pas compter.Introduction
La combinatoire, science du dénombrement, sert comme son nom l"indique à compter. Il ne s"agit bien entendu pas de revenir au stade du CP et d"apprendre à compter sur ses doigts, maisbien de définir des objets et notations mathématiques permettant de compter le nombre d"éléments
d"ensembles bien trop gros et compliqués pour être dénombrés à la main. Le dénombrement n"a
pas en soi énormément d"intérêt, mais trouvera toute son utilité ensuite en probabilités : dans le
cadre des probabilités finies, la probabilité d"un évènement se calcule en divisant le nombre de cas
favorables par le nombre total de cas possibles, ce qui suppose qu"on sache calculer les nombres de cas en question.Objectifs du chapitre :
être capable d"analyser correctement un énoncé pour choisir le bon type d"outil de dénombre-
ment, et mener un raisonnement combinatoire clair et rigoureux manipuler sans hésitation les coefficients binomiauxQuelques exemples de problèmes faisant intervenir les objets que nous allons étudier dans ce cours :
Un tirage de Loto consiste à tirer sept boules dans une urne en contenant49(numérotées de1à49). Combien y a-t-il de tirages possibles?
Il y a49élèves dans la classe. Quelle est la probabilité qu"il y en ait (au moins) deux parmi
eux qui soient nés le même jour de l"année?On veut répartir les48élèves d"une classe en16trinômes de colles. Combien y a-t-il de répar-
titions possibles (l"ordre des trinômes ainsi que l"ordre des élèves au sein de chaque trinôme
n"étant pas important)? 11 Cardinaux d"ensembles finis
Définition 1.Un ensembleEestfinis"il est en bijection avec l"ensemblef1;2;:::;ng, pour un entier natureln. Cet entiernest alors unique. Il est appelécardinalde l"ensembleE, et on le note card(E), oujEj, ou encore]E.Remarque1.Cela correspond bien à la notion intuitive d"ensemble dont on peut compter les éléments.
En effet, une bijection deEversf1;:::;ngest simplement une façon d"étiquetter les éléments deE
avec les numéros1,2, ...,n. Proposition 1.SoitEun ensemble fini etFun sous-ensmble deE, alorsFest un ensemble fini, etjFj6jEj, avec égalité si et seulement siE=F.Démonstration.Cette propriété, comme souvent en ce qui concerne les ensembles finis, est assez
évidente d"un point de vue intuitif, mais pas si simple à démontrer correctement. Nous nous en
tiendrons au point de vue intuitif.Proposition 2.SoientEetFdeux ensembles finis. SiEetFsont en bijection l"un avec l"autre,
ils ont même cardinal. Démonstration.Il existe par hypothèse une bijectionfdeEversF. De plus,Fétant fini, notonsn son cardinal, il existe alors une bijectiongdeFdansf1;:::;ng. L"applicationgf:E! f1;:::;ng est une composée d"applications bijectives, donc est bijective, ce qui prouve queEest de cardinal n.Proposition 3.SoientAetBdeux sous-ensembles d"un même ensemble finiE. AlorsjA[Bj= jAj+jBj jA\Bj. Démonstration.Commençons par constater que dans le cas où les deux ensemblesAetBsont disjoints, on ajA[Bj=jAj+jBj. Vous voulez une démonstration? Soitfune bijection deAdans f1;:::;ngetgune bijection deBdansf1;:::;pg,netpétant les cardinaux respectifs deAet deB. On peut alors construire une bijectionhdeA[Bversf1;:::;n+pgen posant8x2A,h(x) =f(x)et8x2B,h(x) =g(x)+p(intuitivement, cela revient à garder pour les éléments deAla numérotation
donnée par l"applicationf, et à décaler pour les éléments deBla numérotation donnée parg, de
façon à ne pas utiliser deux fois les mêmes numéros). Une fois ce fait admis, constatons queA[B
est l"union disjointe des trois ensemblesAnB,BnAetA\B. On a donc, en utilisant le résultat que nous venons de démontrer,jA[Bj=jAnBj+jBnAj+jA\Bj. Or,Aétant union disjointe deAnB et deA\B, on a égalementjAj=jAnBj+jA\Bj, ou encorejAnBj=jAj jA\Bj. De même, jBnAj=jBj jA\Bj, donc on obtientjA[Bj=jAj jA\Bj+jBj jA\Bj+jA\Bj, ce qui donne bien la formule annoncée.Théorème 1.Formule du crible de Poincaré. SoientA1,A2, ...,Andes sous-ensembles finis d"un même ensembleE, alors j n[i=1Aij=nX k=1X16i1< Proposition 4.La formule de Poincaré étant assez peu lisible, voici ce que ça donne pourn= 3et
n= 4: jA[B[Cj=jAj+jBj+jCj jA\Bj jA\Cj jB\Cj+jA\B\Cj jA[B[C[Dj=jAj+jBj+jCj+jDj jA\Bj jA\Cj jA\Dj jB\Cj jB\Dj jC\ Dj+jA\B\Cj+jA\B\Dj+jA\C\Dj+jB\C\Dj jA\B\C\Dj
2 Démonstration.La preuve de la formule générale, assez technique, se fait par récurrence. On se
contentera de prouver la formule pourn= 3en partant de la proposition précédente :jA[B[Cj= j(A[B)[Cj=jA[Bj+jCj j(A[B)\Cj=jAj+jBj jA\Bj+jCj j(A\C)[(B\C)j= jAj+jBj jA\Bj+jCj jA\Cj jA\Bj+jA\C\B\Cj, ce qui donne bien la formule annoncée.Exemple :Dans un lycée de300élèves,152savent jouer au poker,83au tarot et51au bridge. De
plus,24savent jouer à la fois au poker et au tarot,14au poker et au bridge, et8au tarot et au bridge. Enfin,3élèves maitrisent les trois jeux de cartes. Le nombre d"élèves jouant aux cartes est
alors de152 + 83 + 5124148 + 3 = 237. Proposition 5.SoitAun sous-ensemble fini d"un ensemble finiE, alorsjAj=jEj jAj. Démonstration.C"est une conséquence de la formule pour une union :Eest union disjointe deAet deA, doncjEj=jAj+jAj.Proposition 6.SoientEetFdeux ensembles finis, alorsEFest fini, etjEFj=jEj jFj. Démonstration.Pas de preuve rigoureuse pour celui-ci, simplement une idée de la façon dont ça
marche. Soitnle cardinal deE, ete1;e2;:::;enses éléments,ple cardinal deFetf1;:::;fpses éléments. on peut placer les éléments deEFdans un tableau de la façon suivante :e 1e 2:::e nf 1(e1;f1)(e2;f1):::(en;f1).
..f p(e1;fp)(e2;fp):::(en;fp)Il y biennpéléments dans le tableau, donc dansEF.2 Listes, arrangements et combinaisons
Définition 2.SoitEun ensemble fini de cardinaln, etp2N. Unep-listed"éléments deE, ou p-uplet d"éléments deE, est simplement un élément deEp. Remarque2.On peut très bien avoir plusieurs fois le même élément dans unep-liste. Par ailleurs,
l"ordre des éléments de lap-liste est important. Proposition 7.Le nombre dep-listes dans un ensemble de cardinalnvautnp. Démonstration.C"est une conséquence de la formule de cardinal du produit vue un peu plus haut :
commejEFj=jEj jFj, on ajEpj=jEjp, ce qui prouve bien la propriété.Exemple :On tire dans une urne contenant10boules numérotées de1à10quatre boules succes-
sivement avec remise. Le nombre de tirages possibles est de104= 10 000(il y a répétition possible
à cause des remises, et l"ordre est important). Remarque3.Le nombre dep-listes d"un ensemble ànéléments est aussi le nombre d"applications de l"ensemblef1;:::;pgvers cet ensemble. En effet, se donner une telle applicationfrevient à se donner les valeurs des imagesf(1),f(2), ...,f(p), c"est-à-dire à se donner une liste depéléments
deE. Définition 3.SoitEun ensemble ànéléments etp2N, on appellearrangementdepéléments deEunep-liste d"éléments distincts deE. Remarque4.L"ordre des éléments est toujours important, par contre on ne peut plus avoir de répétition d"élément dans un arrangement. 3 Définition 4.Soientnetpdeux entiers tels quep6n, on noteApn=n!(np)!=n(n1)(n 2):::(np+ 1).
Proposition 8.Le nombre d"arrangements depéléments dans un ensemble ànéléments vautApn.
Démonstration.Contentons-nous de l"idée intuitive : lorsqu"on construit un arrangement, on an choix pour le premier élément,n1pour le deuxième, ...,np+ 1pour lepème, soit au total n(n1)(np+ 1) =n(n1):::(np+ 1)(np):::21n(n1):::21=n!(np)!.Exemple :On reprend la même urne que précédemment, mais on tire les quatre boules successive-
ment sans remise. Le nombre de tirages possibles est désormais deA410=10!6! = 10987 = 5 040. Remarque5.Le nombre d"arrangements depéléments dans un ensemble ànéléments est également
le nombre d"applications injectives def1;:::;pgdansE. Définition 5.Un arrangement denéléments dans un ensemble ànéléments est aussi appelé
permutation. Il y a doncn!permutations dans un ensemble ànéléments. Exemple :Le nombre d"anagrammes d"un mot peut se calculer à l"aide de permutations. Il faut simplement diviser le nombre total du permutations du mot park!chaque fois qu"une même lettre apparaitkfois dans le mot (ainsi, s"il y a troisEdans le mot, on divise par3!car les permutations qui se contentent d"échanger lesEentre eux ne modifient pas l"anagramme). Par exemple, le nombre d"anagrammes du mot DENOMBREMENT est 12!3!2!2!.
Remarque6.Le nombre de permutations d"un ensemble ànéléments est le nombre d"applications bijectives de cet ensemble dans lui-même. Définition 6.Unecombinaisondepéléments dans un ensemble finiEànéléments est un sous-
ensemble àpéléments deE. Définition 7.Soientnetpdeux entiers tels quep6n, on appellecoefficient binomiald"indices netple nombren p =n!p!(np)!(qui se lit " p parmi n »). Remarque7.On pose souventn
p = 0sip > n. Proposition 9.Le nombre de sous-ensembles àpéléments d"un ensemble ànéléments estn p Démonstration.En effet, une combinaison n"est rien d"autre qu"un arrangement dans lequel on a en- levé l"importance de l"ordre. Autrement dit, chaque combinaison apparaitp!fois quand on dénombre
les arrangements (puisqu"il y ap!façons d"ordonner un ensemble àpéléments), donc le nombre de
combinaisons àpéléments vautAn;pp!=n p .Exemple :Toujours dans la même urne, on tire désormais quatre boules simultanément. Le nombre
de tirages est10 4 =A4104! = 210. Remarque8.On peut encore une fois interpréter ceci à l"aide d"applications : le nombre de com- binaisons àpéléments dans un ensemble ànéléments est le nombre d"applications strictement
croissantes def1;:::;pgdansE. En effet, se donner une application strictement croissantefest équivalent à se donner le sous-ensembleff(1);f(2);:::;f(p)g(l"ordre étant imposé par la croissance
de l"application). 4 Un petit tableau pour résumer les cas d"utilisations de ces trois outils de dénombrement : L"ordre n"est pas importantL"ordre est important
RépétitionsListes
interdites!coefficients binômiaux!quotient de factorielles3 Propriétés des coefficients binomiaux
Proposition 10.Quelques propriétés des coefficients binomiaux, utiles pour les calculs : 8 n>2,n
0 = 1;n 1 =n;n 2 =n(n1)2 8 k6n,n
k =n nk (propriété de symétrie). 8 16k6n,kn
k =nn1 k1 8 16k6n,n1
k +n1 k1 =n k (relation de Pascal). Démonstration.Pour le premier point, il suffit de reprendre la définition des coefficients binomiaux :n
0 =n!0!n!= 1;n 1 =n!(n1)!=netn 2 =n!2!(n2)!=n(n1)2 La propriété de symétrie est facile aussi : n nk =n!(nk)!(n(nk))!=n!(nk)!k!=n k . Il y a également une interprétation combinatoire de ce résultat : choisir un sous-ensemble dekéléments
dans un ensemble ànéléments est équivalent à choisir son complémentaire, qui est constitué denk
éléments, donc il y a autant de sous-ensembles àkéléments et ànkéléments dans un ensemble à
néléments. Pour la troisième,kn
k =kn!k!(nk)!=n!(k1)!(nk)!, etnn1 k1 =n(n1)!(k1)!(n1k+ 1)!= n!(k1)!(nk)!, les deux quantités sont bien égales. Enfin, la formule de Pascal :
n1 k +n1 k1 =(n1)!k!(n1k)!+(n1)!(k1)!(nk)! (nk)(n1)! +k(n1)!k!(nk)!=n(n1)!k!(nk)!=n k . La encore, il y a une interprétation combinatoire. SoitEun ensemble ànéléments etxun élément fixé deE. Les sous-ensembles deE
àkéléments, au nombre den
k , se répartissent en deux catégories : ceux qui contiennentx, qui sont au nombre de n1 k1 puisqu"il restek1éléments à choisir parmi lesn1restants dansE une foisxchoisi; et ceux qui ne contiennent pasx, qui sont au nombre den1 k puisqu"il reste cette fois-cikéléments à choisir parmi lesn1restants (on n"en a encore choisi aucun). D"où la
formule.Triangle de Pascal :La relation de Pascal permet de calculer les valeurs des coefficients binomiaux
par récurrence, en les répartissant sous forme d"un tableau triangulaire : 5 k= 0k= 1k= 2k= 3k= 4k= 5k= 6k= 7k= 8n= 01 n= 111 n= 2121 n= 31331 n= 414641 n= 515101051 n= 61615201561 n= 7172135352171 n= 818285656562871 Pour obtenir un coefficient du tableau, on fait la somme de celui qui est au-dessus de lui, et de celui
qui est à gauche de celui-ci. Théorème 2.Formule du binôme de Newton.
Soientaetbdeux réels, etn2N, alors(a+b)n=nX
k=0 n k a kbnk. Remarque9.On peut obtenir à partir de cette formule le développement d"une différence :(ba)n=
nX k=0 n k (1)kakbnk. En pratique, il suffit d"alterner les signes. Exemple :(a+b)6=a6+ 6a5b+ 15a4b2+ 20a3b3+ 15a2b4+ 6ab5+b6. L"ordre est inversé par rapport à celui de la formule, mais c"est la façon habituelle d"écrire le développement. Autre exemple :
(12x)5= 152x+10(2x)210(2x)3+5(2x)4(2x)5= 110x+40x280x3+80x532x5. Démonstration.On va procéder par récurrence sur l"entiern. Pourn= 0, la formule du binome dit
simplement que(a+b)0=0 0 a 0b0, ce qui est vrai (on a1de chaque côté). Supposons la formule
vraie au rangn, on a alors(a+b)n+1= (a+b)(a+b)n= (a+b)nX k=0 n k a kbnkpar hypothèse de récurrence, donc en développant lea+bet en le faisant rentrer dans la somme, on obtient(a+b)n+1=
nX k=0 n k a k+1bnk+nX k=0 n k a kbn+1k. Effectuons un changement d"indice en remplaçantkpark+1 dans la première somme (on ne touche à rien dans la deuxième) :(a+b)n+1=n+1X k=1 n k1 a kbn+1k+ n X k=0 n k a kbn+1k=n n a n+1b0+nX k=1 n k1 +n k a kbn+1k+n 0 a 0bn+1(on a isolé un terme
dans chaque somme pour pouvoir regrouper les sommes). Maintenant, on reconnait la formule de Pascal dans la somme, donc(a+b)n+1=an+1+nX
k=1 n+ 1 k a kbn+1k+bn+1. Il ne reste plus qu"à remettre les deux termes isolés dans la somme pour obtenir la formule au rangn+ 1, ce qu"on peut faire puisqu"ils sont justement égaux aux termes manquants pourk= 0etk=n+ 1.Proposition 11.SoitEun ensemble fini de cardinaln. AlorsP(E)est fini, de cardinal2n.
Démonstration.Le cardinal deP(E)est le nombre de sous-ensembles deE. Or, on sait que, pour tout entierk, il y an k sous-ensembles deEàkéléments, ce qui fait au totalnX k=0 n k sous-ensembles. Cette somme n"est rien d"autre qu"un cas particulier de formule du binôme, poura=b= 1, donc elle vaut(1 + 1)n= 2n. 6 Une autre démonstration possible utilise le fait (démontré dans un chapître antérieur) queP(E)est
en bijection avec l"ensemble des applications deEdansf0;1g(via la fonction caractéristique). En découle quejP(E)j=jf0;1gjn= 2n. Une troisième démonstration pour la route, par récurrence en utilisant la relation de Pascal. Le fait
que 0X k=0 0 k = 2 0est trivial. Supposons que la formule reste vraie au rangn, alorsn+1X
k=0 n+ 1 k n+1X k=0 n k +n k1 =n+1X k=0 n k +Xk=1nn k = 22n= 2n+1puisque les coefficients binomiaux sont nuls pourk=1et pourk=n+ 1.Il est maintenant temps de répondre aux trois questions posées en début de chapitre :
C"est une application directe du cours, il y a49
7 = 85 900 584grilles différentes au Loto. Le nombre de choix possibles pour les49dates de naissance des élèves de la classe est36549 puisqu"on a365dates possibles pour chaque élève. Si on ne veutpasde répétition (donc des élèves tous nés à des dates distinctes), il n"y a plus queA49365possibilités. Autrement
dit, la probabilité que tous les élèves soient nés à des dates différentes vaut A49365365
40'0:034. La
probabilité qu"au moins deux élèves soient nés le même jour vaut donc environ10:034 = 0:966.
L"existence d"anniversaires simultanés est pratiquement certaine. Pour constituer le premier trinôme, il faut choisir3élèves parmi les48élèves de la classe. Pour
le deuxième, on choisit3élèves parmi les45restants, et ainsi de suite jusqu"à avoir à prendre3
élèves parmi les3derniers pour le dernier trinôme (autant dire qu"on n"a plus le choix). Reste
à diviser tous ces choix par16!, le nombre d"ordres différents possibles qu"on peut avoir sur les
16trinômes, soit48
3 45
3 42
3 39
3 36
3 33
3 30
3 27
3 24
3 21
3 18 3 15 3 12 3 9 3 6 3 3 3 116!
répartitions possibles. Si on écrit tout sous forme de quotient de factorielles, ça se simplifie beaucoup pour laisser 48!(3!)
1616!
(qui est accessoirement un nombre gigantesque). On peut retrouver ce résultat directement : on choisit un ordre sur les48élèves (d"où le numérateur), puis on découpe la liste ordonnée de
48élèves en16paquets de3. L"ordre dans chacun des16paquets n"a aucune importance (on
divise donc16fois de suite par3!) et l"ordre des16paquets n"a pas non plus d"importance, donc on divise encore par16!. 7quotesdbs_dbs41.pdfusesText_41
Proposition 4.La formule de Poincaré étant assez peu lisible, voici ce que ça donne pourn= 3et
n= 4: jA[B[Cj=jAj+jBj+jCj jA\Bj jA\Cj jB\Cj+jA\B\Cj jA[B[C[Dj=jAj+jBj+jCj+jDj jA\Bj jA\Cj jA\Dj jB\Cj jB\Dj jC\Dj+jA\B\Cj+jA\B\Dj+jA\C\Dj+jB\C\Dj jA\B\C\Dj
2Démonstration.La preuve de la formule générale, assez technique, se fait par récurrence. On se
contentera de prouver la formule pourn= 3en partant de la proposition précédente :jA[B[Cj= j(A[B)[Cj=jA[Bj+jCj j(A[B)\Cj=jAj+jBj jA\Bj+jCj j(A\C)[(B\C)j= jAj+jBj jA\Bj+jCj jA\Cj jA\Bj+jA\C\B\Cj, ce qui donne bien la formuleannoncée.Exemple :Dans un lycée de300élèves,152savent jouer au poker,83au tarot et51au bridge. De
plus,24savent jouer à la fois au poker et au tarot,14au poker et au bridge, et8au tarot et aubridge. Enfin,3élèves maitrisent les trois jeux de cartes. Le nombre d"élèves jouant aux cartes est
alors de152 + 83 + 5124148 + 3 = 237. Proposition 5.SoitAun sous-ensemble fini d"un ensemble finiE, alorsjAj=jEj jAj. Démonstration.C"est une conséquence de la formule pour une union :Eest union disjointe deAet deA, doncjEj=jAj+jAj.Proposition 6.SoientEetFdeux ensembles finis, alorsEFest fini, etjEFj=jEj jFj.Démonstration.Pas de preuve rigoureuse pour celui-ci, simplement une idée de la façon dont ça
marche. Soitnle cardinal deE, ete1;e2;:::;enses éléments,ple cardinal deFetf1;:::;fpses éléments. on peut placer les éléments deEFdans un tableau de la façon suivante :e 1e 2:::e nf1(e1;f1)(e2;f1):::(en;f1).
..fp(e1;fp)(e2;fp):::(en;fp)Il y biennpéléments dans le tableau, donc dansEF.2 Listes, arrangements et combinaisons
Définition 2.SoitEun ensemble fini de cardinaln, etp2N. Unep-listed"éléments deE, ou p-uplet d"éléments deE, est simplement un élément deEp.Remarque2.On peut très bien avoir plusieurs fois le même élément dans unep-liste. Par ailleurs,
l"ordre des éléments de lap-liste est important. Proposition 7.Le nombre dep-listes dans un ensemble de cardinalnvautnp.Démonstration.C"est une conséquence de la formule de cardinal du produit vue un peu plus haut :
commejEFj=jEj jFj, on ajEpj=jEjp, ce qui prouve bien la propriété.Exemple :On tire dans une urne contenant10boules numérotées de1à10quatre boules succes-
sivement avec remise. Le nombre de tirages possibles est de104= 10 000(il y a répétition possible
à cause des remises, et l"ordre est important). Remarque3.Le nombre dep-listes d"un ensemble ànéléments est aussi le nombre d"applications de l"ensemblef1;:::;pgvers cet ensemble. En effet, se donner une telle applicationfrevient à sedonner les valeurs des imagesf(1),f(2), ...,f(p), c"est-à-dire à se donner une liste depéléments
deE. Définition 3.SoitEun ensemble ànéléments etp2N, on appellearrangementdepéléments deEunep-liste d"éléments distincts deE. Remarque4.L"ordre des éléments est toujours important, par contre on ne peut plus avoir de répétition d"élément dans un arrangement. 3 Définition 4.Soientnetpdeux entiers tels quep6n, on noteApn=n!(np)!=n(n1)(n2):::(np+ 1).
Proposition 8.Le nombre d"arrangements depéléments dans un ensemble ànéléments vautApn.
Démonstration.Contentons-nous de l"idée intuitive : lorsqu"on construit un arrangement, on an choix pour le premier élément,n1pour le deuxième, ...,np+ 1pour lepème, soit au totaln(n1)(np+ 1) =n(n1):::(np+ 1)(np):::21n(n1):::21=n!(np)!.Exemple :On reprend la même urne que précédemment, mais on tire les quatre boules successive-
ment sans remise. Le nombre de tirages possibles est désormais deA410=10!6! = 10987 = 5 040.Remarque5.Le nombre d"arrangements depéléments dans un ensemble ànéléments est également
le nombre d"applications injectives def1;:::;pgdansE.Définition 5.Un arrangement denéléments dans un ensemble ànéléments est aussi appelé
permutation. Il y a doncn!permutations dans un ensemble ànéléments. Exemple :Le nombre d"anagrammes d"un mot peut se calculer à l"aide de permutations. Il faut simplement diviser le nombre total du permutations du mot park!chaque fois qu"une même lettre apparaitkfois dans le mot (ainsi, s"il y a troisEdans le mot, on divise par3!car les permutations qui se contentent d"échanger lesEentre eux ne modifient pas l"anagramme). Par exemple, le nombre d"anagrammes du mot DENOMBREMENT est12!3!2!2!.
Remarque6.Le nombre de permutations d"un ensemble ànéléments est le nombre d"applications bijectives de cet ensemble dans lui-même.Définition 6.Unecombinaisondepéléments dans un ensemble finiEànéléments est un sous-
ensemble àpéléments deE. Définition 7.Soientnetpdeux entiers tels quep6n, on appellecoefficient binomiald"indices netple nombren p =n!p!(np)!(qui se lit " p parmi n »).Remarque7.On pose souventn
p = 0sip > n. Proposition 9.Le nombre de sous-ensembles àpéléments d"un ensemble ànéléments estn p Démonstration.En effet, une combinaison n"est rien d"autre qu"un arrangement dans lequel on a en-levé l"importance de l"ordre. Autrement dit, chaque combinaison apparaitp!fois quand on dénombre
les arrangements (puisqu"il y ap!façons d"ordonner un ensemble àpéléments), donc le nombre de
combinaisons àpéléments vautAn;pp!=n p.Exemple :Toujours dans la même urne, on tire désormais quatre boules simultanément. Le nombre
de tirages est10 4 =A4104! = 210. Remarque8.On peut encore une fois interpréter ceci à l"aide d"applications : le nombre de com-binaisons àpéléments dans un ensemble ànéléments est le nombre d"applications strictement
croissantes def1;:::;pgdansE. En effet, se donner une application strictement croissantefestéquivalent à se donner le sous-ensembleff(1);f(2);:::;f(p)g(l"ordre étant imposé par la croissance
de l"application). 4 Un petit tableau pour résumer les cas d"utilisations de ces trois outils de dénombrement :L"ordre n"est pas importantL"ordre est important
RépétitionsListes
interdites!coefficients binômiaux!quotient de factorielles3 Propriétés des coefficients binomiaux
Proposition 10.Quelques propriétés des coefficients binomiaux, utiles pour les calculs :8 n>2,n
0 = 1;n 1 =n;n 2 =n(n1)28 k6n,n
k =n nk (propriété de symétrie).8 16k6n,kn
k =nn1 k18 16k6n,n1
k +n1 k1 =n k (relation de Pascal).Démonstration.Pour le premier point, il suffit de reprendre la définition des coefficients binomiaux :n
0 =n!0!n!= 1;n 1 =n!(n1)!=netn 2 =n!2!(n2)!=n(n1)2 La propriété de symétrie est facile aussi : n nk =n!(nk)!(n(nk))!=n!(nk)!k!=n k . Ily a également une interprétation combinatoire de ce résultat : choisir un sous-ensemble dekéléments
dans un ensemble ànéléments est équivalent à choisir son complémentaire, qui est constitué denk
éléments, donc il y a autant de sous-ensembles àkéléments et ànkéléments dans un ensemble à
néléments.Pour la troisième,kn
k =kn!k!(nk)!=n!(k1)!(nk)!, etnn1 k1 =n(n1)!(k1)!(n1k+ 1)!= n!(k1)!(nk)!, les deux quantités sont bien égales.Enfin, la formule de Pascal :
n1 k +n1 k1 =(n1)!k!(n1k)!+(n1)!(k1)!(nk)! (nk)(n1)! +k(n1)!k!(nk)!=n(n1)!k!(nk)!=n k . La encore, il y a une interprétationcombinatoire. SoitEun ensemble ànéléments etxun élément fixé deE. Les sous-ensembles deE
àkéléments, au nombre den
k , se répartissent en deux catégories : ceux qui contiennentx, qui sont au nombre de n1 k1 puisqu"il restek1éléments à choisir parmi lesn1restants dansE une foisxchoisi; et ceux qui ne contiennent pasx, qui sont au nombre den1 k puisqu"il restecette fois-cikéléments à choisir parmi lesn1restants (on n"en a encore choisi aucun). D"où la
formule.Triangle de Pascal :La relation de Pascal permet de calculer les valeurs des coefficients binomiaux
par récurrence, en les répartissant sous forme d"un tableau triangulaire : 5 k= 0k= 1k= 2k= 3k= 4k= 5k= 6k= 7k= 8n= 01 n= 111 n= 2121 n= 31331 n= 414641 n= 515101051 n= 61615201561 n= 7172135352171 n= 818285656562871Pour obtenir un coefficient du tableau, on fait la somme de celui qui est au-dessus de lui, et de celui
qui est à gauche de celui-ci.Théorème 2.Formule du binôme de Newton.
Soientaetbdeux réels, etn2N, alors(a+b)n=nX
k=0 n k a kbnk.Remarque9.On peut obtenir à partir de cette formule le développement d"une différence :(ba)n=
nX k=0 n k (1)kakbnk. En pratique, il suffit d"alterner les signes. Exemple :(a+b)6=a6+ 6a5b+ 15a4b2+ 20a3b3+ 15a2b4+ 6ab5+b6. L"ordre est inversé parrapport à celui de la formule, mais c"est la façon habituelle d"écrire le développement. Autre exemple :
(12x)5= 152x+10(2x)210(2x)3+5(2x)4(2x)5= 110x+40x280x3+80x532x5.Démonstration.On va procéder par récurrence sur l"entiern. Pourn= 0, la formule du binome dit
simplement que(a+b)0=0 0 a0b0, ce qui est vrai (on a1de chaque côté). Supposons la formule
vraie au rangn, on a alors(a+b)n+1= (a+b)(a+b)n= (a+b)nX k=0 n k a kbnkpar hypothèse derécurrence, donc en développant lea+bet en le faisant rentrer dans la somme, on obtient(a+b)n+1=
nX k=0 n k a k+1bnk+nX k=0 n k a kbn+1k. Effectuons un changement d"indice en remplaçantkpark+1 dans la première somme (on ne touche à rien dans la deuxième) :(a+b)n+1=n+1X k=1 n k1 a kbn+1k+ n X k=0 n k a kbn+1k=n n a n+1b0+nX k=1 n k1 +n k a kbn+1k+n 0 a0bn+1(on a isolé un terme
dans chaque somme pour pouvoir regrouper les sommes). Maintenant, on reconnait la formule dePascal dans la somme, donc(a+b)n+1=an+1+nX
k=1 n+ 1 k a kbn+1k+bn+1. Il ne reste plus qu"à remettre les deux termes isolés dans la somme pour obtenir la formule au rangn+ 1, ce qu"on peutfaire puisqu"ils sont justement égaux aux termes manquants pourk= 0etk=n+ 1.Proposition 11.SoitEun ensemble fini de cardinaln. AlorsP(E)est fini, de cardinal2n.
Démonstration.Le cardinal deP(E)est le nombre de sous-ensembles deE. Or, on sait que, pour tout entierk, il y an k sous-ensembles deEàkéléments, ce qui fait au totalnX k=0 n k sous-ensembles. Cette somme n"est rien d"autre qu"un cas particulier de formule du binôme, poura=b= 1, donc elle vaut(1 + 1)n= 2n. 6Une autre démonstration possible utilise le fait (démontré dans un chapître antérieur) queP(E)est
en bijection avec l"ensemble des applications deEdansf0;1g(via la fonction caractéristique). En découle quejP(E)j=jf0;1gjn= 2n.Une troisième démonstration pour la route, par récurrence en utilisant la relation de Pascal. Le fait
que 0X k=0 0 k = 20est trivial. Supposons que la formule reste vraie au rangn, alorsn+1X
k=0 n+ 1 k n+1X k=0 n k +n k1 =n+1X k=0 n k +Xk=1nn k = 22n= 2n+1puisque les coefficients binomiauxsont nuls pourk=1et pourk=n+ 1.Il est maintenant temps de répondre aux trois questions posées en début de chapitre :
C"est une application directe du cours, il y a49
7 = 85 900 584grilles différentes au Loto. Le nombre de choix possibles pour les49dates de naissance des élèves de la classe est36549 puisqu"on a365dates possibles pour chaque élève. Si on ne veutpasde répétition (doncdes élèves tous nés à des dates distinctes), il n"y a plus queA49365possibilités. Autrement
dit, la probabilité que tous les élèves soient nés à des dates différentes vautA49365365
40'0:034. La
probabilité qu"au moins deux élèves soient nés le même jour vaut donc environ10:034 = 0:966.
L"existence d"anniversaires simultanés est pratiquement certaine.Pour constituer le premier trinôme, il faut choisir3élèves parmi les48élèves de la classe. Pour
le deuxième, on choisit3élèves parmi les45restants, et ainsi de suite jusqu"à avoir à prendre3
élèves parmi les3derniers pour le dernier trinôme (autant dire qu"on n"a plus le choix). Reste
à diviser tous ces choix par16!, le nombre d"ordres différents possibles qu"on peut avoir sur les
16trinômes, soit48
3 453 42
3 39
3 36
3 33
3 30
3 27
3 24
3 21
3 18 3 15 3 12 3 9 3 6 3 3 3 116!
répartitions possibles. Si on écrit tout sous forme de quotient de factorielles, ça se simplifie beaucoup pour laisser
48!(3!)
1616!(qui est accessoirement un nombre gigantesque). On peut retrouver ce résultat directement :
on choisit un ordre sur les48élèves (d"où le numérateur), puis on découpe la liste ordonnée de
48élèves en16paquets de3. L"ordre dans chacun des16paquets n"a aucune importance (on
divise donc16fois de suite par3!) et l"ordre des16paquets n"a pas non plus d"importance, donc on divise encore par16!. 7quotesdbs_dbs41.pdfusesText_41[PDF] formule de crible dénombrement
[PDF] croissance de la probabilité
[PDF] programmation culturelle anglais cycle 3
[PDF] formule de poincaré application
[PDF] formule d inclusion exclusion demonstration
[PDF] notion définition philosophique
[PDF] notions synonyme
[PDF] jules valles mouvement littéraire
[PDF] jules vallès le bachelier
[PDF] jules vallès livres
[PDF] jules vallès biographie
[PDF] jules valles college
[PDF] jog the web
[PDF] formules de physique pdf