Analyse combinatoire (cours) .pdf



Nom original: Analyse combinatoire (cours).pdf

Ce document au format PDF 1.4 a été généré par TeX / pdfTeX-1.11a, et a été envoyé sur fichier-pdf.fr le 13/12/2015 à 11:39, depuis l'adresse IP 41.249.x.x. La présente page de téléchargement du fichier a été vue 844 fois.
Taille du document: 78 Ko (6 pages).
Confidentialité: fichier public


Aperçu du document


ENS
2eme année
Dr. Aicha. Lazraq Khlass

2015-2016

Mathématiques
Chapitre I
Analyse combinatoire
I. Ensembles …nis.
I. 1. Dé…nitions et propriétés élémentaires.
I. 1. 1. Dé…nition.
Soit E un ensemble non vide, on dit que E est …ni si on peut compter ses
éléments. Autrement dit, on dit que E est …ni s’il existe n 2 N et une bijection
de E dans [1; n] = fi 2 N =1 i ng : L’entier n est unique, c’est le cardinal
de E et se note Card(E).
Par convention Card (?) = 0
Un ensemble qui n’est pas …ni est dit in…ni.
.
I. 1. 2. Remarque.
Si E est non vide et …ni, de cardinal n, on peut numéroter ses éléments et
écrire:
E = fxi ; 1
.

i

ng

