Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



DENOMBREMENT .pdf



Nom original: DENOMBREMENT.pdf
Titre: C:/COURS Marielle/COURS/denombrement.dvi

Ce document au format PDF 1.4 a été généré par dvips(k) 5.98 Copyright 2009 Radical Eye Software / GPL Ghostscript 8.61, et a été envoyé sur fichier-pdf.fr le 15/01/2012 à 12:41, depuis l'adresse IP 41.140.x.x. La présente page de téléchargement du fichier a été vue 1807 fois.
Taille du document: 92 Ko (7 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


D´enombrement
1

Notion d’ensemble

´finition
De
Un ensemble est une collection d’´el´ements ayant en commun une propri´et´e qui les caract´erise.
D´efinir un ensemble, c’est pouvoir affirmer sans ambiguit´e qu’un ´el´ement appartient ou non `a cet ensemble.
Remarque : La description d’un ensemble se fait toujours entre accolades.
Exemples :
– L’ensemble des entiers pairs peut se d´ecrire {0, 2, 4, 6, ...} ou encore {n ∈ N | n pair} ou encore
{2n, n ∈ N}.
– L’ensemble des couleurs d’un jeu de carte s’´ecrit { coeur, carreau, pique, tr`efle}.
– {3 poires, 3 chaussures, 3 nombres, 3 phrases, ... } est ´egalement un ensemble : la propri´et´e commune
`a ses ´el´ements, est d’ˆetre au nombre de trois.
Certains ensembles peuvent ˆetre compar´
es :
Inclusion :
Un ensemble A est inclus dans un ensemble B si tout ´el´ement de A est ´el´ement de B.
On le note A ⊂ B.
Exemple : l’ensemble des entiers pairs est inclus dans N.
Egalit´
e:
Deux ensembles A et B sont ´egaux lorsque A ⊂ B et B ⊂ A. On le note alors A = B.

2

Op´
erations sur les ensembles
1. Intersection :
L’intersection des ensembles A et B not´ee A ∩ B, est d´efinie par : x ∈ A ∩ B ⇔ (x ∈ A et x ∈ B)
Si l’on consid`ere 3 ensembles A, B et C : x ∈ A ∩ B ∩ C si x ∈ A et x ∈ B et x ∈ C.
n
Plus g´en´eralement, on d´efinit l’intersection A1 ∩ A2 ∩ ... ∩ An not´ee ∩ Ak par :
k=1

n

x ∈ ∩ Ak ⇔ ∀k ∈ [[1, n]], x ∈ Ak
k=1


egation :
x∈
/ An∩ B ssi x ∈
/ A ou x ∈
/B
x∈
/ ∩ Ak ⇔ ∃k ∈ [[1, n]], tel que x ∈
/ Ak
k=1

2. R´
eunion :
La r´eunion des ensembles A et B not´ee A ∪ B est d´efinie par : x ∈ A ∪ B ⇔ (x ∈ A ou x ∈ B)
Le ou est dit inclusif, car on peut avoir x ∈ A ∩ B.
Si l’on consid`ere 3 ensembles A, B et C : x ∈ A∪B ∪C si x est dans l’un (au moins) des 3 ensembles ;
c’est-`a-dire si x ∈ A ou x ∈ B ou encore x ∈ C. n
Plus g´en´eralement, on d´efinit la r´eunion A1 ∪ A2 ∪ ... ∪ An not´ee ∪ Ak par :
k=1

n

x ∈ ∪ Ak ⇔ ∃k ∈ [[1, n]] tel que x ∈ Ak
k=1


egation :
x∈
/ An∪ B ssi x ∈
/ A et x ∈
/B
x∈
/ ∪ Ak ⇔ ∀k ∈ [[1, k]], x ∈
/ Ak
k=1

