Sommes et produits

Nous commençons par les sommes. L'écriture

$$\sum_{k=0}^5 2^k$$

se lit « somme pour $k$ allant de zéro à cinq de deux puissance $k$». C'est une notation abrégée pour :

$$2^0+2^1+2^2+2^3+2^4+2^5.$$

La lettre $k$ est l'indice de sommation. On la remplace successivement par toutes les valeurs entières comprises entre les deux bornes, qui sont 0 et $5$ dans notre exemple. La première borne, celle qui est écrite au-dessous du signe somme, sera toujours inférieure ou égale à celle qui est au-dessus. Les bornes peuvent elles-mêmes être des variables, mais elles sont nécessairement différentes de l'indice de sommation. Par exemple, pour tout entier naturel $n$:

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

désigne la somme

$$2^0+2^1+2^2+2^3+\cdots+2^{n-1}+2^n\;.$$

Rappelons que, par convention, $a^0=1$ pour tout nombre réel $a$. Prenez l'habitude d'écrire les sommes sous forme développée quitte à introduire des points de suspension entre les premiers termes et les derniers. Voici quelques exemples d'égalités illustrant la manipulation des indices et des bornes. Nous donnons sous chaque exemple une écriture sous forme développée.

$$\sum_{k=1}^n 2^k = \sum_{h=0}^{n-1} 2^{h+1}$$

$$2^1+\cdots+2^n = 2^{0+1}+\cdots+2^{n-1+1}\;.$$

L'indice de sommation peut être remplacé par n'importe quel autre : on dit que c'est une variable muette.

$$\displaystyle{ \sum_{k=0}^n 2^k +\sum_{h=1}^{n} 2^{n+h}} = \displaystyle{\sum_{k=0}^{2n} 2^k}$$

$$(2^0+\cdots+2^n) + (2^{n+1}+\cdots+2^{2n}) = 2^0+\cdots+2^{2n}\;.$$

Observez que la borne peut être une des variables de la quantité à sommer.

$$\displaystyle{\sum_{k=0}^n 2^n} = (n+1)2^n$$

$$2^n+\cdots+2^n = (n+1)2^n\;.$$

Dans cet exemple la quantité à sommer ne dépend pas de l'indice de sommation : celle-ci a pour seul effet de compter les termes. Attention, pour $m\leqslant n$, il y a $n-m+1$ termes dans la somme de $m$ à $n$.

$$\displaystyle{\sum_{k=0}^n \sum_{h=0}^1 2^{k+h} } = \displaystyle{\sum_{h=0}^{1} \sum_{k=0}^n 2^{k+h}}$$

$$(2^0+2^1)+\cdots+ (2^{n}+2^{n+1}) = (2^0+\cdots+2^n)+(2^1+\cdots+2^{n+1})\;.$$

Une double somme est une somme de sommes, et on peut toujours intervertir les deux.

Voici un enchaînement d'égalités, montrant que la somme des puissances de $2$ de $2^0$ jusqu'à $2^n$ vaut $(2^{n+1}-1)$ (c'est un cas particulier d'une formule à connaître que nous verrons plus loin). Pour chaque ligne de calcul, nous donnons à droite l'écriture sous forme développée. On rappelle que $2^0=1$.

$$\begin{array}{lcl\vert cl} \displaystyle{\sum_{k=0}^n 2^k}&=... ...cdots+2^n) [2ex] &=& 2^{n+1}-2^0 &=& 2^{n+1}-1\;. \end{array}$$

Ce que nous venons de voir pour les sommes s'applique aussi aux produits. Le produit des entiers de $1$ à $n$ intervient dans de nombreuses formules. C'est la factorielle de $n$. Elle se note «$n!$». $n!$

$$n! = \prod_{k=1}^n k = 1 2 3\cdots (n-2) (n-1) n\;.$$

Il est souvent utile d'étendre la définition de la factorielle en convenant que $0!=1$. Voici les premières valeurs.

$$\begin{array}{\vert c\vert ccccccccccc\vert} \hline n&0&1&2&... ...&2&6&24&120&720&5040&40320&362880&3628800\\ \hline \end{array}$$

Si $n$ est un entier positif, un $n$-uplet désigne une liste ordonnée de $n$ objets. On appelle permutation des nombres de $1$ à $n$ un $n$-uplet d'entiers $(u_1,\dots,u_n)$ dans lequel chaque entier entre $1$ et $n$ apparaît une et une seule fois. Par exemple $(5,3,2,4,1)$ est une permutation des nombres de $1$ à $5$.

Théorème 1   Le nombre de permutations des nombres de $1$ à $n$ est $n!$.

Démonstration : On montre le théorème par récurrence sur $n$.

Si $n=1$, la seule permutation des entiers de $1$ à $1$ est $(1)$.

On suppose donc que le résultat est vrai pour l'entier $n$. Montrons-le pour l'entier $n+1$. Soit $k$ un entier tel que $1\leqslant k\leqslant n+1$ et comptons le nombre $A_k$ de permutations

$$(u_1,\dots,u_{n+1})$$

telles que $u_k=n+1$. À une telle permutation, associons le $n$-uplet :

$$(u_1,\dots,u_{k-1},u_{k+1},\dots,u_{n+1})\;.$$

