Principes de dénombrement

Principes de dénombrement

-

Documents
7 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

Principes de dénombrement. Dénombrement desp-listes,
des arrangements et des permutations. Exemples de
situations dont l’étude se ramène aux cas précédents.
Dany-Jack Mercier
IUFM de Guadeloupe, Morne Ferret,
BP399, Pointe-à -Pitre cedex 97159, France
dany-jack.mercier@univ-ag.fr
28 mai 2002
¤Si F est un ensemble …ni, on note #F son cardinal. Si p 2 N on pose N = f1; :::; pg.p
En…n, dans toute la suite, A désigne l’ensemble …ni A = fa ; :::;a g de cardinal n ¸ 1.1 n
Le premier paragraphe est constitué de rappels. Pour un exposé de 25 minutes, on se
contentera de rappeler brièvement le principe du berger.
1 Principes de dénombrement
Le langage privilégié du dénombrement est celui des ensembles. Il suppose connu la notion
de cardinal d’un ensemble …ni, et celle de partition d’un ensemble.
Tous les problèmes de dénombrement se résolvent en utilisant les deux principes ci-dessous,
et l’on remarquera que le principe du berger provient directement de celui de la somme, si
bien que l’on puisse a¢rmer de faç on abrupte qu’un seul principe est àla base de toutes
les opérations de dénombrement : le principe de la somme.
Lemme 1 Principe de la somme
Si A ; :::; A est une partition de l’ensemble … ni A, alors #A = #A + ::: + #A .1 k 1 k
Preuve : On raisonne par récurrence sur k. La propriété est triviale si k = 1. Si k = 2,
considérons une partition A ; A de A. Si l’on note n le cardinal de A , on sait l’existence1 2 i i
de deux bijections f : N ! A (i = 1;2) et on véri…e que ...

Sujets

Informations

