Les coefficients binomiaux $C_n^k$ définis précédemment ont en fait de nombreuses propriétés, des plus basiques aux plus surprenantes. Il est important de bien connaître celles-ci puisque, en plus d'être divertissantes, elles permettent de simplifier des formules a priori compliquées obtenues lors d'un dénombrement. Le triangle de Pascal permet de représenter les différents coefficients binomiaux de sorte à mettre en évidence plusieurs de ces propriétés.
Nous avons vu dans les sections précédentes différents symboles dont $A^k_n$, $B^k_n$, $C^k_n$ et $D^k_n$. En fait, la plus connue de ces notations est $C^k_n$ (il faut d'ailleurs faire attention en utilisant les autres : il vaut mieux préciser ce dont on parle car les notations ne sont pas courantes).
Nous allons maintenant nous intéresser de plus près à la valeur de $C^k_n$ en fonction de $k$ et de $n$. Rappelons que, pour $0 \leq k \leq n$,
$$C^k_n = \frac{n!}{k! \cdot (n-k)!}.$$ (NB : par convention, $0! = 1$). Comme déjà mentionné précédemment, il s'agit d'un nombre entier puisqu'il a été défini comme étant un nombre de combinaisons. On peut également remarquer que
$$C^k_n = C^{n-k}_n.$$ C'est évident en observant la formule, mais cela a aussi un sens du point de vue des combinaisons : choisir $k$ objets parmi $n$, cela revient exactement à choisir les $n-k$ objets que l'on ne prend pas ! Il y a donc autant de façons de choisir $k$ objets parmi $n$ que d'en choisir $n-k$.
La formule de Newton permet de directement trouver les coefficients apparaissant dans le développement de l'expression $(x+y)^n$, pour $n$ entier. Il est bien connu que $$(x+y)^2 = x^2 + 2xy + y^2$$ ou encore que
$$(x+y)^3 = x^3 + 3x^2 y + 3xy^2 + y^3,$$ et la formule du binôme de Newton traîte le cas de la puissance $n$ en général.
Formule du binôme de Newton
Pour $n \in \mathbb{N}$, on a le développement
$$(x+y)^n = C^0_n \cdot x^n + C^1_n \cdot x^{n-1} y + \ldots + C^{n-1}_n \cdot x y^{n-1} + C^n_n \cdot y^n,$$ ce qui s'écrit, à l'aide du signe somme,
$$(x+y)^n = \sum_{k=0}^n C^k_n \cdot x^k y^{n-k}.$$
Notons déjà que $C^0_n = C^n_n = 1$ pour tout $n$, les coefficients de $x^n$ et $y^n$ dans le développement seront donc toujours égaux à $1$.
Démonstration
Nous commençons par donner le raisonnement dans le cas où $n = 3$, pour qu'il soit plus clair dans le cas général. Lorsqu'on développe
$$(x+y)^3 = (x+y) \cdot (x+y) \cdot (x+y),$$ on obtient huit termes :
$$xxx+xxy+xyx+xyy+yxx+yxy+yyx+yyy.$$ Dans chacun de ces termes, le nombre de $x$ et le nombre de $y$ dépendent uniquement de si on a choisi l'élément $x$ ou l'élément $y$ dans chaque parenthèse $(x+y)$. Si on désire compter le nombre de termes avec deux $y$ (c'est-à-dire le coefficient de $xy^2$), alors il faut calculer le nombre de façons de choisir $x$ ou $y$ dans chaque parenthèse de sorte qu'on ait choisi une fois $x$ et deux fois $y$. Autrement dit, il s'agit du nombre de façons de choisir $2$ objets parmi $3$ (les objets sont les différents $(x+y)$ et on doit choisir ceux pour lesquels on prend $y$), c'est-à-dire $C^2_3$.
Dans le cas général, on a
$$(x+y)^n = \underbrace{(x+y)\cdot \ldots \cdot (x+y)}_{n \text{ fois}}.$$ Cette fois, le coefficient de $x^{n-k}y^k$ est égal au nombre de façons de choisir $k$ objets parmi $n$ : encore une fois, on choisit les parenthèses pour lesquelles on prend $y$. Ce coefficient est donc égal à $C^k_n$.
On a alors le corollaire immédiat suivant :
Corollaire
Pour $n \in \mathbb{N}$, on a
$$C^0_n + C^1_n + \ldots + C^{n-1}_n + C^n_n = 2^n.$$
Démonstration
Il suffit de prendre $x = y = 1$ dans le binôme de Newton.
Une autre formule impliquant le symbole combinatoire est la suivante, parfois appelée
relation de Pascal.
Relation de Pascal
Pour $k, n \in \mathbb{N}$ avec $0 \leq k < n$, on a
$$C_{n+1}^{k+1} = C_n^k + C_n^{k+1}.$$
Démonstration
On peut à nouveau utiliser le binôme de Newton pour démontrer ce résultat, ou encore le faire à partir de la formule, mais le plus simple est à nouveau de raisonner à partir de la définition combinatoire de $C^k_n$. En effet, $C_{n+1}^{k+1}$ représente le nombre de façons de choisir $k+1$ objets parmi $n+1$. Lors de notre choix, on peut ou non choisir le premier objet. Si on le choisit, alors il nous reste à choisir $k$ autres objets parmi les $n$ objets restants. Si on ne le choisit pas, alors on doit encore choisir nos $k+1$ objets parmi les $n$ autres objets. On a donc directement la formule annoncée.
L'intérêt de cette formule est que l'on peut déduire la valeur des $C^k_{n+1}$ (avec $n$ fixé) directement de la valeur des $C^k_n$. Le triangle de Pascal permet justement de visualiser ce résultat. Sur la $(n+1)^\text{ème}$ ligne de ce triangle, on retrouve les valeurs de $C^0_n, C^1_n, \ldots, C^n_n$. Puisque $C^0_n = C^n_n = 1$, chaque ligne commence et se termine par un $1$.
$$\begin{array}{ccccccccc}
& & & & C^0_0 & & & & \\
& & & C^0_1 & & C^1_1 & & & \\
& & C^0_2 & & C^1_2 & & C^2_2 & & \\
& C^0_3 & & C^1_3 & & C^2_3 & & C^3_3 & \\
\ldots & &\ldots & & \ldots & & \ldots & & \ldots
\end{array}$$ En valeurs, on obtient :
$$\begin{array}{ccccccccccccc}
& & & & & & 1 & & & & & & \\
& & & & & 1 & & 1 & & & & & \\
& & & & 1 & & 2 & & 1 & & & & \\
& & & 1 & & 3 & & 3 & & 1 & & & \\
& & 1 & & 4 & & 6 & & 4 & & 1 & & \\
& 1 & & 5 & & 10 & & 10 & & 5 & & 1 \\
\ldots & & \ldots & & \ldots & & \ldots & & \ldots & & \ldots & & \ldots
\end{array}$$ On peut observer les différents résultats que nous avons jusqu'ici obtenus sur ce triangle de Pascal. Tout d'abord, pour avoir les coefficients du développement de $(x+y)^n$, il suffit de regarder la $(n+1)^\text{ème}$ ligne du triangle. Par exemple, on a
$$(x+y)^4 = x^4 + 4x^3 y + 6 x^2 y^2 + 4 x y^3 + y^4$$ D'autre part, on retrouve aussi les puissances de $2$ en additionnant les éléments d'une même ligne. Enfin, ce triangle est très simple à construire puisqu'on sait que le premier et le dernier élément de chaque ligne vaut $1$ et que chaque élément est égal à la somme des deux éléments situés juste au dessus (car $C_{n+1}^{k+1} = C_n^k + C_n^{k+1}$).
Le triangle de Pascal possède en fait un grand nombre d'autres propriétés. Nous ne les donnons pas toutes, mais le lecteur intéressé pourra facilement trouver des articles consacré à ce fameux triangle. Pour notre part, nous évoquons encore une curiosité : on peut retrouver les nombres de Fibonacci dans le triangle de Pascal ! Il faut pour cela réécrire le triangle sous une forme parfois préférée à la forme précédente :
$$\begin{array}{ccccccc}
1 & & & & & & \\[2mm]
1 & 1 & & & & & \\[2mm]
1 & 2 & 1 & & & & \\[2mm]
1 & 3 & 3 & 1 & & & \\[2mm]
1 & 4 & 6 & 4 & 1 & & \\[2mm]
1 & 5 & 10 & 10 & 5 & 1 & \\[2mm]
1 & 6 & 15 & 20 & 15 & 6 & 1
\end{array}$$ Pour observer les nombres de Fibonacci, il faut calculer la somme des éléments des diagonales de ce triangle. On retrouve alors $\boxed{1}$, $\boxed{1}$, $1+1 = \boxed{2}$, $1+2 = \boxed{3}$, $1+3+1 = \boxed{5}$, $1+4+3 = \boxed{8}$, $1+5+6+1 = \boxed{13}$, ... Rappelons que les nombres de Fibonacci sont définis par
$$\left\{\begin{array}{ll}
F_1 = F_2 = 1 & \\
F_n = F_{n-1} + F_{n-2} & \text{ si } \ n \geq 3
\end{array}\right.$$ Cette observation s'écrit en formules par
Propriété (Fibonacci et Pascal réunis)
Pour $n \in \mathbb{N}$, on a
$$C_n^0 + C_{n-1}^1 + \ldots + C_{\left\lfloor \frac{n+1}{2} \right\rfloor}^{\left\lceil \frac{n-1}{2} \right\rceil} = F_{n+1}.$$
Les notations $\lceil x \rceil$ et $\lfloor x \rfloor$ permettent de ne pas distinguer le cas où $n$ est pair de celui où $n$ est impair, mais cela veut tout simplement dire que
$$C_n^0 + C_{n-1}^1 + \ldots + C_{\left(\frac{n}{2}\right)}^{\left(\frac{n}{2}\right)} = F_{n+1} \quad \text{ si $n$ est pair},$$ $$C_n^0 + C_{n-1}^1 + \ldots + C_{\left(\frac{n+1}{2}\right)}^{\left(\frac{n-1}{2}\right)} = F_{n+1} \quad \text{ si $n$ est impair}.$$
La démonstration de ce résultat se fait par récurrence : on a vu que la formule était correcte pour $n = 1$ et $n = 2$ sur le triangle, et il suffit alors d'utiliser la relation de Pascal pour montrer que si la formule est vérifiée pour $n-2$ et $n-1$, alors elle l'est également pour $n$. Nous ne donnons pas les détails.