Définitions

Ensemble d’éléments

Cette partie donne quelques rappels sur la notion d’ensemble en mathématiques.

Définition

Un ensemble EE désigne une collection finie ou infinie d’objets distincts qu’on appelle ses éléments.

On note xEx \in E si l’objet xx appartient à EE. Dans le cas contraire, on note xEx \notin E.

À noter que l’ordre des objets n’a aucune importance lorsque l’on compare deux ensembles.

Réunion et intersection

Soient EE et FF deux ensembles.

  • Leur réunion notée EFE \, \cup \, F est l’ensemble constitué des éléments de EE et des éléments de FF.

  • Leur intersection notée EFE \, \cap \, F est l’ensemble constitué des éléments communs à EE et FF.

  • Si EF=E \, \cap \, F = \emptyset, on dit que EE et FF sont disjoints.

Sous-ensemble

Définition

Soient EE et FF deux ensembles. On dit que FF est un sous-ensemble (ou une partie) de EE si tout élément de FF est un élément de EE.

On note ceci par FEF \subset E (qui signifie FF est inclus dans EE).

Liste d’éléments

Nous allons désormais voir un type de collection similaire aux ensembles, mais qui prend en compte l’ordre des éléments.

Définition

Un pp-uplet (ou une pp-liste) d’un ensemble EE désigne une collection ordonnée de pp éléments de EE.

Remarquons que l’on ne demande pas que les éléments d’un pp-uplet soient tous distincts.

Combinaisons

Factorielle

Définition

Soit nn un nombre entier. On appelle factorielle de nn le nombre entier n!=1×2××nn! = 1 \times 2 \times \dots \times n.

Il est très courant de rencontrer des calculs avec des factorielles en mathématiques, leur utilisation ne se limitant pas au dénombrement.

Qu’est-ce-qu’une combinaison ?

Définition

Une combinaison de kk éléments parmi nn éléments, notée (nk)\displaystyle{\binom{n}{k}}, est le nombre de sous-ensembles de kk éléments que possède un ensemble de nn éléments.

Calcul d’une combinaison

Soient nn et kk deux entiers. Alors (nk)=n!(nk)!k!\displaystyle{\binom{n}{k} = \frac{n!}{(n-k)!k!}}.

Formules

Formules

Soient nn et kk deux entiers.

  • (n0)=(nn)=1\displaystyle{\binom{n}{0} = \binom{n}{n} = 1}

  • (n1)=(nn1)=n\displaystyle{\binom{n}{1} = \binom{n}{n-1} = n}

  • (nk)=(nnk)\displaystyle{\binom{n}{k} = \binom{n}{n-k}}

Dénombrement

Principe additif

Principe additif

Soient EE et FF deux ensembles disjoints contenant respectivement nn et mm éléments. Alors EFE \, \cup \, F contient n+mn + m éléments.

Principe multiplicatif

Commençons cette sous-section par une définition.

Produit cartésien

Soient EE et FF deux ensembles. Leur produit cartésien E×FE \times F est l’ensemble des couples (e;f)(e; f)eEe \in E et fFf \in F.

Principe multiplicatif

Soient EE et FF deux ensembles contenant respectivement nn et mm éléments. Alors E×FE \times F contient n×mn \times m éléments.

Ce principe (tout comme le principe additif vu précédemment) sont notamment utilisés en probabilités.

Formules de dénombrement

Permutations

Soit EE un ensemble de taille nn. On appelle permutation de EE tout nn-uplet d’éléments distincts de EE.

Formules

Soit EE un ensemble possédant nn éléments.

  • Le nombre de pp-uplets d’éléments de EE est égal à npn^p.

  • Le nombre de pp-uplets d’éléments distincts de EE est égal à n!(np)!\frac{n!}{(n-p)!}.

  • Le nombre de permutations de EE est égal à n!n!.

  • Le nombre de sous-ensembles de EE est égal à 2n2^n.

  • Le nombre de sous-ensembles de kk éléments que possède EE est égal à (nk)\displaystyle{\binom{n}{k}} (pour rappel).