1 – Préambule et notations
Pour tout entier naturel on désigne par l’ensemble des entiers vérifiant .
Noter que :
Définition
Un ensemble E est dit fini lorsqu’il existe un entier naturel et une bijection de vers . On peut montrer l’unicité d’un tel : c’est le cardinal de , noté .
Intuitivement, indique le nombre d’éléments de .
On peut démontrer (nous l’admettrons ici) la :
Proposition 1
Proposition 2
- si , alors
Nous aurons enfin à utiliser le :
Principe Additif
Si sont deux ensembles finis et disjoints, alors est fini et :
Plus généralement, si sont des ensembles finis deux à deux disjoints, alors :
2 – Point de vue combinatoire sur les coefficients binomiaux
Définition
Exemple
Manifestement, il en existe six. Par conséquent : .
Et ne parlons pas de :
Même si nous étions capables de passer en revue les parties de cardinal 30 d’un ensemble de cardinal 60, à raison d’une par seconde, sans jamais faire de pause, il ne nous faudrait pas moins de 3,7 milliards d’années pour en venir à bout !!
3 – Formule de symétrie
Ces éléments, qui sont mis de côté, sont donc – en un sens – « choisis » eux aussi !
Il n’est donc pas surprenant qu’on ait :
Proposition
Pour tout et pour tout :
C’est la formule de symétrie des coefficients binomiaux.
En voici une justification rigoureuse.
Preuve (cliquer pour déplier / replier)
Soit un ensemble de cardinal . Pour chaque partie de , notons le complémentaire de dans et considérons les applications :
Comme le complémentaire du complémentaire d’une partie n’est autre que , il est clair que :
Il s’ensuit que et sont des bijections (et que chacune est la réciproque de l’autre).
En particulier, et sont équipotents, d’où la formule.
4 – Formule de Pascal
Soient deux entiers naturels tels que et .
Considérons un ensemble de cardinal ainsi qu’un élément particulier de , que nous notons .
Les parties de de cardinal , qui sont au nombre de , peuvent être classées en deux catégories :
- celles qui ne contiennent pas ,
- celles qui contiennent .
Les premières sont les parties de cardinal de . Il en existe .
Les autres s’obtiennent en ajoutant à une partie de cardinal de : il en existe donc autant que de parties de cardinal de , c’est-à-dire .
Ce raisonnement prouve, via le principe additif, que :
Proposition
Pour tout et pour tout :
Cette relation (appelée formule de Pascal) permet de construire un tableau, appelé « triangle de Pascal », qui renferme les valeurs des coefficients binomiaux. La valeur de est placée à l’intersection de la ligne n et de la colonne k.
➣ Comme pour tout , on place au préalable des ‘1’ sur la colonne 0 et sur la diagonale.
➢ Ensuite, on utilise la formule encadrée pour « garnir » la table, ligne par ligne.
L’animation suivante montre le remplissage du triangle de Pascal, jusqu’à la ligne 8 :
5 – Formule de Fermat
Nous sommes maintenant en mesure d’établir une formule adaptée au calcul direct de .
Il s’agit de la « formule de Fermat » :
Proposition
Pour tout et pour tout :
Si la notion de factorielle vous est peu familière, je vous suggère la lecture des articles suivants :
- Qu’est-ce qu’une factorielle ? Partie 1 (article de vulgarisation)
- Qu’est-ce qu’une factorielle ? Partie 2 – (article de niveau supérieur)
La formule encadrée se prouve par récurrence sur . Pour , il est clair que :
Supposons ensuite que, pour un certain , on ait pour tout :
Alors, pour tout :
c’est-à-dire :
comme souhaité.
Cette égalité est encore vraie pour et pour , et la formule de Fermat est donc établie.
Pour les calculs numériques, il est pratique d’utiliser ceci :
Version simplifiée de la formule de Fermat
Pour tout et pour tout :
On retiendra que le numérateur et le dénominateur de cette fraction sont chacun le produit de entiers consécutifs. Ceci peut aider à mémoriser correctement la formule.
Quelques Exemples
Exemple 1
De combien de façons peut-on choisir 6 cartes à jouer dans un paquet de 16 cartes ?
Réponse :
Exemple 2
Une grille de loto comporte 49 numéros.
De combien de façons le joueur peut-il en choisir 6 ?
Réponse :
Remarquons, pour conclure cette section, que la formule de Fermat exprime une propriété arithmétique intéressante en soi, à savoir qu’étant donné un entier , tout produit de entiers consécutifs est multiple de la factorielle de . En effet, étant donné :
Pour plus de détails à ce sujet, je vous invite à lire l’article (n+1)(n+2)…(n+k) est multiple de k!
6 – Formule du binôme de Newton
Au collège, on apprend l’identité remarquable .
La formule du binôme en donne une version généralisée, avec un exposant quelconque :
Proposition
Pour tout et pour tout :
Commençons par en donner une preuve combinatoire.
En développant « brutalement » l’expression , on obtient termes, qui sont tous de la forme pour un certain .
Pour une valeur donnée de , combien de fois le terme apparaît-il ? C’est simple : il suffit de voir que, pour obtenir ce terme, on doit sélectionner la lettre dans facteurs et la lettre dans les autres, ce qui peut se faire de façons.
Pour chaque , le terme apparaît donc fois dans le développement de . La formule du binôme en résulte.
On peut aussi envisager une …
Preuve par récurrence (cliquer pour déplier / replier)
Etant donnés , on considère l’assertion :
est vraie, puisque :
Supposons vraie pour un certain . Alors :
Si l’on effectue dans la première somme le changement d’indice , il vient :
L’avant-dernière égalité résulte de la formule de Pascal. La dernière s’obtient en ré-insérant les termes et dans le (ils correspondent respectivement à et à ).
L’assertion est donc établie, ce qui achève la démonstration.
Je vous signale par ailleurs l’existence d’un article où la formule du binôme et celle de Leibniz sont étudiées conjointement : ces deux formules sont étroitement liées et l’objet de l’article en question est notamment de montrer en quel sens elles peuvent être vues comme des cas particuliers d’une même formule générale.
7 – Formule du pion
Proposition
L’égalité :
est valable pour tout couple d’entiers naturels tels que .
On l’appelle parfois « formule du pion ».
Cette appellation est sans doute due à une vague analogie avec le jeu d’échec : lorsqu’un pion attaque un pion adverse, il se déplace d’une case en diagonale (disons depuis la case située à l’intersection de la ligne et de la colonne vers celle située à l’intersection de la ligne et de la colonne ), comme l’indique le schéma ci-dessous :
Cette formule peut être établie de deux manières : par un calcul ou bien par un raisonnement combinatoire.
Preuve 1 – par calcul (cliquer pour déplier / replier)
Avec la formule de Fermat, on voit facilement que :
Mais le point de vue combinatoire est clairement plus instructif …
Preuve 2 – combinatoire (cliquer pour déplier / replier)
Etant donné un ensemble de cardinal et un entier tel que , on va dénombrer les couples tels que :
Pour cela, on peut choisir d’abord de façons, puis choisir de façons : au total, on trouve couples.
Une autre méthode consiste à choisir d’abord de façons, puis à « l’entourer » de éléments choisis dans , et ce de façons : au total, on trouve couples.
La formule du pion en résulte.
Vous en trouverez un exemple d’utilisation dans la vidéo Calcul de sommes – 01.
L’illustration ci-dessous permet de visualiser les deux manières de compter :
8 – Formule de Vandermonde
Considérons un ensemble de cardinal . Le nombre de parties de qui sont de cardinal est, par définition . Mais on peut raisonner autrement.
On commence par fixer deux parties complémentaires et de même cardinal (autrement dit : on place une « cloison » dans ). Se donner une partie de de cardinal revient alors à choisir, pour un certain , éléments d’un côté de la cloison et éléments de l’autre. La figure ci-dessous montre l’une des manières de choisir 12 objets parmi 56 :
Pour donné, le nombre de ces double-choix est , c’est-à-dire .
Ces possibilités s’excluent mutuellement, ce qui autorise l’usage du principe additif mentionné en début d’article. En ajoutant, il vient :
Par conséquent :
On peut aisément généraliser : pour dénombrer les parties d’un ensemble de cardinal qui sont de cardinal (avec ). On cloisonne en deux parties de cardinaux respectifs et puis, en raisonnant comme ci-dessus, on parvient à la formule de Vandermonde :
Si l’on convient que dès que ou , cette formule s’écrit plus simplement :
Proposition
Pour tout et pour tout :
En voici une illustration «concrète». Etant donné un jeu de 32 cartes, on peut compter le nombre de «mains» (une main est un ensemble de 5 cartes extraites du jeu) : il en existe évidemment . Si l’on note le nombre de mains comportant exactement rois (pour ), on voit que :
Par exemple, se calcule en considérant que, pour former une main comportant exactement deux rois, il faut choisir deux cartes parmi les quatre rois ainsi que trois cartes parmi les 28 qui restent (celles qui ne sont pas des rois). En notant l’ensemble des mains et celui des mains comportant exactement rois, il est alors clair que :
d’où, en passant aux cardinaux (et les étant deux à deux disjoints) :
ce qui correspond à la formule de Vandermonde pour , et .
9 – Somme d’une colonne dans le triangle de Pascal
Reprenons le triangle de Pascal et examinons ce qui se passe lorsqu’on ajoute les termes d’une colonne, depuis le terme diagonal (qui vaut 1) jusqu’à une certaine profondeur.
Après quelques essais, on conjecture qu’une telle somme est égale au coefficient binomial situé « en-dessous, à droite » de la colonne considérée. Plus formellement :
Proposition
Pour tout et pour tout :
Cette relation est prouvable grâce à une sommation télescopique (pour savoir ce qu’est une « sommation télescopique », voir l’article : Manipulation de sommes à l’aide du symbole ∑)
Là encore, il est intéressant d’interpréter le résultat de manière combinatoire.
Détail de la preuve combinatoire (cliquer pour déplier / replier)
Ce point de vue est celui proposé par GD (voir plus bas dans les commentaires)
Notons la partie de constituée des parties de de cardinal et dont le plus grand élément est , de sorte que
et cette union est évidemment disjointe. Par conséquent :
Or, pour chaque , les éléments de sont les
avec parcourant . De ce fait :
On retrouve ainsi la formule :
10 – Coefficients binomiaux et nombres de Fibonacci
Reprenons le triangle de Pascal et ajoutons cette fois les termes d’une diagonale ascendante, comme indiqué sur la figure ci-dessous :
On voit apparaître une suite, qui commence par : 1, 1, 2, 3, 5, 8, 13, 21, 55, 89, 144, …
Vous aurez probablement reconnu les premiers termes de la célèbre suite de Fibonacci. Rappelons que cette suite est définie par :
Cette observation nous amène formuler la :
Proposition
Pour tout :
Preuve par récurrence (cliquer pour déplier / replier)
L’égalité se vérifie sans peine pour . Supposons-la vraie pour aux rangs et , pour un certain entier et montrons qu’alors :
Pour cela, distinguons deux cas, selon la parité de .
➣ Si est pair, on voit en posant et en invoquant pour commencer la formule de Pascal, que :
On a séparé le de l’avant-dernière ligne en deux, puis posé dans le second morceau. Ainsi :
➣ Si est impair, on pose cette fois et le calcul est similaire :
La proposition est établie.
Preuve combinatoire (cliquer pour déplier / replier)
Imaginons un petite grenouille, confortablement installée au pied d’un escalier. Elle doit le gravir, mais en respectant une consigne : elle ne peut effectuer que des sauts dirigés vers le haut de l’escalier et ne peut franchir qu’une marche ou deux à chaque saut.
De combien de façons la grenouille peut-elle gravir l’escalier ? Notons la réponse, qui dépend bien sûr du nombre de marches …
On calcule facilement « à la main » pour les petites valeurs de :
Ces quelques observations suggèrent la formule générale :
Celle-ci se prouve à l’aide d’une récurrence d’ordre 2.
Manifestement : , . Supposons (hypothèse de récurrence) que et .
Etant donné un escalier de marches (avec ), il existe manières de le gravir en terminant par un saut de deux marches, et il en existe autres se terminant par le franchissement d’une seule marche. Au total : , comme souhaité.
Changeons maintenant de point de vue pour le calcul de . Etant donné un entier naturel , considérons le nombre de façons de gravir un escalier de marches, en effectuant exactement sauts de deux marches (ce qui impose ).
Le nombre total de sauts effectués est alors : . Une telle façon de gravir l’escalier s’identifie à un mot de lettres, chaque lettre pouvant être ‘1’ ou ‘2’ et le mot comportant un total de lettres ‘2’ : il existe tels mots. Le nombre de façons de gravir l’escalier est donc :
En confrontant et , nous retrouvons le fait que :
J’espère que cet article vous sera utile !
Vous pouvez commencer à chercher des exercices relatifs aux coefficients binomiaux. Je vous ai préparé des énoncés ici.
Vos questions ou remarques sont les bienvenues. Vous pouvez laisser un commentaire ci-dessous ou bien passer par le formulaire de contact.
Une petite remarque : dans la démonstration de 9, il est inutile de faire intervenir les applications strictement croissantes.
Il suffit de dénombrer directement le nombre des parties à n+1 éléments d’un ensemble à p+1 éléments, soit n+1 parmi p+1
Puis on distingue selon la valeur du plus grand élément d’une telle partie, qui est nécessairement compris entre n+1 et p+1.
Si ce plus grand élément est k+1 avec n ≤ k ≤ p, on détermine une telle partie par ses n autres éléments dans [1, k].
Et il y a n parmi k telles façons de le faire.
La formule 9 en résulte aussitôt.
Bonjour et merci pour ce commentaire. En effet, ce point de vue est plus simple et donc plus éclairant. Je vais le signaler dans le corps du texte.
Dans l’argument plus rigoureux pour la symétrie des coefficients binomiaux, n’a t’on pas plutôt lorsqu’on écrit l’application ?
Bonjour Joseph,
Le formalisme adopté dans l’article est le bon. D’une manière générale, lorsqu’on définit une application u de manière explicite, on spécifie son ensemble de départ E et son ensemble d’arrivée F ainsi que le “mécanisme” par lequel on associe, à chaque élément de E, son image par u. Un élément générique de E est généralement désigné par une lettre (x, y, …), à la rigueur par un couple ou plus généralement un n-uplet si E est un produit cartésien de deux ou plusieurs ensembles, mais JAMAIS par une expression plus complexe.
Par exemple, il est ILLICITE de définir .
Dans l’exemple qui nous intéresse, on définit en disant qu’à chaque partie de E de cardinal n-k, on associe son complémentaire dans E. Cela dit, il est certain que si une partie de E de cardinal n-k se présente sous la forme du complémentaire d’un certain B, alors son image par est B.