Combinaisons sans répétition

Il s'agit de dispositions non ordonnées de $p$ éléments discernables pris parmis $n$, sans répétition.
Pour une disposition ordonnée de $p$ éléments pris parmi $n$ sans répétition, il y a $A_{n}^{p}$ possibilités. Parmi celles-ci, $p!$ permutations correspondent à la même disposition non-ordonnée. On en déduit donc :

$$\boxed{\forall (p,\ n) \in \mathbb{N}^{2},\ p \leq n,\ C_{n}^{p}=\frac{A_{n}^{p}}{p!}=\frac{n!}{p!(n-p)!}}$$

Propriétés :

$$C_{n}^{p} = \frac{n!}{p!(n-p)!}=C_{n}^{n-p}$$

$$C_{n}^{p} = C_{n-1}^{p}+C_{n-1}^{p-1}$$

Demonstration :
Parmi les $C_{n}^{p}$ combinaisons de $p$ éléments pris parmi $n$, il y en a qui contiennent un élément particulier $a$, et d'autres qui ne le contiennent pas.

• Nombre de combinaisons qui contiennent $a$ : elles contiennent $a$ et $(p-1)$ éléments autres que $a$, pris parmi les $(n-1)$ qui ne sont pas $a$. Il y en a donc $C_{n-1}^{p-1}$.
• Nombre de combinaisons qui ne contiennent pas $a$ : elles contiennent $p$ éléments pris parmi les $(n-1)$ éléments autres que $a$. Il y en a donc $C_{n-1}^{p}$

Donc $C_{n}^{p}=C_{n-1}^{p}+C_{n-1}^{p-1}$

Triangle de Pascal :

p	0	1		2	3	$\dots$	(p-1)		p
n
1	1	1
2	1	2	+	1
				$\parallel$
3	1	3		3	1
$\vdots$
(n-1)			...				$C_{n-1}^{p-1}$	+	$C_{n-1}^{p}$
									$\parallel$
n			...						$C_{n}^{p}$

Formule du binôme de Newton :

On retrouve ainsi la formule du développement d'un binôme (voir formule_binome) :

$$\forall n \in \mathbb{N},\ (a+b)^{n}=\sum_{k=0}^{n}C_{n}^{k}\ a^{k}\ b^{(n-k)}$$

Tout terme en $a^{k}b^{(n-k)}$ est répété autant de fois qu'on peut prendre $k$ éléments $a$ et $(n-k)$ éléments $b$ dans un rang différent.

On en déduit aisément :

$$\sum_{k=0}^{n}C_{n}^{k} = 2^{n}$$

$$\sum_{p=0}^{n}(-1)^{p}C_{n}^{p} = (1-1)^{n}=0$$