I. 1. 3. Proposition.
* Soit E un ensemble …ni non vide de cardinal n. Tout ensemble F qui est
en bijection avec E est …ni et de cardinal n:
* Deux ensembles …nis sont de même cardinal si et seulement s’il existe une
bijection de l’un vers l’autre.
.
I. 1. 4. Proposition.
Toute partie A d’un ensemble …ni E est …ni et CardA
CardE: De plus
CardA = CardE si et seulement si A = E:
.
I. 2. Opérations sur les cardinaux.
I. 2. 1. Théorème.
* Soient A et B deux ensembles …nis tels que A \ B = ?, alors A [ B est
…ni et Card(A [ B) = Card(A) + Card(B):
* Soient n 2 N et A1 ; :::; An des ensembles …nis disjoints deux à deux, c’est
à dire :
2

8 (i; j) 2 [1; n] ; i 6= j =) Ai \ Aj = ?
1

Alors A1 [ A2 [ ::: [ An est …ni et :
Card( [ Ai ) =
1 i n

* Soit A

P

Card (Ai )

1 i n

A
E, alors CE
= EnA est …ni et :
A
Card(CE
) = Card(E)

Card(A):

Preuve.
* Soient A et B deux ensembles …nis de cardinaux respectifs n et p non nuls.
On suppose A\B = ?. Soient f : A ! [1; n] et g : B ! [1; p] des bijections.
On dé…nit h : A [ B ! [1; n + p] par :
8x 2 A [ B; h(x) = f (x) si x 2 A; h(x) = n + g(x) si x 2 B
On véri…e que h est une bijection. Donc Card(A [ B) = n + p = Card(A) +
Card(B):
* Par récurrence pour un nombre …ni d’ensemble deux à deux
P disjoints. On
montre la propriété dé…nie pour n 2 par Card( [ Ai ) =
Card (Ai ) :
1 i n

1 i n

A
A
* On a : E = A [ CE
, donc Card(E) = Card(A) + Card(CE
) et par suite
A
Card(CE ) = Card(E) Card(A):
.
I. 2. 2. Proposition.
Soient A et B deux ensembles …nis, alors A \ B est …ni et :

Card(A \ B)

min(Card(A); Card(B)):
.

I. 2. 3. Théorème.
Soient A et B deux ensembles …nis, alors A [ B est …ni et :
Card(A [ B) = Card(A) + Card(B)
.
I. 2. 4. Théorème.
* Soient A et B deux ensembles …nis, alors A
Card(A

B) = Card(A)

Card(A \ B)

B est …ni et :
Card(B)

* Soient n 2 N et A1 ; :::; An des ensembles …nis, alors A1 [ A2 [ ::: [ An est
…ni et :
Q
Q
Card(
Ai ) =
Card (Ai )
1 i n

1 i n

Preuve.
Soient A et B deux ensembles …nis de cardinaux respectifs non nuls n et p:
On a :

2

A = fx1 ; :::; xn g : Le cardinal de Bi = fx
S i g B est égal au cardinal de B:
De plus Bi \ Bj = ? (i 6= j) et A B =
(fxi g B), donc,
1 i n

Card(A B) = nCard(B) = Card(A) Card(B)
.
I. 2. 5. Théorème.
Soient E et F deux ensembles …nis, de cardinaux respectifs p et n (n, p 2
N ): L’ensemble A(E; F ) = F E des applications de E dans F est …ni et :
Card(E)

Card(A(E; F )) = (Card(F ))

:

.
II. Analyse combinatoire.
II. 1. Dé…nition.
Soient E un ensemble de cardinal n 1 et p 2 N . Une p-liste à éléments
dans E est un élément de E p :
.
II. 2. Théorème.
Soient n 2 N et p 2 N : Soit E un ensemble …ni de cardinal n, il y a np
p-listes d’éléments de E.
Preuve.
p
Une p-liste à éléments dans E est un élément de E p et Card(E p ) = (Card(E)) :
D’où le résultat.
.
II. 3. Remarque.
Il y a une notion d’ordre dans une p-liste, la 3-liste (1; 2; 3) est di¤érente de
la 3-liste (3; 2; 1), d’autre part on peut répéter les mêmes éléments, comme par
exemple dans la 3-liste (2; 2; 2) :
.
II. 4. Dé…nition.
Soit E un ensemble …ni et p 2 N: Un p-arrangement d’élément de E est une
p-liste d’éléments distincts de E:
.
II. 5. Théorème.
Soit E un ensemble …ni de cardinal n 2 N et p 2 N : Le nombre des
p-arrangements d’éléments de E; noté, Apn est égal à :
Apn

=

n!
(n p)!

Apn = 0 si n < p
= n(n 1):::(n p + 1) si n

p

Par convention : A0n = 1:
Preuve.
On veut montrer par récurrence sur n la propriété P (n):
Apn =

n!
(n p)!

= n(n

1):::(n

3

p + 1) si n

p

* Si n = 1, p = 1, on a : A11 = 1:
On suppose dans la suite n 2:
- Pour p = 1, il y a n façons de choisir une 1-liste dans E car on choisit un
seul élément, donc A1n = n
On suppose la propriété P (p) est vraie pour un p 2 [1; n 1] et on montre
P (p + 1) est vraie, c’est à dire :
Ap+1
=
n

n!
(n p)!

= n(n

1):::(n

p)

Pour choisir p+1 éléments distincts dans E, on choisit d’abord les p premiers,
il y a donc n(n 1):::(n p+1) choix possibles. Ensuite, il faut choisir le dernier
élément parmi les n p éléments restants. Il y a donc en tout : n(n 1):::(n
p + 1)(n p); choix possibles.
.
II. 6. Remarque.
Soient p et n deux entiers naturels non nuls, Apn est le nombre de façon de
choisir p objets parmi n objets distincts avec ordre.
.
II. 7. Théorème.
Soient E et F deux ensembles …nis de cardinaux non nuls respectifs p et n:
L’ensemble des applications injectives de E dans F est :
* Vide, si n < p:
* Fini de cardinal Apn ; si n p
Preuve.
Soit E de cardinal p et F de cardinal n. Si f : E ! F est injective, alors
card(f (E)) = Card(E):
Donc si n < p, il ne peut pas y avoir d’injection de E vers F .
On suppose p n. On pose E = fx1 ; :::; xp g : On note Inj(E; F ) l’ensembles
des applications injectives de E vers F et Arrp (F ) l’ensemble des p-arrangements
d’éléments de F: Alors, l’application :
Inj(E; F ) ! Arrp (F ) ; f 7 ! (f (x1 ) ; :::; f (xp ))
Est une bijection, donc card(Inj(E; F )) = Card(Arrp (F )) = Apn :
.
II. 8. Corollaire.
Le nombre de bijections d’un ensemble E de cardinal n non nul dans un
ensemble F de même cardinal n est n!.
Preuve.
Comme card(E) = Card(F ) = n, les applications injectives de E vers F
sont exactement les applications bijectives. Donc il ya Ann = n! applications
bijectives.
.
II. 9. Dé…nition.
Soit n 2 N et E un ensemble de cardinal n. On appelle permutation de E
toute bijection de E vers E.

4

.
II. 10. Théorème.
Le nombre des permutations d’un ensemble de cardinal n est exactement n!
.
II. 11. Théorème.
Soit E un ensemble …ni de cardinal n:
Pour tout entier p tel que 0 p n, on note Pp (E), l’ensemble des parties
de E de cardinal p:
n
Pp (E) est …ni, son cardinal est noté
= Cnp et véri…e :
p
n
p
Par convention :

n
p

=

Ap
n
p!

=

n!
p!(n p)!

= 0 si n < p

Preuve.
Si on considère une partie Ep de p éléments de E, on peut écrire p-arrangements
avec ses éléments. Donc quand on énumère les p arrangements de E on cite p!
n
:
fois la même partie, donc Apn = p!
p
.
II. 12. Corollaire.
Le nombre de façons de choisir p objets parmi n objets distincts, sans répin
n
tition et sans tenir compte de l’ordre est
: C’est pour cela que
p
p
se lit "p parmi n". On l’appelle aussi "combinaison de p éléments parmi n"
Preuve.
Choisir p éléments parmi n, sans tenir compte de l’ordre et sans répitition,
c’est exatement choisir une partie de p élément dans l’ensemble E de cardinal
n, donc il y a autant de possibilités d’e¤ectuer le choix d’une telle partie.
.
II. 13. Propriétés.
Pour tous n , m et p 2 N; (p n)on a :
n
n
*
=
p
n p
n
n 1
*
= np
p 1
p
n+1
n
n
*
=
+
(Relation de Pascal)
p+1
p+1
p
P
n
*
= 2n :
k
0 k n
P
k
n+1
*
=
p
p+1
p k n
P
m
n
m+n
*
=
(Formule de Van Der Mond)
k
p
k
p
0 k p
5

* Pour tout couple (a; b) de réels et tout n 2 N, on a la formule du binôme
de Newton :
P
P
n
n
n
(a + b) =
ak bn k =
an k bk
k
k
0 k n
0 k n
.
II. 14. Corollaire.
L’ensemble des parties d’un ensemble E de cardinal n 2 N est …ni de
cardinal 2n :

6


Analyse combinatoire (cours).pdf - page 1/6
 
Analyse combinatoire (cours).pdf - page 2/6
Analyse combinatoire (cours).pdf - page 3/6
Analyse combinatoire (cours).pdf - page 4/6
Analyse combinatoire (cours).pdf - page 5/6
Analyse combinatoire (cours).pdf - page 6/6
 




Télécharger le fichier (PDF)


Analyse combinatoire (cours).pdf (PDF, 78 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


analyse combinatoire cours
td02
ex ensembles relations appliction
denombrement
recherche cardinal quantitatif 18 07 2020 23h56
sec questions

Sur le même sujet..