Cardinalité des ensembles finis PDF

Définition 8 Soit A un ensemble fini. Le cardinal de A noté

Combinatoire et dénombrement

Soient E un ensemble fini et A et B deux parties de E disjointes. Le cardinal de la réunion de A et de B est la somme des cardinaux des parties A et B. ?

COMBINATOIRE ET DÉNOMBREMENT

Dénombrer c'est compter le nombre d'éléments que contient un ensemble fini

Chapitre6 : Dénombrement

Chapitre6 : Dénombrement I Ensembles finis et cardinaux : les bases. A) Supposé connu ... Ce qu'est le cardinal d'un ensemble fini (card(H)=0).

Cardinalité des ensembles finis

Deux ensembles (fini ou non) sont équipotents ou de même cardinal s'il existe une bijection entre eux. Pourquoi dénombrer un ensemble fini ?

Quelques notions mathématiques de base

22 janv. 2017 Dénombrer un ensemble fini non vide consiste à déterminer le nombre de ses éléments. ... Cardinal de l'ensemble des k-listes d'un ensemble.

Dénombrement

17. Dénombrement. Théorème 4. Soit E un ensemble fini de cardinal n. Soit p ? n. Alors le nombre de p-arrangements Ap n de l'ensemble. E est égal à.

Ensembles : définitions dénombrement et construction

Cardinal et dénombrement. Ensembles Le cardinal d'un ensemble fini E est son nombre d'éléments. ... Mode de définition trivial (pour ensembles finis).

denombrement.pdf - Dénombrement

5 nov. 2009 1 Cardinaux d'ensembles finis. 1.1 Quelques définitions. Définition 1. Un ensemble E est fini s'il est en bijection avec l'ensemble {1; ...

COMBINATOIRE ET DÉNOMBREMENT - maths et tiques

Dénombrer c’est compter le nombre d’éléments que contient un ensemble fini c’est à dire en déterminer le cardinal Exemples : L’ensemble ! des joueurs d’une équipe de foot est un ensemble fini Alors #$ &(!) = 11 L’ensemble ? des entiers naturels n’est pas un ensemble fini

Cours - Denombrement

1 cardinal d’un ensemble fini Dé?nition-théorème (Ensemble ?ni/in?ni cardinal d’un ensemble ?ni) Soit E un ensemble • On dit que E est ?ni s’il est vide ou si pour un certain n ? N ? il existe une bijection de l’ensemble ¹1 n ºsur E

DENOMBREMENT - Unisciel

Le cardinal d’un ensemble fini est le nombre de ses éléments On définit aussi le cardinal d’un ensemble infini mais c’est beaucoup plus compliqué Exemples : L’ensemble des nombres impairs et sont infinis dénombrables

Ensembles ?nis et Dénombrement

a) Cardinal d’un ensemble ?ni Cardinal d’un ensemble ?ni Notations j A Card( ) #A Tout fondement théorique des notions d’entier na-turel et de cardinal est hors programme Cardinal d’une partie d’un ensemble ?ni cas d’égalité Une application entre deux ensembles ?nis de même cardinal est bijective si et seulement

Chapitre6 : Dénombrement

‚ Ce qu’est le cardinal d’un ensemble fini (card(H) = 0) ‚ Pour np P N avec p ? n card(JpnK) = n´p+1 ‚ Proposition (admise) : Si E est fini et siF ? E alors F est fini et card(F) ? card(E) Si E et F sont disjoints et finis alors F YE est fini et card(E YF) = card(E)+card(F) B) Conséquences Si E1E2 En sont finis et

Searches related to dénombrement cardinal dun ensemble fini PDF

? 1) CARDINAL d’un ensemble fini ( effectif ) a) Définition 1 : Un ensemble ? contenant n éléments où n ? IN est dit « fini » On dit alors que « le cardinal de ? est n » on note card( ?) = n ou encore ? = n b) Exemples : 1 ? est l’ensemble des lettres de l’alphabet : card( ?) = ? = 26

Quel est le cardinal d’un ensemble fini ?

1CARDINAL D’UN ENSEMBLE FINI Dé?nition-théorème (Ensemble ?ni/in?ni, cardinal d’un ensemble ?ni)SoitEun ensemble. • On dit queEest?nis’il est vide ou si, pour un certainn? N?, il existe une bijection de l’ensemble ¹1,nºsurE. On dit dans le cas contraire queEestin?ni.

Comment calculer le cardinal d’un ensemble ?

On admet qu’un tel entier n, si il existe est unique, il est appelé cardinal de E et noté card(E), |E| ou encore #E. ? Le cardinal d’un ensemble fini est son nombre d’éléments. = { x1, x2, ...,xn }. ? Si E n’est pas un ensemble fini, on dit qu’il est infini. Un singleton est un ensemble de cardinal 1 E =

Comment montrer qu’un ensemble est fini ?

Dans la pratique : Pour montrer qu’en ensemble est fini et donner son cardinal, on pourra le mettre en bijection avec un ensemble fini dont le cardinal est connu. Lemme 10.2: Si E est une ensemble fini de cardinal n ? 1 et a un élément de E alors E{a} est fini et de cardinal n – 1. Si n = 1 alors E = {a} et E{a} = ?, le lemme est vérifié

Comment dénombrer un ensemble ?

? Méthode : Pour dénombrer un ensemble on peut représenter ses éléments dans une structure de données (arbre, tableau...) qui permet de compter. Corollaire : Soit E et F deux ensembles finis de cardinal respectifs p et n. Théorème 10.3 : Soit E un ensemble fini de cardinal n, l’ensemble P(E) des parties de E est fini et card(P(E)) = 2n.