R`
egles de calcul : l’intersection et la r´eunion sont distributives l’une sur l’autre
(A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C)
(A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C)
1

3. Compl´
ementaire :
Soit A une partie de E. Le compl´ementaire de A dans E est not´e cA ou A et est d´efini par :
x ∈ A ⇔ (x ∈ E et x ∈
/ A)
R`
egles de calcul
A∪A=E
A=A
A∪B =A∩B
A∩B =A∪B
A∩A=∅
4. Partition :
Deux ensembles A et B sont disjoints si A ∩ B = ∅.
Une famille (A1 , A2 , ..., An ) de parties non vides de E est une partition de E si :
(
n
∪ Ak = E
k=1

∀(i, j) ∈ [[1, n]]2 , avec i 6= j, Ai ∩ Aj = ∅

Par exemple, les ensembles des entiers pairs et impairs A1 = {2n, n ∈ N} et A2 = {2n + 1, n ∈ N}
forment une partition de N.
5. Diff´
erence :
Soient A et B deux parties de E. On note A\B l’ensemble d´efini par : x ∈ A\B ⇔ x ∈ A et x ∈
/ B.
Donc A\B = A ∩ B
Exemple :
On consid`ere l’ensemble E = {0, 1, 2, 3, 4, 5} ainsi que ses sous-ensembles A = {0, 1, 3, 4} et
B = {2, 3, 4}. Alors A ∪ B = {0, 1, 2, 3, 4}, A ∩ B = {3, 4}, A¯ = {2, 5}, A\B = {0, 1}
6. Produit cart´
esien :
Le produit cart´esien de deux ensembles E et F est not´e E × F et est d´efini par :
E × F = {(x, y) avec x ∈ E et x ∈ F }

Plus g´en´eralement le produit cart´esien de n ensembles est :
E1 × E2 × . . . En = {(x1 , x2 , . . . , xn ) avec ∀i ∈ [[1, n]], xi ∈ Ei }

Par d´efinition E 2 = E × E et plus g´en´eralement, E n = E × E × . . . × E (n facteurs ).
Les ´el´ements du produit cart´esien de n ensembles sont appel´es des n-uplets.
Mais si n=2 (resp. n=3), on dit plutˆ
ot des couples (resp. des triplets).
Premier exemple : {0, 1} × {1, 2, 3} = {(0, 1); (0, 2); (0, 3); (1, 1); (1, 2); (1, 3)}
Dans le cas d’un produit cart´esien de 2 petits ensembles, on peut le repr´esenter via un tableau `a double
entr´ees : les lignes correspondent `
a la premi`ere coordonn´ee, et les colonnes `a la deuxi`eme.
0
1

1
(0,1)
(1,1)

2
(0,2)
(1,2)

3
(0,3)
(1,3)

Exemple fondamental : le plan R2 = R × R.
Dans ce plan, un point est repr´esent´e par un couple de coordonn´ees : son abscisse x et son ordonn´ee
y. Vous notiez par exemple le point A(0, 1) : abscisse=0 et ordonn´ee=1. Ce plan est la repr´esentation
graphique du produit cart´esien R × R qui par d´efinition est l’ensemble des couples de r´eels : `a tout point
du plan on associe un couple-ses coordonn´ees- et r´eciproquement.
Autre exemple : l’espace tridimensionnel R3 = R × R × R. Pour d´efinir un point, 3 coordonn´ees sont
n´ecessaires ! Par exemple, le point A(1, 1, −1).
Autres exemples :
– (−3, π) est un ´el´ement de Z × R car −3 ∈ Z et π ∈ R.

1 √
1
Par contre ( , 2) n’est pas un ´el´ement de Z × R car, bien que 2 ∈ R, ∈
/ Z.
2
2
4
– R d´esigne les 4−uplets de la forme (x1 , x2 , x3 , x4 ) o`
u les quatre ´el´ements x1 , x2 , x3 , x4 sont des
nombres r´eels.
2

3

Cardinaux

´finition
De
On dit que l’ensemble E est fini s’il est vide ou s’il existe un entier n et n ´el´ements deux `a deux distincts
e1 , e2 , . . . , en tels que E = {e1 , e2 , . . . , en }.
L’entier n est appel´e le cardinal de E : c’est le nombre d’´el´ements de E.
Il peut ˆetre not´e card(E) ou |E|. Par convention, card(∅) = 0.
Remarque
Le d´
enombrement est l’art de d´eterminer le cardinal d’un ensemble fini (c’est-`a-dire son nombre d’´el´ements)
sans avoir `a faire la liste de tous les ´el´ements de cet ensemble.
Proposition
Soit E un ensemble fini et A un sous-ensemble de E : A ⊂ E.
Alors A est un ensemble fini et card(A) ≤ card(E).
Si de plus, card(A) = card(E), alors A = E.
Remarque
soit A = {2, 3} et E = {3, 5}. On a card(A) = card(E) MAIS A 6= E
Th´
eor`
eme Crible de Poincar´
e
Soient A et B deux sous-ensembles d’un ensemble fini E.
1. Alors A ∪ B et A ∩ B sont des ensembles finis et card(A ∪ B) = card(A) + card(B) − card(A ∩ B).
En particulier si A et B sont disjoints, card(A ∪ B) = card(A) + card(B)
2. Soit C un autre sous-ensemble de E. Alors card(A ∪ B ∪ C)
= card(A) + card(B) + card(C) − card(A ∩ B) − card(A ∩ C) − card(B ∩ C) + card(A ∩ B ∩ C).
En particulier, si les ensembles A, B et C sont deux `a deux disjoints, i.e. A∩B = A∩C = B ∩C = ∅,
card(A ∪ B ∪ C) = card(A) + card(B) + card(C).
C

A

B

3. G´en´eralisation : soient A1 , A2 , ...,An n ensembles deux `a deux disjoints i.e. ∀(i, j) ∈ [[1, n]], i 6= j ⇒
n
n
P
card(Ai )
Ai ∩ Aj = ∅. Alors card( ∪ Ai ) =
i=1

