View
38
Download
3
Category
Preview:
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
Recommended