Cardinalité

Université de Toulouse

Année 2020/2021

1 / 23

Cardinalité des ensembles finis

Cardinalité des ensembles finis2 / 23

Ensembles équipotents

SoientE=fa;b;c;dgetF=f1;2;3g.Il existe une application surjective deEsurF, mais pas d"application injective.Il existe application injective deFsurE, mais pas d"application surjective. En fait, il n"y a pas assez d"éléments dansF(ou trop peu dansE). Le cardinal d"un ensemble précise la notion de nombre d"élémentsEnsemble de même cardinal Deux ensembles (fini ou non) sontéquipotentsou demême cardinals"il existe une bijection entre eux. Cardinalité des ensembles finisEnsembles équipotents3 / 23

Cardinal d"un ensemble fini

Définition

Un ensembleEestfinisiE=;ou si9n2?tel queEest en bijection avecf1;:::;ng. Cet entier est unique, il est appelé lecardinaldeEnoté

Card(E). SiE=;, on poseCard(E) =0.Pour montrer que cet entier est définit de manière unique, on prouve la

proposition suivante :Proposition S"il existe une application injective def1;:::;ngdansf1;:::;kgalors nk.S"il existe une application surjective def1;:::;ngdansf1;:::;kg alorsnk.S"il existe une application bijection def1;:::;ngdansf1;:::;kgalors n=k.Cardinalité des ensembles finisCardinal d"un ensemble fini4 / 23

Cardinal d"un ensemble fini

Définition

Un ensembleEestfinisiE=;ou si9n2?tel queEest en bijection avecf1;:::;ng. Cet entier est unique, il est appelé lecardinaldeEnoté Card(E). SiE=;, on poseCard(E) =0.Qui se traduit de la manière suivante avec les cardinaux.

Proposition

SoientEetFdeux ensembles finis. On a :Il existe une application injective deEdansFsi et seulement si Card(E)Card(F).Il existe une application surjective deEdansFsi et seulement si Card(E)Card(F).Il existe une application bijective deEdansFsi et seulement si Card(E) =Card(F).Cardinalité des ensembles finisCardinal d"un ensemble fini4 / 23

Principe des tiroirs

SoientEetFdeux ensembles finis non vides etf:E!Fune application. SiCard(E)>Card(F)alors il existex1;x22Etels quef(x1) =f(x2).Nombre moyen de cheveux : 150000

Nombre d"habitant à Paris : 2,2 million

Il y a au moins deux personnes à Paris qui ont exactement le même nombre de cheveux.Principe des tiroirs généralisé SoientEetFdeux ensembles finis non vides etf:E!Fune application. SiCard(E)>kCard(F)aveck2?alors il existe une valeur defqui est répétée au moinsk+1 fois.Cardinalité des ensembles finisPrincipe des tiroirs5 / 23

Principe des tiroirs

SoientEetFdeux ensembles finis non vides etf:E!Fune application. SiCard(E)>Card(F)alors il existex1;x22Etels quef(x1) =f(x2).Nombre moyen de cheveux : 150000

Nombre d"habitant à Paris : 2,2 million

Dénombrement

Dénombrement6 / 23

Pourquoi dénombrer un ensemble fini?

En informatique vous utiliserez la notion de dénombrement au moins dans

les deux cas de figures suivants :dénombrer le nombre de cas à analyser par un algorithme en vu

d"étudier sa complexité;lorsqu"on tire au hasard un élément dans un univers finis de manière équiprobable (c"est à dire que chaque élément à la même probabilité d"être tiré), la probabilité que cet élément soit dans l"ensembleA est

P(A) =Card(A)Card(

):DénombrementMotivations7 / 23 Dénombrement et opérations sur les ensembles Union

Card(A[B) =Card(A) +Card(B)Card(A\B)AB

abcd efgh DénombrementOpération sur les ensembles8 / 23 Dénombrement et opérations sur les ensembles Union

Card(A[B) =Card(A) +Card(B)Card(A\B)

Card(A[B[C) =Card(A) +Card(B) +Card(C)Card(A\B)

Card(A\C)Card(B\C) +Card(A\B\C)AB

C abcd efgh i jkl m DénombrementOpération sur les ensembles8 / 23 Dénombrement et opérations sur les ensembles

Produit cartésien

Card(AB) =Card(A)Card(B)

Card(A1 An) =Card(A1) Card(An)a

1a 2a 3a

4(a1;b1)(a1;b2)(a1;b3)(a2;b1)(a2;b2)(a2;b3)(a3;b1)(a3;b2)(a3;b3)(a4;b1)(a4;b2)(a4;b3)A=fa1;a2;a3;a4g,B=fb1;b2;b3g,Card(AB) =43=12DénombrementOpération sur les ensembles9 / 23

Dénombrement et opérations sur les ensembles

Passage au complémentaire

Card A

=Card(

)Card(A)DénombrementOpération sur les ensembles10 / 23

Arrangement

Permutation denélémentsNombre de façon de rangernobjets dans l"ordre. n! =n(n1)(n2) 21Examples :

DénombrementArrangement11 / 23

Arrangement

Permutation denélémentsNombre de façon de rangernobjets dans l"ordre. n! =n(n1)(n2) 21Examples : Voici les 4! =24 permutations de quatre éléments distincta,b,cetd: abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cdba cdab cdba dabc dacb dbac dbca dcab dcba

DénombrementArrangement11 / 23

Arrangement

De combien de façons pouvez-vous ranger 10 livres sur une étagère?DénombrementArrangement11 / 23