Dénombrement

Un article de wiki sillages.info.

Ce résumé est basé sur le programme de mathématiques de première année des classes préparatoires aux grandes écoles économiques et commerciales, voie scientifique (ECS1). Un résumé complet du programme de mathématiques ECS1 est proposé sur la Plate-forme SILLAGES.

Sommaire

Cardinal d’un ensemble fini

Si E\neq\O, c’est l’unique entier n\in\mathbb N^* tel que E soit en bijection avec [\![1,n]\!].

\mathrm{Card}E=n est le nombre d’éléments de E et \mathrm{Card}\O=0.

Propriétés :

\mathrm{Card}\overline A=\mathrm{Card}E-\mathrm{Card}A

\mathrm{Card}(A\cup B)=\mathrm{Card}A+\mathrm{Card}B-\mathrm{Card}(A\cap B)

\mathrm{Card}(A\cup B\cup C)=\mathrm{Card}(A)+\mathrm{Card}(B)+\mathrm{Card}(C)-\mathrm{Card}(A\cap B)-\mathrm{Card}(A\cap C)-\mathrm{Card}(B\cap C)+\mathrm{Card}(A\cap B\cap C)

Formule du crible :

\mathrm{Card}\left(\bigcup_{k=1}^{n}A_k\right)=\sum_{k=1}^{n}(-1)^{k-1}\left(\sum_{1\leq i_1<...<i_k\leq n}\mathrm{Card}(A_{i_1}\cap ...\cap A_{i_k})\right)

\mathrm{Card}(A\times B)=(\mathrm{Card}A)\times\mathrm{Card}B

Partition

Une famille (A_1, ...,A_n ) de parties de E est une partition de E si :

  1. Leur réunion est égale à E : E=A_1\cup ...\cup A_n
  2. Elles sont deux à deux disjointes : A_i\cap A_j=\O\quad\mathrm{pour} \quad\mathrm{tous}\quad i\neq j

Alors \mathrm{Card}E=\mathrm{Card}A_1+ ...+\mathrm{Card}A_n.

Arbre de dénombrement

Si une situation se décompose en k étapes ayant respectivement n_1, ..., n_k issues possibles, alors on peut schématiser cette situation par un arbre et le nombre total d’issues est : n=n_1\times ...\times n_k.

Notation factorielle

Si n\neq 0, n! est le produit de tous les entiers compris entre 1 et n.

Par définition : 0!= 1

Propriété: (n+1)!=(n+1)\times n!

Nombre de p-listes avec répétition

Une p-liste avec répétition de E est un élément (x_1, ...,x_p) de E^p.

Si \mathrm{Card}E=n, le nombre de p-listes avec répétition de E est : n^p.

C’est aussi le nombre d’applications d’un ensemble à p éléments dans un ensemble à n éléments.

Nombre de p-listes sans répétition (arrangements)

Une p-liste sans répétition de E est un élément (x_1, ...,x_p) où les x_i sont des éléments distincts de E.

Si \mathrm{Card}E=n, le nombre de p-listes sans répétition de E est : A_{n}^{p}=\dfrac{n!}{(n-p)!}\quad\mathrm{si}\quad 0\leq p\leq n\quad\mathrm{et}\quad A_{n}^{p}=0\quad\mathrm{sinon.}

C’est aussi le nombre d’applications injectives d’un ensemble à p éléments dans un ensemble à n éléments.

Nombre de permutations

Une permutation de E est une bijection de E dans E. Si \mathrm{Card}E=n, une permutation de E correspond à une n-liste sans répétition de E. Donc le nombre de permutations de E est n!.

C’est aussi le nombre de bijections d’un ensemble à n éléments dans un autre ensemble à n éléments.

Nombre de parties à p éléments (combinaisons)

Si \mathrm{Card}E=n, le nombre de parties à p-éléments est : \begin{pmatrix} n \\ p \end{pmatrix}=\dfrac{n!}{p!(n-p)!}\quad\mathrm{si}\quad 0\leq p\leq n\quad\mathrm{et}\quad\begin{pmatrix} n \\ p \end{pmatrix}=0\quad\mathrm{sinon.}

Propriétés :

\begin{pmatrix} n \\ p \end{pmatrix}=\begin{pmatrix} n \\ {n-p} \end{pmatrix}

\begin{pmatrix} {n+1} \\ p \end{pmatrix}=\begin{pmatrix} n \\ p \end{pmatrix}+\begin{pmatrix} n \\ {p-1} \end{pmatrix}\quad\mathrm{si}\quad 1\leq p\leq n

Formule de Vandermonde :

\sum_{k=0}^{n}\begin{pmatrix} p \\ k \end{pmatrix}\begin{pmatrix} q \\ {n-k} \end{pmatrix}=\begin{pmatrix} {p+q} \\ n \end{pmatrix}

Nombre de parties d’un ensemble à n éléments

Le nombre de parties d’un ensemble à n éléments est 2^n

Nombre de manières d’ordonner des objets

Le nombre de manières d’ordonner n objets est : n!

Nombre de tirages de p objets parmi n

  • Tirages successifs avec remise de p objets parmi n : n^p
  • Tirages successifs sans remise de p objets parmi n : A_{n}^{p}=\dfrac{n!}{(n-p)!}\quad\mathrm{si}\quad 0\leq p\leq n
  • Tirages simultanés de p objets parmi n : \begin{pmatrix} n \\ p \end{pmatrix}=\dfrac{n!}{p!(n-p)!}\quad\mathrm{si}\quad 0\leq p\leq n


--CatherineLaidebeure 13 juillet 2010 à 15:03 (CEST)