Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
190 personne(s) sur le site en ce moment
E. Cartan

Les maths pour l'agreg

A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 
Combinaisons next up previous index
suivant: Quelques applications monter: Combinatoire et dénombrements précédent: Arrangements   Index


Combinaisons

Définition On appelle $ p$-combinaison de $ E$ tout sous-ensemble de $ E$ de cardinal $ p$. On note $ C_n^p$ ou $ \left(\begin{array}{c}n \\ p \end{array}\right)$ le cardinal de l'ensemble des $ p$-combinaisons de $ E$. On montre facilement, par récurrence, que $ C_n^p=\frac{n!}{p!(n-p)!}$.
Cette formule peut aussi se déduire sans récurrence en voyant que $ p!$ $ p$-arrangements donnent la même $ p$-combinaison donc $ C_n^p=\frac1{p!}A_n^p=\frac{n!}{p!(n-p)!}$.
Elle peut aussi se déduire du fait que le groupe $ \sigma (E)$ des permutations de $ E=\{1,2,...,e\}$ agit transitivement sur l'ensemble des $ p$-combinaisons de $ E$, que le stabilisateur $ S$ de $ F=\{1,2,...,f\}\subset E$ est le produit $ A\times B$ avec $ A$ et $ B$ respectivement les groupes de permutations de $ \{1,2,...,f\}$ et $ \{f+1,f+2,...,e\}$; $ S$ a donc pour cardinal $ S=f!(e-f)!$, d'où $ C_e^f=\frac{\sigma (E)}{\vert S\vert}=\frac{e!}{f!(e-f)!}$. Un argument similaire permet d'ailleurs de montrer la formule $ A_n^p=\frac{n!}{(n-p)!}$ sans récurrence.

En outre on a les formules suivantes:

Proposition

$\displaystyle C_n^p=C_n^{n-p}$

$\displaystyle C_{n+1}^p=C_n^p+C_n^{p+1}$

    Formule de Newton, valable dans un anneau: si $ a.b=b.a$ et $ n>0$, alors:

$\displaystyle (a+b)^n=\sum_{k=0}^n C_n^k a^k.b^{n-k}$

$\displaystyle \sum_{k=0}^n C_n^k=2^n$

$\displaystyle \sum_{k=0}^n (-1)^k C_n^k=0$

   (ces deux formules sont obtenues en spécialisant la formule de Newton)

$\displaystyle 1 \leq p \leq n \rightarrow p.C_n^p=n.C_{n-1}^{p-1}$

$\displaystyle \sum_{k=0}^n k.C_n^k=n.2^{n-1}$

$\displaystyle \sum_{k=0}^n (-1)^k C_n^k=1$

$\displaystyle \sum_{k=0}^n (C_n^k)^2=C_{2n}^n$

\begin{displaymath}\begin{array}{c\vert ccccc}
& p=0 & p=1 & p=2 & p=3 & p=4 \\...
...& 1 & 3 & 3 & 1 & 0 \\
n=4 & 1 & 4 & 6 & 4 & 1 \\
\end{array}\end{displaymath}


next up previous index
suivant: Quelques applications monter: Combinatoire et dénombrements précédent: Arrangements   Index
C_Antonini,J_F_Quint,P_Borgnat,J_Bérard,E_Lebeau,E_Souche,A_Chateau,O_Teytaud
 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page