Analyse Combinatoire

Embed Size (px)

DESCRIPTION

En fonction de la demande de l’utilisateur, Alizé-Lcpc est distribué dans sa version intégrale comportant les troismodules Alizé-mécanique, Alizé-gel et Alizé-rétrocalcul, ou dans l’une des trois versions réduites suivantes : Alizémécaniqueseul, ou Alizé-gel seul, ou Alizé-mécanique et Alizé-rétrocalcul. La présente notice d’utilisation estcommune à ces trois versions possibles de distribution. Les différentes parties qui la composent recouvrent les troisprofils de distribution du logiciel :

Citation preview

  • 5/19/2018 Analyse Combinatoire

    1/51

    Dpartement de Mathmatiques et Informatique

    A b d e l h am i d El M o ss ad e q

    Professeur l HTP

  • 5/19/2018 Analyse Combinatoire

    2/51

    A. El Mossadeq

    Mai 2008

  • 5/19/2018 Analyse Combinatoire

    3/51

    TABLE DES MATIRES

    1.Principedesbergers 1

    2.Applications 2

    3.

    Ensemble

    de

    parties

    4

    4.Injections 4

    5.Partiesdunensemble 6

    6.

    Arrangements

    7

    7.Combinaisons 8

    8.Permutationsavecrptition 9

    9.

    Combinaisons

    avec

    rptition

    10

    10.Exercices 12

    11.Appendice:Principauxrsultats 46

  • 5/19/2018 Analyse Combinatoire

    4/51

  • 5/19/2018 Analyse Combinatoire

    5/51

    Analyse Combinatoire A. El Mossadeq

    1. Principe des Bergers

    Proposition 1

    SoitA etB deux ensembles non vides etfune application deA dansB.On suppose queB est ni de cardinaln et que pour touty dansB, le cardinalde limage rciproque dey parf,f1 (fyg), est gal un entier non nulp.AlorsA est ni et son cardinal est gal np :

    card A= np

    Preuve 1

    Par hypothse, le cardinal def1 (fyg) est non nul pour touty dansB.Doncf1 (fyg) est non vide pour tout y dansB, do la surjection de f:Daprs la dcomposition canonique de f,A=Retf(A) sont quipotents.Orfest surjective, donc :

    f(A) =Bet par consquent A=RetB ont le mme cardinal :

    card A=R= card B

    Pour toutx2 A, dsignons parC(x) la classe dquivalence de x modulo R:

    C(x) = fy2A j xRyg

    = fy2A j f(x) =f(y)g

    =

    y2A j y 2f1

    (ff(x)g)

    = f1 (ff(x)g)

    On en dduit que C(x) a pour cardinal p pour tout x2 A :

    8x2 A : card C(x) =p

    Soit alorsx1;:::;xn un systme de reprsentants des classes dquivalence mod-uloR.

    Comme C(x1) ;:::;C(xn) forment une partition deA :

    1

  • 5/19/2018 Analyse Combinatoire

    6/51

    A. El Mossadeq Analyse Combinatoire

    8>>>:

    8i; j 2 f1;:::;ng: i 6=j =)C(xi) \ C(xj) =;nSi=1

    C(xi) =A

    On a alors :

    card A =

    nXk=1

    card C(xk)

    =

    nXk=1

    p

    = np

    Exemple 1

    Le nombre dlments dun tableau n lignes et p colonnes est np.En eet, soit lapplacation de lensemble des lments du tableau dans lensemblef1;:::;ng, qui aux lments de laieme ligne associei,1 i n: Alors :(1) est surjective,(2) pour tout i,1 i n, card1 (fyg) =p:Donc le nombre dlments du tableau est np.

    2. Applications

    Proposition 2

    SoitA etB deux ensembles de cardinauxn etp respectivement et soit F(A; B)lensemble des applications deA dansB.Alors le cardinal deF(A; B) estpn :

    cardF(A; B) =pn

    2

  • 5/19/2018 Analyse Combinatoire

    7/51

    Analyse Combinatoire A. El Mossadeq

    Preuve 2

    Procdons par rcurrence surn.

    (i)n = 1

    Pour dnir une application deA = fagdansB , il sut de dnir limage de

    adansB:

    Il y ap possibilits, donc p applications de A dansB .

    (ii) On suppose que si A1 a pour cardinal n1, alors le cardinal de F(A1; B)

    estpn1 :

    F(A1; B) =pn1

    SoitA un ensemble de cardinal n,a un lment arbitraire de Aet posons :

    A1=A fag

    Lapplication':

    F(A; B) ! F(A1; B) F(fag ; B)f 7!

    fjA1; fjfag

    est bijective, do :

    cardF(A; B) = cardF(A1; B) cardF(fag ; B)

    = pn

    Exemple 2

    Une socit a dcid de lancer un nouveau produit dentretien. Le nom de ce

    nouveau produit doit comporter quatre lettres.

    Combien de noms peut-on former avec toutes les lettres de lalphabet ?

    Il y a autant de noms que dapplications dun ensemble quatre lments dans

    un ensemble 26 lments, cest dire :

    264 = 456 976

    3

  • 5/19/2018 Analyse Combinatoire

    8/51

    A. El Mossadeq Analyse Combinatoire

    3. Ensembles des Parties

    Proposition 3

    SoitEun ensemble ni de cardinaln etP(E) lensemble de toutes les partiesdeE.Alors le cardinal deP(E) est2n :

    cardP(E) = 2n

    Preuve 3

    Lapplication :

    P(E) ! F(E; f0; 1g)

    A 7! A

    oA est la fonction caractristique de A, est une bijection.

    En eet, toute application f 2 F(E; f0; 1g) est la fonction caractristique dela partief1 (f1g).De plus, pour toute partie AetB deEon a :

    A= B =)A = B

    Il en rsulte que :

    cardP(E) =cardF(E; f0; 1g) = 2n

    4. Injections

    Proposition 4

    SoitA etB deux ensembles de cardinaux respectifsp etn,p n, etG (A; B)lensemble des injections deA dansB.

    4

  • 5/19/2018 Analyse Combinatoire

    9/51

    Analyse Combinatoire A. El Mossadeq

    Alors lensemble dinjections deA dansB a pour cardinal n!

    (n p)!:

    card G (A; B) = n!

    (n p)!

    Preuve 4

    Procdons par rcurrence surp.

    (i)p = 1

    Toute application de A dans B est injective, donc le nombre dapplications

    injectives est :

    n= n!

    (n 1)!

    (ii) On suppose que si A1 est un ensemble p 1 lments, alors le cardinal de

    G (A1; B) est :

    card G (A1; B) =

    n!

    (n (p 1))!SoitA un ensemble de cardinaln,a un lment arbitraire de A et considrons

    lensemble :

    A1=A fag

    Lapplication :

    G (A; B) ! G (A1; B)

    f 7! fjA1

    est surjective, de plus pour tout f 2 G (A1; B), le cardinal de limage r-

    ciproque def par est[n (p 1)] :

    card 1 (ffg) =n (p 1)

    5

  • 5/19/2018 Analyse Combinatoire

    10/51

    A. El Mossadeq Analyse Combinatoire

    Daprs le principe des bergers, on a :

    card G (A; B) = [n (p 1)] card G (A1; B)

    = n!

    (n p)!

    Corollaire 1

    Le nombre depermutations ou bijections dun ensembleA de cardinaln, notP(A), est :

    P(A) =n!

    5. Parties dun Ensemble

    Proposition 5

    SoitB un ensemble ni de cardinaln.Le nombre de parties deB ayantp lments, p n, est :

    C(n; p) = n!

    p! (n p)!

    Preuve 5

    SoitA = f1; : : ;pg, soitG (A; B)lensemble des injections de A dansB , et soit

    Elensemble des parties de B p lments.Lapplication :

    G (A; B) ! E

    f 7! f(f1;:::;pg)

    est surjective. De plus, pour toute partie X2 E, le cardinal de limage rciproquedeXpar,1 (X), estp!puisquil existep! bijections deA surX, et doncp!injections deA dansB:

    6

  • 5/19/2018 Analyse Combinatoire

    11/51

    Analyse Combinatoire A. El Mossadeq

    Il en rsulte, daprs le principe des bergers, que :

    card G (A; B) =p!C(n; p)

    do :

    C(n; p) = n!

    p! (n p)!

    6. Arrangements

    Proposition 6

    SoitA un ensemble de cardinaln.On appelle arrangement dordre p de A, toute suite ordonne de p lmentsdistincts choisis parmi les lments deA:Le nombre darrangements dordrep deA, notA(n; p) est :

    A(n; p) =

    n!

    (n p)!

    Preuve 6

    SoitAlensemble des arrangements dordre p deAet soit G (A; B) lensembledes injections deA dansB .Lapplication :

    G (A; B) ! A

    f 7! (f(1) ;:::;f(p))

    est bijective, donc :

    A(n; p) = card G (A; B)

    = n!

    (n p)!

    7

  • 5/19/2018 Analyse Combinatoire

    12/51

    A. El Mossadeq Analyse Combinatoire

    Exemple 3

    Combien dquipes direntes de football (onze joueurs) peut-on former avec les

    36 lves dune classe en tenant compte de la place des joueurs ?Si lon tient compte de la place des joueurs, le nombre dquipes direntes est

    le nombre darrangements de onze lments parmi les 36 lves de la classe,

    savoir :

    A (36; 11) = 36!

    (36 11)!=

    36!

    25!

    7. Combinaisons

    Proposition 7

    SoitA un ensemble n lments.On appelle combinaison dordrep deA, toute suite non ordonne dep lmentsdistincts choisis parmi les lments deA.

    Le nombre de combinaisons dordrep deA, notC(n; p) est :

    C(n; p) = n!

    p! (n p)!

    Preuve 7

    Dsignons parC lensemble des combinaisons dordrep deA:Lapplication':

    A ! C (a1;:::;ap) 7! fa1;:::;apg

    est surjective. De plus le cardinal de limage rciproque par ' de tout lmentX deCestp! :

    card '1 (X) =p!

    car tant donne une combinaison dordre p deA, le nombre de suite ordonnedep lments distincts quon peut construire, partir de cette combinaison, est

    8

  • 5/19/2018 Analyse Combinatoire

    13/51

    Analyse Combinatoire A. El Mossadeq

    le nombre de permutations de p lments, savoirp!.Il en rsulte, daprs le principe des bergers, que :

    cardA = p!cardC

    do :

    C(n; p) = n!

    p! (n p)!

    Exemple 4

    Combien dquipes direntes de football (onze joueurs) peut-on former avec les

    36 lves dune classe sans tenir compte de la place des joueurs ?

    Si lon ne tient pas compte de la place des joueurs, le nombre dquipes direntes

    dans ce cas est le nombre de combinaisons de onze lments parmi les 36 lves

    de la classe, savoir :

    C(36; 11) = 36!

    11! 25!= 600 805 296

    8. Permutations avec Rptition

    Proposition 8

    SoitE=fa1;:::;ang un ensemble n lments.On appelle permutation avec rptition dordre (p1;:::;pn) de E, toute suiteordonne des lments deE, o llmentai est rptpi fois, 1 i n.Le nombre de ces permutations quon noteP(p1;:::;pn), est :

    P(p1;:::;pn) = p!

    p1!:::pn!

    o :

    p= p1+::: +pn

    9

  • 5/19/2018 Analyse Combinatoire

    14/51

    A. El Mossadeq Analyse Combinatoire

    Preuve 8

    Le nombre de manires pour placer llment a1 dansp1 positions de la suite est

    le nombre de combinaisons dordre p1 dep lments : C(p; p1):Pour a2, il y a C(p p1; p2) manires possibles,...Pour ak, il y a C(p p1 ::: pk1; pk) manires possibles.Do :

    P(p1;:::;pn) =nY

    k=1

    C(p p1 ::: pk1; pk)

    = p!

    p1!:::pn!op0= 0

    Exemple 5

    Combien danagrammes peut-on former avec les lettres du mot OIGNON ?

    Le nombre de ces anagrammes est le nombre de permutations dordre 6 avec lesrptitions (2; 2; 1; 1), savoir :

    P(2; 2; 1; 1) = 6!2!2!1!1!

    = 180

    9. Combinaisons avec Rptition

    Proposition 9

    SoitE=fa1;:::;ang un ensemble n lments.On appelle combinaison avec rptition dordrep deE, toute suite non ordonnedes lments deEde longeurp.Le nombre de ces combinaisons quon noteK(n; p) est :

    K(n; p) =C(n+p 1; p)

    10

  • 5/19/2018 Analyse Combinatoire

    15/51

    Analyse Combinatoire A. El Mossadeq

    Preuve 9

    On admet que le nombre de combinaisons avec rptition dordre pdenlments

    est :

    K(n; p) =C(n+p 1; p)

    Exemple 6

    SoitE=fa;b;cg :Dterminer les combinaisons avec rptition deE dordre1,2 et3.

    (i) Les combinaisons avec rptition de E dordre1 sont :

    a ; b ; c

    (ii) Les combinaisons avec rptition de E dordre2 sont :

    aa ; bb ; cc ; ab ; ac ; bc

    (iii) Les combinaisons avec rptition deE dordre3 sont :

    aaa ; bbb ; ccc ; aab ; aac ; abb ; acc ; bbc ; bcc ; abc

    11

  • 5/19/2018 Analyse Combinatoire

    16/51

    A. El Mossadeq Analyse Combinatoire

    10. Exercices

    Exercice 1

    SoitAetB deux ensembles et fune application de AdansB.On suppose queB est ni de cardinal n et que pour tout y dansB, le cardinalde limage rciproque dey parf,f1 (fyg), est gal un entier non nul p.

    1. Montrer quef est surjective.

    2. Soit Rla ralation dquivalence associe f.Montrer queA=RetB sont quipotents.

    3. En dduire le cardinal de A.

    Solution 1

    1. Par hypothse, le cardinal def1 (fyg) est non nul pour tout y dansB .

    Doncf1

    (fyg) est non vide pour touty dansB, do la surjection de f :2. Daprs la dcomposition canonique de f,A=Retf(A) sont quipotents.

    Orfest surjective, doncf(A) =B , et par consquentA=Ret B ont mme

    cardinal.

    3. Pour tout x2 A;dsignons parC(x) la classe dquicalence de x modulo R.

    On a :

    C(x) = fy2A j xRyg

    = fy2A j f(x) =f(y)g

    =

    y2A j y 2f1 (ff(x)g)

    = f1 (ff(x)g)

    On en dduit queC(x) a pour cardinal p pour tout x2 A.

    Soit alors x1;:::;xn un systme de reprsentants des classes dquivalence

    modulo la relation dquivalence R.

    12

  • 5/19/2018 Analyse Combinatoire

    17/51

    Analyse Combinatoire A. El Mossadeq

    CommeC(x1) ;:::;C(xn) forment une partion de A, on a :

    card A=

    nXk=1

    card C(xk) =np

    Exercice 2

    Soit A et B deux ensembles de cardinaux respectifs n et p, et dsignons parF(A; B) lensemble des applications deAdansB.

    1. Dterminer le nombre dapplications de A dansB pourn= 1 etn= 2.

    2. Soita2 A etA1= A fag.

    Montrer queF(A; B) etF(A1; B) F(fag ; B) sont quipotents.

    3. En dduire, par un raisonnement par rcurrence, le nombre dapplications de

    AdansB.

    Solution 21. n = 1 : pour dnir une application de A = fag dans B, il sut de

    dnir limage dea dansB:

    Il y a p possibilits, doncp applications deAdansB.

    n = 2 : pour dnir une application de

    A= fa; bg !B

    il sut de dnir les images a etb dansB:

    Pour chacun deux, il y a p possibilits, donc p2 applications de A dans

    B.

    2. Considrons lapplication:

    F(A; B) ! F(A1; B) F(fag ; B)

    f 7!

    fjA1; fjfag

    13

  • 5/19/2018 Analyse Combinatoire

    18/51

    A. El Mossadeq Analyse Combinatoire

    ofjA1 etfjfag reprsentent les restrictions def A1 etfagrespectivement,

    est une bijection.3. Il sen suit que :

    cardF(A; B) = card [F(A1; B) F(fag ; B)]

    = cardF(A1; B) cardF(fag ; B)

    = p cardF(A1; B)

    Par un raisonnement par rcurrence surn,n 1, on conclut que :

    cardF(A; B) =pn

    Exercice 3

    SoitEun ensemble de cardinal ni n etP(E)lensemble de toutes ses parties.

    1. Soitf deE dansf0; 1g une application.

    Montrer quil existe une partie uniqueAdans P(E)telle quefsoit la fonction

    caractristique deA.

    2. En dduire, en utilisant Exercice 2., le cardinal de P(E).

    Solution 3

    1. Soit f :E! f0; 1gune application.

    A= f1 (f1g)est lunique partie deEtelle quefsoit la fonction caractris-

    tiqueA deA.

    2. Lapplication :

    P(E) ! F(E; f0; 1g)

    A 7! A

    o F(E; f0; 1g) est lensemble des applications de E dans f0; 1g, est une

    bijection.

    14

  • 5/19/2018 Analyse Combinatoire

    19/51

    Analyse Combinatoire A. El Mossadeq

    On en dduit que :

    cardP(E) =cardF(E; f0; 1g) = 2n

    Exercice 4

    SoitAetB deux ensembles de cardinaux respectifsp etn,p n.

    1. Dterminer le nombre dapplications injectives deA dansB pourp = 1; 2:

    2. Soit a 2 A, A1 = A fag et G (resp.G1) lensemble des injections de A

    (resp. A1) dansB .Montrer que si g est une injection de A1 dans B, alors lapplication f deA

    dans B qui x 2 A1 associe g (x) et a associe un lment arbitraire de

    B g (A1) est une injection.

    3. En dduire que lapplication qui f 2 G associe la restriction de f A1

    est une application surjective sur G1, et que pour tout g 2G1, le cardinal de

    limage rciproque deg parestn p + 1.

    4. Dterminer par rcurrence sur p, le nombre dinjections de A dansB.

    5. On supposen = p.

    En dduire le nombre de bijections de A dansB.

    Solution 4

    1. p = 1

    Toute application de A = fag dans B est une injection. Donc, il y a ninjections defag dansB:

    p = 2

    Pour le premier lment a de A = fa; bg il y a n possibilits alors que

    pour le deuximeb il ny a que(n 1)possibilits puisque son image doit

    tre dirente de celle de a.

    Donc, le nombre dinjections de fa; bg dansB estn (n 1).

    15

  • 5/19/2018 Analyse Combinatoire

    20/51

    A. El Mossadeq Analyse Combinatoire

    2. Soit :

    g:A1!B

    une injection.

    Pour touty 2B g (A1), lapplicationfy qui coincide avecg surA1 et telle

    que :

    fy(a) =y

    est une injection.

    De plus :

    g=fyjA1

    On peut construire ainsi (n p + 1) aplications injectives : autant que le

    cardinal deB g (A1).

    3. Daprs la question 2, lapplication:

    G ! G1

    f 7! fjA1

    est surjective, de plus pour tout g2G1 on a :

    card1 (fgg) =n p+ 1

    Il sen suit que :

    card G= (n p + 1) card G1

    4. En utilisant le thorme des Bergers, on conclut, par une rcurrence sur p,

    p 1, que :

    card G= n!

    (n p)!

    5. Lorsquen= p, toute injection est une bijection.

    Il y a donc n! bijections deA surB.

    16

  • 5/19/2018 Analyse Combinatoire

    21/51

    Analyse Combinatoire A. El Mossadeq

    Exercice 5

    On appelle arrangement dordre p de A, toute suite ordonne de p lments

    distincts choisis parmi les lments deA.

    1. Montrer que lensemble des arrangements dordre p de A est quipotent

    lensemble des injections def1;:::;pg dansA.

    2. En dduire le nombre darrangements dordre p deA, notA(n; p).

    3. En dduire le nombre de permutationsdeA(arrangements dordren de A),

    notP(n):

    Solution 5

    1. Soit(a1;:::;ap) un arrangement dordre p deA.

    Lapplicationf :

    f1;:::;pg ! A

    i 7! ai

    est une injection.

    Rciproquement, si :

    f :f1;:::;pg !A

    est une injection, alors (f(1) ;:::;f(p)) est un arrangement dordre p deA.

    2. On en dduit que le nombre darrangements dordre p deA concide avec le

    nombre dinjections de f1;:::;pg dansA; do :

    A(n; p) = n!

    (n p)!

    3. En particulier, le nombre de permutations de A coincide avec le nombre de

    bijections deA, savoir :

    P(n) =n!

    17

  • 5/19/2018 Analyse Combinatoire

    22/51

    A. El Mossadeq Analyse Combinatoire

    Exercice 6

    SoitAun ensemble n lments.

    On appellecombinaisondordrepdeA, toute suite non ordonne deplmentsdistincts choisis parmi les lments deA.

    1. Quelle est le nombre darrangements quon peut associer une combinaison

    dordre p deA?

    2. En dduire le nombre de combinaisons dordre p deA, notC(n; p).

    Solution 6

    1. Etant donne une combinaison dordre p de A, le nombre de suite ordonne

    dep lments distincts quon peut construire, partir de cette combinaison,

    est le nombre de permutations de p lments, a savoirp!.

    2. Ainsi, chaque combinaison dordrep de A correspondp!arrangements dordre

    p deA, donc :

    A(n; p) =p!C(n; p)

    do :

    C(n; p) = n!

    p! (n p)!

    Exercice 7

    Soitaun lment de E.Dterminer le nombre de sous-ensembles de Ede cardinal p : qui contiennenta qui ne contiennent pas aEn dduire :

    C(n; p) =C(n 1; p 1) + C(n 1; p)

    18

  • 5/19/2018 Analyse Combinatoire

    23/51

    Analyse Combinatoire A. El Mossadeq

    Solution 7

    Le nombre de sous-ensembles deEde cardinalp qui contiennenta est le nom-

    bre de parties (p 1) lments deE fag, savoir :

    C(n 1; p 1) = (n 1)!

    (p 1)!(n p)!

    Le nombre de sous-ensembles deEde cardinal p qui ne contiennent pasa estle nombre de parties p lments de E fag, savoir :

    C(n 1; p) =

    (n 1)!

    p! (n p 1)!

    Or toute partie deEp lments soit elle contient a soit elle ne le contient pas,on en dduit donc :

    C(n; p) =C(n 1; p 1) + C(n 1; p)

    Exercice 8

    SoitAun ensemble n lments.

    1. Quelle est le nombre de partie de Ap lments ?

    2. En dduire le cardinal de P(A).

    Solution 8

    1. Le nombre de partie de A p lments est le nombre de combinaisons dordre

    p deA

    2. Notons C (n; p) lensemble des lments de P(A) ayantp lments.

    [C (n; p)]0pn forment une partition de P(A) do :

    19

  • 5/19/2018 Analyse Combinatoire

    24/51

    A. El Mossadeq Analyse Combinatoire

    cardP(A) =

    nXp=0

    card C (n; p)

    =nX

    p=0

    C(n; p)

    = (1 + 1)n

    = 2n

    Exercice 9

    1. Montrer que :

    C(n; p) =C(n; n p)

    2. En dduire que :

    C(n; n) =C(n; 0)

    3. En dduire que :

    C(2n; n) = 2C(2n 1; n) = 2C(2n 1; n 1)

    4. En utilisant les dveloppements de (1 1)n et(1 + 1)n, calculer :X

    fC(n; p)j 0 p n ; p pairg

    et :

    X fC(n; p)j 0 p n ; p impairg

    Solution 9

    1. SoitEun ensemble n lments.

    A toute partie de E p lments correspond une et une seule partie de E

    (n p) lments qui est son complmentaire, do :

    C(n; p) =C(n; n p)

    20

  • 5/19/2018 Analyse Combinatoire

    25/51

    Analyse Combinatoire A. El Mossadeq

    2. En particulier :

    C(n; n) =C(n; n n) =C(n; 0) = 1

    Lunique partie deEn lments estE.

    Lunique partie deE qui ne contient aucun lment est lensemble vide ?.

    3. Puisque:

    C(n; p) =C(n 1; p 1) + C(n 1; p)

    et :

    C(n; p) =C(n; n p)

    alors :

    C(2n; n) = C(2n 1; n 1) + C(2n 1; n)

    = 2C(2n 1; n 1)

    = 2C(2n 1; n)

    4. En utilisant la formule du binme on a :

    (1 + 1)n =

    nXp=0

    C(n; p)

    et :

    (1 1)n =n

    Xp=0

    (1)np C(n; p)

    =

    nXp=0

    (1)np C(n; n p)

    =nX

    p=0

    (1)p C(n; p)

    21

  • 5/19/2018 Analyse Combinatoire

    26/51

    A. El Mossadeq Analyse Combinatoire

    En faisant la somme et la dirence de ces deux quantits, on obtient :

    2n = 2X

    fC(n; p)j 0 p n ; p pairg

    et :

    2n = 2X

    fC(n; p)j 0 p n ; p impairg

    do :

    XfC(n; p)j 0 p n ; p pairg =

    XfC(n; p)j 0 p n ; p impairg

    = 2n1

    Exercice 10

    SoitE=fa1;:::;ang un ensemble n lments.On appellepermutation avec rptition dordre(p1;:::;pn)deE, toute suiteordonne des lments de E, o llment ai est rpt pi fois,1 i n.

    Dterminer le nombre de ces permutations quon note P(p1;:::;pn) :

    Solution 10

    Le nombre de manires pour placer llment a1 dansp1 positions de la suite estle nombre de combinaison dordre p1 parmi p lments : C(p; p1):

    Pour a2, il y a C(p p1; p2) manires possibles,...Pour ak, il y a C(p p1 ::: pk1; pk) manires possibles.

    Do :

    P(p1;:::;pn) =nY

    k=1

    C(p p1 ::: pk1; pk)

    = p!

    p1!:::pn!

    op0= 1 etp = p1+::: +pn:

    22

  • 5/19/2018 Analyse Combinatoire

    27/51

    Analyse Combinatoire A. El Mossadeq

    Exercice 11

    SoitE=fa1;:::;ang un ensemble n lments.

    On appelle combinaison avec rptition dordre p de E, toute suite nonordonne des lments de Ede longeurp.Dterminer le nombre de ces combinaisons quon note K(n; p).

    Solution 11

    On dmontre que le nombre de combinaisons avec rptition dordre p de nlments est :

    K(n; p) =C(n+p 1; p)

    Exercice 12

    1. Dterminer le nombre dapplications strictement croissantes def1;:::;pgdans

    f1;:::;ng

    2. Dterminer le nombre dapplications croissantes de f1;:::;pg dansf1;:::;ng.

    3. Dterminer le nombre de solutions de lquation :nXi=1

    xi=p ; p2 N ; xi2 N

    4. Dterminer le nombre de solutions de linquation :nXi=1

    xip ; p2 N ; xi2 N

    Solution 12

    1. Dmontrons que le nombre dapplications strictement croissantes de f1; : : ;pg

    dans f1; : : ;ng est gal au nombre de combinaisons dordre p def1; : : ;ng,

    savoir :

    C(n; p) = n!

    p! (n p)!

    23

  • 5/19/2018 Analyse Combinatoire

    28/51

    A. El Mossadeq Analyse Combinatoire

    En eet, si :

    f :f1;:::;pg ! f1;:::;ng

    est une application strictement croissante, alors(f(1) ;:::;f(p))est une com-

    binaison dordrep def1;:::;ng.

    Rciproquement, soit fa1;:::;apg une combinaison dordre p def1;:::;ng et

    soit une permutation de f1;:::;pg telle que :

    a(1)< a(2)< ::: < a(p)

    Lapplicationf :

    f1;:::;pg ! f1;:::;ng

    k 7! a(k)

    est strictement croissante.

    Do le rsultat.

    2. Dmontrons que le nombre dapplications croissantes de f1;:::;pg dans f1;:::;ng

    est gal au nombre de combinaisons avec rptition dordre pdef1;:::;ng,

    savoir :

    K(n; p) = C(n+p 1; p)

    = (n+p 1)!

    p!(n 1)!

    En eet, si :

    f :f1;:::;pg ! f1;:::;ng

    est une application croissante, alors(f(1) ;:::;f(p))est une combinaison avec

    rptition dordrep def1;:::;ng.

    Rciproquement, soit fa1;:::;apg une combinaison avec rptition dordre p

    24

  • 5/19/2018 Analyse Combinatoire

    29/51

    Analyse Combinatoire A. El Mossadeq

    def1;:::;ng et soit une permutation de f1;:::;pg telle que :

    a(1)a(2)::: a(p)

    Lapplicationf :

    f1;:::;pg ! f1;:::;ng

    k 7! a(k)

    est croissante.

    Do le rsultat.

    3. Dmontrons que le nombre de solutions de lquation :nXi=1

    xi=p ; p2 N ; xi2 N

    est le nombre de combinaisons avec rptition dordre p def1;:::;ng, cest

    dire :

    K(n; p) = C(n+p 1; p)

    = (n+p 1)!

    p!(n 1)!

    En eet, si (x1;:::;xn) est une solution de cette quation, alors la suite dans

    laquelle llment 1 est rpt x1 fois, ..., llment n est rpt xn fois est

    une combinaison avec rptition dordre p def1;:::;ng.

    Rciproquement, soit fa1;:::;apg une combinaison avec rptition dordre p

    def1;:::;ng et dsignons par xi le nombre de rptition de llment i dans

    cette combinaison; on a alors :nXi=1

    xi=p

    (x1;:::;xn) est donc une solution de lquation.

    Do le rsultat.

    25

  • 5/19/2018 Analyse Combinatoire

    30/51

    A. El Mossadeq Analyse Combinatoire

    4. Remarquons que linquation :nXi=1

    xip ; p2 N ; xi2 N

    est quivalente :

    9xn+12 N :n+1Xi=1

    xi=p

    Il en rsulte que le nombre de solutions de linquation est gal au nombre de

    solutions de lquation :

    n+1Xi=1

    xi=p ; p2 N ; xi2 N

    savoir :

    K(n+ 1; p) =C(n+p; p)

    Exercice 13

    Combien de plaques minralogiques portant un matricule de sept caractres peut-

    on former si les trois premiers sont des lettres et les quatre derniers sont des

    chires ?

    Solution 13

    Pour chaque lettre, il y a26possibilits, alors quil y a10possibilits pour chaque

    chire.Ainsi, le nombre de plaques minralogiques quon peut former est :

    263 104

    Exercice 14

    A partir dun groupe de cinq hommes et sept femmes, combien de comits dif-

    frents composs de deux hommes et trois femmes peut-on former ?

    26

  • 5/19/2018 Analyse Combinatoire

    31/51

    Analyse Combinatoire A. El Mossadeq

    Quen est-il si deux des hommes sentendent mal et refusent de siger ensemble

    au comit ?

    Solution 14

    Pour le choix des trois femmes il y a C(7; 3) possibilits et pour celui des

    hommes il y aC(5; 2).

    On en dduit que le nombre total de comits quon peut ainsi former est :

    C(7; 3) C(5; 2) = 350

    Les deux hommes ne peuvent siger ensemble, donc soit lun seulement sige

    dans le comit, soit aucun des deux ne sige dans le comit.

    Le nombre de choix des hommes dans le premier cas est :

    C(2; 1) C(3; 1) = 6

    dans le second cas, le nombre de choix des hommes est :

    C(2; 0) C(3; 2) = 3

    Ainsi, le nombre de choix des deux hommes est :

    C(2; 1) C(3; 1) + C(2; 0) C(2; 2) = 9

    et par suite, le nombre de comits quon peut ainsi former est :

    C(7; 3) [C(2; 1) C(3; 1) + C(2; 0) C(2; 2)] = 315

    On peut aussi procder en dnombrant les comits o les deux hommes sigentensemble soit :

    C(7; 3) [C(2; 2) C(3; 0)] = 35

    Do, le nombre de comit recherch est :

    350 35 = 315

    27

  • 5/19/2018 Analyse Combinatoire

    32/51

    A. El Mossadeq Analyse Combinatoire

    Exercice 15

    Un cours de Calcul des Probabilits est suivi par six femmes et quatre hommes.

    Un examen a lieu, puis les tudiants sont classs selon leurs notes.On suppose exclu que deux tudiants obtiennent la mme note.

    1. Combien de classements dirents peut-on envisager ?

    2. Si les femmes sont classes entre elles uniquement et les hommes entre eux,

    combien de classements globaux peut-on envisager ?

    Solution 15

    1. Le nombre de classements possibles est le nombre de permutations dordre 10,

    savoir :

    10! = 3628800

    2. Le nombre de classements des femmes est 6! et celui des hommes est 4!.

    Il en rsulte que le nombre de classements globaux est :

    4! 6! = 17280

    Exercice 16

    Parmi les dix participants un tournoi dchec, on compte quatre russes, trois

    amricains, deux anglais et un franais.

    Si dans le classement du tournoi on ne peut lire que la liste des nationalits des

    joueurs mais pas leur identit, combien de classements individuels correspond

    une telle liste ?

    Solution 16

    Etant donn un classement par nationalit, il y a 4! possibilits pour classserindividuellement les quatre russes, 3! pour les trois amricains, 2! pour les deuxanglais et une seule possibilit pour le franais.

    28

  • 5/19/2018 Analyse Combinatoire

    33/51

    Analyse Combinatoire A. El Mossadeq

    Donc, le nombre de classents individuels qui correspondent un classement par

    nationalit est :

    4! 3! 2! 1! = 288

    Notons que le nombre de classements individuels est :

    P(10) = 10!

    et le nombre de classements par nationalit est le nombre de permutations avec

    les rptitions(4; 3; 2; 1)

    :

    P(4; 3; 2; 1) = 10!

    4! 3! 2! 1!= 12 600

    Exercice 17

    Douze personnes ont leur disposition trois voitures de six, quatre et deux places

    respectivement.

    De combien de manires peut-on aecter ces douze personnes aux trois voituresen supposant :

    1. que nimporte laquelle de ces personnes est susceptible de conduire ?

    2. que seulement quatre des douze personnes sont susceptibles de conduire ?

    Solution 17

    1. Puisque nimporte laquelle de ces personnes est susceptible de conduire, lenombre de manires de rpartir les douze personnes sur les trois voitures est

    le nombre de permutations dordre 12 avec les rptitions6,4 et2, savoir :

    P(6; 4; 2) = 12!

    6!4!2!= 13860

    29

  • 5/19/2018 Analyse Combinatoire

    34/51

    A. El Mossadeq Analyse Combinatoire

    2. Si seulement quatre des douze personnes sont susceptibles de conduire, alors

    il faut dabord choisir trois personnes parmi ces quatre et les aecter aux troisvoitures en tant que conducteurs, puis rpartir les neuf personnes restanta-

    ntes sur les trois voitures. Ainsi, le nombre de possibilits pour choisir les

    conducteurs est :

    A (4; 3) = 24

    et le nombre de manires pour rpartir les neuf personnes sur les trois voitures

    est gal au nombre de permutations dordre 9 avec les rptitions 5,3 et1,

    savoir :

    P(5; 3; 1) = 9!

    5!3!1!= 504

    Finalement, le le nombre de manires de rpartir, dans ce cas, les douze per-

    sonnes sur les trois voitures est :

    A (4; 3) P(5; 3; 1) = 12096

    Exercice 18

    Un ascenseur desservantN tages contient Spersonnes.

    1. De combien de manires les Spersonnes peuvent-elles sarrter aux dirents

    tages ?

    2. De combien de manires les Spersonnes peuvent-elles sarrter aux direntstages si :

    il y an1 tages tels quen chacun deux sarrtent a1 personnes,

    il y ani tages tels quen chacun deux sarrtent ai personnes,

    il y ank tages tels quen chacun deux sarrtent ak personnes,

    o :

    n1+n2+::: +nk=N

    30

  • 5/19/2018 Analyse Combinatoire

    35/51

    Analyse Combinatoire A. El Mossadeq

    Solution 18

    1. Chacune des Spersonnes a Nchoix possibles pour sarrter, donc le nombre

    de manires possibles estNS, cest le nombre dapplications dun ensemble

    Slments dans un ensemble N lments.

    2. Le nombre de personnes Sscrit :

    S=n1a1+n2a2+::: +nkak

    Le nombre de manires pour rpartir les tages est le nombre de permutations

    dordre Navec les rptitions n1; n2;:::;nk savoir :

    P(n1; n2;:::;nk) = N!

    n1!n2!:::!nkLe nombre de manire pour rpartir lesSpersonnes est le nombre de permu-

    tations dordreSavec les rptitionsa1 (n1 fois), ...,ak (nk fois) savoir :

    P(a1;:::;a1;:::;ak;:::;ak) = S!(a1!)n1 ::: (ak!)

    nk

    Ainsi, mle nombre total de possibilits est :

    P(n1; n2;:::;nk) P(a1;:::;a1;:::;ak;:::;ak) = N!S!

    n1!n2!:::!nk(a1!)n1 ::: (ak!)

    nk

    Exercice 19Une personne dispose de vingt mille dirhams investir sur quatre placements

    potentiels. Chaque mise doit se monter un nombre entier de milliers de dirhams.

    Entre combien de stratgies dinvestissement cette personne a-t-elle le choix si

    elle dcide de risquer la totalit de la somme ?

    Quen est-il si on admet que la personne nest pas oblige dinvestir la totalit

    de la somme ?

    31

  • 5/19/2018 Analyse Combinatoire

    36/51

    A. El Mossadeq Analyse Combinatoire

    Solution 19

    Soit xi, 1 i 4, la somme, en milliers de dirhams, investie dans le ieme

    placements.

    Le nombre de stratgies possibles est donc gal au nombre de solutions de

    lquation :4X

    i=1

    xi = 20; xi2 N ; 1 i 4

    savoir :

    K(4; 20) = C(23; 20)

    = 1771

    Dans le cas o la personne nest pas oblige dinvestir la totalit de la somme,

    le nombre de stratgies possibles est donc gal au nombre de solutions de

    linquation :

    4

    Xi=1

    xi20 ; xi2 N ; 1 i 4

    savoir :

    K(5; 20) = C(24; 20)

    = 10626

    Exercice 20

    On achte six pices mcaniques. De combien de manires peut-on les rpartir

    si :

    1. elles doivent tre places chacune dans un atelier dirent ?

    2. elles sont places deux deux dans trois ateliers dirents ?

    3. il y a quatre ateliers, deux recevant deux pices chacun et deux autres une

    pice chacun ?

    32

  • 5/19/2018 Analyse Combinatoire

    37/51

    Analyse Combinatoire A. El Mossadeq

    Solution 20

    1. Le nombre de manires de rpartir les six pices mcaniques, chacune dans un

    atelier dirent, est le nombre de permutations dordre 6:

    6! = 720

    2. Le nombre de manires de rpartir les six pices mcaniques, deux deux

    dans trois ateliers dirents, est le nombre de permutations dordre 6 avec les

    rptitions (2; 2; 2) :

    P(2; 2; 2) = 6!2! 2! 2!

    = 90

    3. Le nombre de manires de rpartir les six pices mcaniques sur quatre ate-

    liers dirents , deux recevant chacun deux pices et les deux autres recevant

    chacun une seule pice, est le nombre de permutations dordre 6 avec les

    rptitions (2; 2; 1; 1) :

    P(2; 2; 1; 1) = 6!

    2! 2! 1! 1!= 180

    Exercice 21

    Quel est le nombre de monmes de lensemble des polynomes homognes n

    variables de degrp ?

    Solution 21

    Un monme de lensemble des polynomes homognes n variables et de degrp scrit sous la forme :

    X11 X22 :::X

    nn

    33

  • 5/19/2018 Analyse Combinatoire

    38/51

    A. El Mossadeq Analyse Combinatoire

    o :

    8