i=1

Th´
eor`
eme
Soient A et B deux sous-ensembles d’un ensemble fini E, F un autre ensemble fini et p un entier. Alors
1. card(A\B) = card(A) − card(A ∩ B).
¯ = card(E) − card(A).
En particulier card(A)
2. E × F est un ensemble fini et card(E × F ) = card(E) × card(F ).
(c’est le nombre de cases du tableau `
a double entr´ee !)
p
Par r´ecurrence, E = E × E × . . . × E est un ensemble fini et card(E p ) = (card(E))p .

4
4.1

p-listes
p-listes g´
en´
erales

´finition
De
On appelle p-liste ou p-uplet d’un ensemble E, tout ´el´ement de E p c’est-`a-dire tout ´el´ement de la forme
(e1 , .., ep ) o`
u pour tout i ∈ {1, ..., p}, ei ∈ E
3

Remarque
1. Les ´el´ements ne sont pas n´ecessairement deux `a deux distincts : des ´el´ements peuvent apparaitre
plusieurs fois. Par exemple, (8, 8, 8), (1, 8, 5) et (7, 5, 7) sont des 3-listes de N
2. Dans une p-liste, l’ordre des ´el´ements est important.
Par exemple, dans le plan R2 le point (0,2) (c’est-`a-dire la deux-liste ou couple (0,2)) n’est pas le
mˆeme que le point (2,0) (si on ´echange l’abscisse et l’ordonn´ee d’un point, on change de point !)
Proposition

Le nombre de p-listes d’un ensemble E `a n ´el´ements est np .


emonstration
Il suffit de remarquer que les p-listes d’un ensemble E `a n ´el´ements forment l’ensemble E p et donc son
cardinal est (card(E))p = np .
Cas typique : on lance un d´e deux fois de suite. Combien de r´esultats diff´erents peut-on obtenir ?
On peut repr´esenter le r´esultat par un couple d’entiers compris entre 1 et 6 : (5,2) signifie que le premier
lancer a donn´e 5 et le deuxi`eme 2.
L’ensemble des r´esultats possibles est donc [[1, 6]] × [[1, 6]] de cardinal 6*6=36.

4.2

Arrangements

Cas typique : le tierc´e.
Le joueur parie sur le premier, le deuxi`eme et le troisi`eme cheval. 2 caract´eristiques :
l’ordre importe entre les chevaux gagnants et les chevaux gagnants sont deux `a deux distincts.
´finition
De
Un p-arrangement d’un ensemble E est une p-liste de E constitu´ee d’´el´ements deux `a deux distincts.
Exemple :
(1, 8, 5) est un 3-arrangement de N. Par contre, (8, 8, 8),et (7, 5, 7) ne sont pas des 3-arrangements de N,
mais sont des 3-listes (ou triplets) de N.
Rappel : factorielle n = n! := 1 × 2 × · · · × n =

n
Q

k et par convention 0! := 1.

k=1

Proposition
Soit E un ensemble `
a n ´el´ements. Si Apn d´esigne le nombre de p-arrangements de E alors
Apn

=





n(n − 1)..(n − p + 1) =
0

p−1
Q