C'est une permutation des nombres de $1$ à $n$. Inversement étant donnée une permutation $(v_1,\dots,v_n)$ des entiers de $1$ à $n$, alors

$$(v_1,\dots,v_{k-1},n+1,v_{k+1},\dots,v_n)$$

est une permutation des entiers de $1$ à $n+1$ dont le $k$-ième terme est $n+1$. En appliquant l'hypothèse de récurrence, on obtient que $A_k=n!$. Donc le nombre total de permutations des nombres de $1$ à $n+1$ est :

$$\sum_{k=1}^{n+1}A_k=\sum_{k=1}^{n+1}n!=(n+1) n!=(n+1)!\;,$$

ce qui montre le résultat pour $n+1$.$\square$

Pour ordonner $n$ objets, il faut associer à chacun un nombre entre $1$ et $n$ de sorte que chaque nombre renvoie à un objet et un seul. Il y a autant de manières de le faire que de permutations des $n$ premiers entiers : $n!$. Au tiercé, il y a $5!=120$ manières d'ordonner les 5 premiers chevaux. Une seule donne l'ordre d'arrivée, soit le quinté dans l'ordre, et il y a $119$ quintés dans le désordre. Le nombre de combinaisons de $k$ objets parmi $n$ est le nombre de manières de choisir $k$ objets parmi $n$, sans distinguer leur ordre.

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}\;.$$ (1)

La notation $\binom{n}{k}$ $\binom{n}{k}$$C_n^k$que nous utilisons ici, de préférence à l'ancienne notation $C_n^k$, est conforme aux programmes en vigueur et à l'usage international. Nous conseillons de la lire «de $n$ choisir $k$».

La formule (1) correspond au raisonnement suivant. Pour choisir $k$ objets, on peut se donner une permutation des $n$ objets, et décider d'en retenir les $k$ premiers. Parmi les permutations, toutes celles qui auront en commun leurs $k$ premiers nombres conduiront au même choix. Il faut donc diviser par le nombre de permutations des $k$ objets choisis, et par le nombre de permutations des $n-k$ objets qui ne l'ont pas été.

Observez que (1) ne change pas si on remplace $k$ par $n-k$.

$$\binom{n}{k}=\binom{n}{n-k}\;.$$

Choisir $k$ objets parmi $n$ (ceux que l'on garde) revient à en choisir $n-k$ (ceux que l'on laisse).

Voici une autre expression de $\binom{n}{k}$.

$$\binom{n}{k} = \frac{1}{k!}\prod_{h=0}^{k-1} (n-h) =\frac{n (n-1) \cdots (n-k+1)}{1 2 \cdots k}\;.$$ (2)

Notez qu'il y a $k$ facteurs au numérateur, comme au dénominateur. On obtient cette formule en simplifiant le quotient $n!/(n-k)!$ dans (1).

On peut aussi raisonner comme suit. Il y a $n$ façons de choisir le premier objet, puis $n-1$ de choisir le second (puisqu'un objet a déjà été choisi), etc. Pour choisir le $k$-ième objet, il reste $n\!-\!(k\!-\!1)$ possibilités. Ceci correspond au numérateur de (2). Cette manière de procéder retourne une liste ordonnée. Il faut donc diviser par le nombre d'ordres possibles des $k$ objets choisis, qui est $k!$.

Observez les relations suivantes, faciles à déduire de (1) ou (2) et de la définition de la factorielle.

$$\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1} = \frac{n-k+1}{k}\binom{n}{k-1}\;.$$

Pour calculer $\binom{n}{k}$ en pratique, on n'utilise ni (1) ni (2). Le calcul récursif par la formule du triangle de Pascal (connue des indiens, des chinois et des arabes bien avant Pascal) est beaucoup plus rapide.

$$\binom{n}{k} = \binom{n-1}{k}+\binom{n-1}{k-1}\;.$$ (3)

Nous conseillons au lecteur de démontrer cette formule à partir des expressions (1) et (2). Voici la justification combinatoire. Supposons que parmi les $n$ objets dont $k$ doivent être choisis, l'un d'entre eux soit distingué (disons qu'il est rouge). Parmi les choix possibles de $k$ objets, certains ne contiennent pas l'objet rouge, d'autres le contiennent. Les premiers sont au nombre de $\binom{n-1}{k}$, car les $k$ objets sont choisis parmi les $n-1$ différents de l'objet rouge. Les choix contenant l'objet rouge sont au nombre de $\binom{n-1}{k-1}$ car l'objet rouge ayant été retenu, il reste $k-1$ objets à choisir parmi les $n-1$ autres. Voici, disposées en triangle, les valeurs de $\binom{n}{k}$ pour $n$ allant de 0 à $6$.

$$\begin{array}{c\vert ccccccc} n\backslash k&0&1&2&3&4&5&6 ... ...&4&6&4&1&&\\ 5&1&5&10&10&5&1\\ 6&1&6&15&20&15&6&1 \end{array}$$

Chaque valeur est la somme de celle qui est au-dessus, et de celle qui est à gauche de celle qui est au-dessus. S'il n'est pas indispensable de connaître ce tableau par cur, il est souvent utile de savoir le réécrire rapidement.