Publié par
Nombre de visites sur la page 204
Langue Français
Signaler un problème
pincie de dénômemen. Dénômemen deplie, de ààngemen e de emûàiôn.Exemle de iûàiôn dôn l’éûde e àmène àûx cà écéden. DànyJàck Mecie IÛFM de Gûàdelôûe, Mône Fee, Bp399, pôineàpie cedex 97159, Fànce dànyjàck.mecie@ûniàg.f 28 mài 2002
¤ iFe ûn enemleni, ôn nôe#Fôn càdinàl.ip2Nôn ôeNp=f1p: : ;; :g. Enn, dàn ôûe là ûie,Adéigne lenemleniA=fa1; :: : ;angde càdinàln¸1. Le emie ààgàhe e côniûéde àel.pôû ûn exôéde 25 minûe, ôn e côneneà de àele ièemen le incie dû ege.
1 Principesde dénombremen Le làngàge iilégiédû dénômemen e celûi de enemle.Il ûôe cônnû là nôiôn de càdinàl dûn enemleni, e celle de àiiôn dûn enemle. ôû le ôlème de dénômemen e éôlen en ûiliàn le deûx incie cideôû, e lôn emàûeà ûe le incie dû ege ôien diecemen de celûi de là ômme, i ien ûe lôn ûie à¢me de fàçôn àûe ûûn eûl incie eàlà àe de ôûe le ôéàiôn de déle incie de là ômme.nômemen : Lemme 1Principe de la somme SiA1; :: : ;Akne partition de lest ûensembleniA, alors#A= #A1+: : :+ #Ak. PreUVe :Ô n àiônne à écûence ûk. Làôiéée iiàle ik= 1. ik= 2, cônidéôn ûne àiiônA1; A2deAl. iôn nôenile càdinàl deAi, ôn ài lexience (i= 1;2) e ôn éie û de deûx ijeciônfi:Nni!Aie làlicàiôn N!A=A[A f:n1+n21 2 dé …nie àf(n) =f1(n)in·n1ef(n) =f2(n¡n1)in > n1, e ûne ijeciôn. Là ôiééàû àng2û¢àôûe ûe là ôiéée héédiàie. Ene¤e, i là fômûle e ài àû àngk, e iA1; :A: : ;k+1déigne ûne àiiôn deA, là àie 0 [cden0001] 1.00h://eô.wànàdôô.f/megàmàh °D.J. Mecie. vôû ôûez fàie ûne côie de ce nôe ôû ôe ûàge eônnel.c 2002,
1
fA[: : :[A ; Age ûne àiiôn deA. Ô nà dônc 1k k+1 #A(= #A[: : :[A) + #A 1k k+1 e lhyôhèe écûene enàîne ien#A= #A1+: : :+ #Ak+ #Ak+1. Le incie de là ômme enàîne immédiàemen le héôème ûiàn : héorème 1SiAetBsont deûX parties dû nensembleniE, alors ¡ ¢ 1)#{A= #E¡#A. 2)# (A[B) = #A+ #B¡# (A\B)et plûs généralement, siA1; :: : ;Apsont des parties deE, X X # (A1[: : :[Ap#) =Ai¡# (Ai\Aj) +: : : i i<j X k+1p+1 1ik) +: :+ (¡(1) #A1\: :\Ap) + (¡(1) #Ai\: :\A i <:: : <i 1k © ª PreUVe :1) Là àieA;{Afôme ûne àiiôn deA. 2) Ô n àiônne à écûence ûk. ik= 1i, là fômûle e iiàle.k= 2, ôn inôdûi là àiiôn ûiàne deA1[A2: A[A= (AnA)[(AnA)[(A\A) 1 21 22 11 2 ôû ôeni # (A1[A2) = #(A1nA2) + # (A2nA1) + # (A1\A2) = [#(A1nA2) + # (A1\A2)] + [# (A2nA1) + # (A1\A2)] ¡# (A1\A2) = #(A1) + # (A2)¡# (A1\A2): Aû àngk+ 1, ôônB=A1[: : :[Akà. Ô n # (A[: : :[A) = #(B[A() = #B) + # (A)¡# (B\A): 1k+1k+1k+1k+1 Lhyôhèe écûene imliûe àlô k X X ¡ ¢ j+1 # (A[: : :[A() =¡\: : :\A 1k+11) #Ai1ij+ # (Ak+1) j=1 1·i1<: : : <ij·k ¡# (B\Ak+1) e # (B\Ak+1) = #((A1\Ak+1)[: : :[(Ak\Ak+1)) k X X ¡ ¢ j+1 = (\ \A : ¡1) #Ai1: : :\Aijk+1 j=1 1·i1<: : : <ij·k Ce deûx denièe exeiôn enàînen ien là fômûle àû àngk+ 1. Le incie de là ômme enàîne àûi le célèe :
2
Lemme 2Principe du berger (ou principe des tiroirs) Sif:E!Fest ûne application sûrjectiVeàValeû rn ensembledans ûniF, et sil eXiste ¡ ¢ ¤ ¡1 p2Ntel qûe#f(fyg) =ppoû rtoû ty2F, alors#E=p£#F. : S ¡1¡1 PreUVen à là àiiôn: ÔE=f(F) =f(fyg)deEen#Fôûenemle y2F P¡ ¢ ¡1 cônenàn chàcûnpélémen, dôù#E= #f(fyg) =p£#F. y2F Dàn le ààgàhe ûiàn, ôn dénôme deplie àn ûil ôi néceàie de cônnàîe le càdinàl dû ôdûi càéien depenemleni. Ô neû néànmôin éfée càlcûle ce càdinàl e àliûe le éûlà ôû ôeni le nôme deplie. Ce ûne à¤àie de chôix. àelôn ûe le ôdûi càéien de deûx enemleniA1[: : :[Ape lenemle de ûienie(a1; :: : ;ap)ôùai2Aiôû ôûi, lôde de eme de ce ûieéàn imôàn. Ceenemle e nôéA1£: : :£Apcee d. Aecé …niiôn : Lemme 3Principe du produit Si#Ai=nitoû tpoû ri, alors# (A1£: : :£Ap) =n1£: : :£np. PreUVe :Le éûlà e iiàl ûàndp= 1. Aûàngp+ 1, ôn dé …ni là ûjeciôn f:A£: : :£A£A!A 1p p+1p+1 (a ; a: : ;a ; :)7!a 1p p+1p+1 ¡1 Cômme#f(fap+1g() = #A1£: : :£Ap) =n1£: : :£npà àlicàiôn de lhyôhèe écûene, le incie dû ege enàîne # (A1£: : :£Ap+1) = #(A1£: : :£Ap)£# (Ap+1) =n1£: : :£np+1:
2 Dénombremen desplis es Dé …1ni ionÛnepliste d’éléments deA(on dit aûssi :û nepliste deA) est û nesû itedepéléments deA. Onappelleproduit cartésiendepcopies deAlensemble formédesplistes deA. Onle note p A=A£: : :£A: | {z } pfacteû rs Ûneplie deA’éci dônc(x1: : ;x; :p)ôùxi2Aôû ôûi. Ô nemàûeà ien ûe lôde de eme dûnepà exemle lelie e imôàn :3lie(a; b; c)e(b; a; c) ôn di¤ éene. Ceendànle eme de là lie eûenêe ééé àûàn de fôi ûôn le déie. héorème 2tant deIl Y a aûplistes deAdqû eapplications deNpdansA. PreUVe: Làlicàiôn p ª:F(Np; A)!A f7!(f(1): : ;; :f(p)) ôùF(Np; A)déigne lenemle de àlicàiôn deNpdànA, e ijecie.
3
p p héorème 3#A=n PreUVe:Premièionre solU: Ô ncônûi ûn àe de chôix. Il y ànchôix dû emie p eme de là lie,nchôix dû ecônd eme, ...ôi en ôûn£n: : :£n=nàncheàce àe. Leecôûàûn àe eme de iûàlie chàcûne deplie, mài là jûicàiôn igôûeûe dûn el éûlà e feà à exemle en càlcûlàn à écûence le càdinàl dû ôdûi càéien depenemleni (cf Lemme 3). DeUXièionme solU: écûence ûpôûnxé. Leéûlà e iiàl ip= 1. ûôônle ài àû àngp. Làlicàiôneiciônª:F(Np+1; A)! F(Np; A) f!7fj Np e ûjecie.ig2 F(Np; A), e iª(f) =g,fe àfàiemen cônnûe û chàcûn de ¡1 enie1,: : :,p, e eûlf(p+ 1)eàchôii dànA. Aini#ª(g) =ne le incie p+1 dû ege enàîne#F(Np+1; A) =n#F(Np; A) =n : n Corollaire 1Le cardinal de lensembleP(A)des parties deAest2. PreUVe: Achàûe àieXdeAôn àôcie là fônciôn cààcéiiûeÂdé …nie à X Â(x) = 1ix2X, eÂ(x) = 0inôn. Ôn ôien ûne ijeciôn deP(A)û X X F(A;f0;1g).
3 DépermU a ionse desarrangemen snombremen des Dé …ni ion2Ûnarrangement depéléments deAû n(on dit encore :parrangement deA) est ûnepliste deAformée d’éléments deûXàdistincts. Ûnedeû Xpermutation deAnest ûnarrangement deA. héorème 4Il Y a aûtant deparrangements deAqû edapplications injectiVes deNp dansA. PreUVe: Làlicàiôn ª:I(N; A)! A p f!7(f(1); :: : ;f(p)) ôùI(Np; A)déigne lenemle de àlicàiôn injecie deNpdànA, eAlenemle de ààngemen deA, e ijecie.
Dé …ni ion3Le nombre darrangements depéléments densembleû nànéléments est p notéAn.
héorème 5On a
oùn! :=n£(n¡1)£
n! p A=n(n¡1): : :(n¡p+ 1) = n (n¡p)! £2£1et0! := 1.
4
PreUVe:Premièionre solU: Ô ncônûi ûn àe, ce ûi eienàfàie le àiôn nemen ûiàn.Il y ànÛne fôi cechôix ôile ôû le emie eme de là lie. chôix e¤ecûé, il een¡1chôix ôile ôû le deûxième eme de là lie, e àini de ûie... Finàlemen,il eeàn¡p+ 1ôiilié ôû lepième eme de là lie.Le nôme de ànche de làe eà dôncn(n¡1): : :(n¡p+ 1). DeUXièionme solU: Ôn dénômeI(Np; A)à écûence ûpôûnxé. Le éûlà e iiàl ip= 1. ilà fômûle e ôûée àû àngp, mônônlà àû àngp+ 1. Làlicàiôneiciônª:I(Np+1; A)! I(Np; A) f!7fjN p e ûjecie.ig2 I(Np; A), e iª(f) =g,fe cônnûe û chàcûn de enie1p; :: : ;. Le ôlôngemen defôile déenden eûlemen dû chôix def(p+ 1)dànA, e ¡1 feà injecie i, e eûlemen i,f(p+ 1)2Anf(Np)àûà. Ô n#ª(g) =n¡pe le incie dû ege enàîne #I(Np+1; A) = (n¡p) #I(Np; A) ôi#I(Np+1; A) = (n¡p) [n(n¡1): : :(n¡p+ 1)]à lhyôhèe écûene. RemarqUeûne jûi: Dônnôncàiôn igôûeûe de lûiliàiôn dûn àe dàn là démônàiôn dû héôème écéden. pôûcelà, àiônnôn à écûence ûn. Nôôn An(p)lenemle depààngemen dûn enemleAànélémen, e cônidéôn là ôiéé H(n) :# (An(p)) =n(n¡1): : :(n¡p+ 1)ôû ôûp2 f1n: : ;; :g.Là ôiééH(1)i là ôie iiàle.ééH(n)e àie, cônidéôn là ôjeciôn ¼:An(p)!A (a1a: : ;; :p)!7ap: ip= 1, àlô# (An(1)) =ne iiàl.ip >1, nôôn ûe là ôjeciôn¼e ûjecie e éie ¡ ¢ ¡1 8a2A#¼(fag# () =A(p¡1)): n¡1 Le incie dû ege dônne # (An(p)) =n£# (An¡1(p¡1)) e lhyôhèe écûene ’éci # (An¡1(p¡1)) = (n¡1): : :((n¡1)¡(p¡1) + 1) = (n¡1): : :(n¡p+ 1): Dônc # (An(p)) =n(n¡1): : :(n¡p+ 1) e là ôiééH(n)e ien démônée.
5