(n − k) =

k=0

n!
(n − p)!

si p ≤ n
si p > n

Esquisse de la preuve : pour la premi`ere coordonn´ee de la p-liste, il n’y a aucune contrainte donc n
possibilit´es. En revanche, afin d’avoir un p-arrangement, la deuxi`eme coordonn´ee doit ˆetre diff´erente de
la premi`ere : il reste donc n − 1 posssibilit´es. Et ainsi de suite, jusqu’`a la pie coordonn´ee qui doit ˆetre
diff´erente des p − 1 coordonn´ees pr´ec´edentes : il reste alors n − (p − 1) = n − p + 1 choix possibles.
Suite du cas typique : vous assistez `
a une course de 15 chevaux. Nombre de tierc´es gagnants ?
3
Il y a A15 =15*14*13 tierc´es gagnants possibles.

4.3

Permutations

C’est le cas particulier p = n.
´finition
De
Soit E un ensemble `
a n ´el´ements. On appelle permutation de E tout n-arrangement de E.
Proposition
Soit E un ensemble `
a n ´el´ements. Alors il y a n! permutations de E.
4

Autrement dit il y a n! fa¸cons de ranger n ´el´ements distincts dans tous les ordres possibles.
Cas typique :
Il y a 4 invit´es et 4 chaises. Combien de choix pour placer les gens ?
On est en pr´esence d’une permutation `
a 4 ´el´ements : il y a donc 4 ! =24 placements possibles.

5

Parties d’un ensemble

5.1

Combinaisons

´finition
De
Soit E un ensemble `
a n ´el´ements. On appelle combinaison de p ´el´ements de E toute partie de E `
a p
´el´ements.
Remarque
1. Les ´el´ements d’une combinaison de p ´el´ements de E sont deux `a deux distincts donc 0 ≤ p ≤ card(E).

2. L’ordre des ´el´ements d’une combinaison n’a pas d’importance.


Exemple S i E = {1; ..; 10} alors {2; 5; 7} = {5; 2; 7} = {7; 5; 2} = ... et {1; 8; 10} sont des combinaisons `
a
3 ´el´ements de E.
Proposition

Soit E un ensemble a
` n ´el´ements. Si Cnp ou np d´esigne le nombre de combinaisons `a p ´el´ements de E
alors

 Apn
n!
n(n − 1) . . . (n − p + 1)
n
=
=
si p ≤ n
=
p!
p!(n − p)!
p!

p
0
si p > n


emonstration
Un arrangement de E est une permutation d’une combinaison de p ´el´ements de E (apr`es avoir choisi les
´el´ements qui vont intervenir dans l’arrangement, il faut les ordonner !). Il y a np fa¸cons de choisir une
combinaison de p ´el´ements de E, puis pour chacune d’entres elles, il y a p! permutations de ses ´el´ements.
Donc Apn = p! np .
Cas typique :
Lors d’un tour de magie, on choisit simultan´ement 3 cartes dans un jeu de 32 cartes.
Nombre de possibilit´es ?
32 ∗ 31 ∗ 30
Le r´esultat est une combinaison de 3 cartes parmi 32 : il y donc 32
possibilit´es.
3 =
3!
Propri´
et´
es :
∀n ∈ N et ∀p ∈ {0; ..; n}, on a




n
n
n
n
p = n−p
0 = n =1

n
1



=

n
n−1



n
p

=n

Preuve : il suffit de revenir `
a la d´efinition !

n!
n!
n
Par exemple, n−p =
=
=
(n − p)!(n − (n − p))!
(n − p)!p!

n
p



=

n
p

n−1
p−1

n
p

+




...

Proposition Triangle de Pascal.
Pour tous n et p deux nombres entiers positifs tels que p ≤ n, on a



n
p+1



=

n+1
p+1



.


emonstration
M´ethode 1 (calculatoire) :


n!
n!
n!
n!
n
n
p + p+1 = p!(n − p)! + (p + 1)!(n − p − 1)! = p!(n − p) × (n − p − 1)! + (p + 1) × p!(n − p − 1)!
5

1
n!
p + 1 + (n − p)
n+1
1
n!
n!
+
=
=
p!(n − p − 1)! n − p p + 1
p!(n − p − 1)! (n − p)(p + 1)
p!(n − p − 1)! (n − p)(p + 1)

(n + 1)!
(n + 1)!
(n + 1)n!
=
=
= n+1
.
=
p+1
(p + 1)p!(n − p)(n − p − 1)!
(p + 1)!(n − p)!
(p + 1)!(n + 1 − (p + 1))!

=

M´ethode 2 (combinatoire) :
Soit E = {a1 , . . . , an+1 } un ensemble
quelconque `a n + 1 ´el´ements. Soit A l’ensemble des parties de E `
a

p + 1 ´el´ements : card(A) = n+1
.
Ces
parties
de
E
a
`
p
+
1
´
e

e
ments
se
regroupent
en
deux
cat´
e
gories
:
p+1
celles qui contiennent l’´el´ement a1 et celles qui ne le contiennent pas.
On notera B (resp. C) le sous-ensemble de A des parties `a p + 1 ´el´ements de E qui contiennent a1 , (resp.
qui ne contiennent pas a1 ). Alors A = B ∪ C et B ∩ C = ∅, donc Card(A) = Card(B) + Card(C).
Il reste `a d´enombrer les ensembles B et C. Or un ´el´ement de B, est une partie `a p ´el´ements de E\{a1 } `
a
laquelle
on
ajoute
a
.
Comme
card(E\{a
})
=
n,
le
nombre
de
choix
d’une
partie
a
`
p
´
e

e
ments
de
E\{a
1
1
1}


n
n
est p . Soit Card(B) = p

n
Puis un ´el´ement de C est une partie `
a p + 1 ´el´ements de E\{a1 } : p+1
choix pour cette combinaison d’o`
u

n
card(C) = p+1
.



n
n
On obtient bien n+1
p+1 = p + p+1 .
n
p

Cette formule permet de calculer les coefficients binomiaux



n
p
n=0
n=1
n=2
n=3
n=4
n=5
..
.

p=0

p=1

p=2

p=3

p=4

1
1
1
1
1
1
..
.

1
2
3
4
5
..
.

1
3
6
10

1
4
10

1
5

n

1

n

n+1

1

n+1

p=5

···

1
..
.

..



pour des petites valeurs de n et p :

p

p+1


...





n
p


n
p+1
n+1
p+1

···
n
P

k=p

k
p



=

n+1
p+1

(on pourra visualiser cette propri´et´e sur le tableau avec n = 4 et p = 1 ou 2)
Th´
eor`
eme Formule du binˆ
ome de Newton.
n
P
Soient a, b deux nombres r´eels et n un entier. Alors on a (a + b)n =

k=0

n
k


emonstration
Faire un raisonnement par r´ecurrence sur n. (laiss´e aux soins du lecteur).
n
P

k=0

n
k


.

n

n+1

.

D’autres propri´et´es relient ces coefficients : par exemple, ∀n ≥ p,

Exemple : calcul de

...





1
n+1

1

.

ak bn−k .

Si pour tout k ∈ [[0, n]], ak = 1 = bk , on reconnaˆıt la formule du binˆ
ome de Newton. Et c’est vrai si
n
n


P
P
n k n−k
n
= (1 + 1)n = 2n .
a = b = 1. D’o`
u
k 1 1
k =
k=0

k=0

6

5.2


enombrement de P(E)

Soit E un ensemble.
On note P(E) l’ensemble des parties de E : un ´el´ement de P(E) est donc une partie de E, appel´ee
´egalement un sous-ensemble de E.
Exemple :
P({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Th´
eor`
eme

Si E est un ensemble `
a n ´el´ements alors card(P(E)) = 2n


emonstration
Notons pour tout k ∈ [[0, n]] Ek l’ensemble des parties de E `a k ´el´ements.

Alors la famille (Ek )0≤k≤n est une partition de P(E) donc card(P(E)) =
Or on a vu que card(Ek ) =

n
k



donc card(P(E)) =

Puis la formule du binˆ
ome de Newton donne

n
P

k=0

n
P

k=0
n
k



n
k



.

= (1 + 1)n = 2n

7

n
P

card(Ek ).

k=0


Documents similaires


Fichier PDF 2p010 cours analyse vectorielle
Fichier PDF denombrement
Fichier PDF cours maths s 09
Fichier PDF espace vectoriel
Fichier PDF 2016 chapitre 3 graphes op rations de base video
Fichier PDF ex ensembles et applications


Sur le même sujet..