Analyse combinatoire et dénombrement

Bonjour, dans ce chapitre, nous allons l’analyse combinatoire et le dénombrement.

Nous allons aborder plusieurs notions ici :

  • La factorielle.
  • Les permutations et les arrangements d’objets.
  • La loi binomiale et les coefficients binomiaux.
  • La formule et le triangle de Pascal.
  • Le binôme de Newton.
  • Permutations avec répétitions.
  • Les combinaisons avec répétitions.
  • Multinôme de Newton.
Cadre de citation: Idéal pour citer les propos de quelqu’un dans un texte. Pour utiliser ce cadre il suffit de copier et coller le code ci-dessous.

Les permutations, les combinaisons et les arrangements d’objets :

Avant de détailler chaque notion, nous allons présenter les choses de manière la plus succincte possible, et pour ceci, nous allons faire un schéma des différentes situations sur lesquelles nous pourrions tomber pour dénombrer des objets. En effet, toutes ces situations (permutations, combinaison et arrangements) sont des dénombrements d’objets.

Expliquons ce schéma point par point, et voyons comment nous pouvons en arriver à ces choix et leurs conséquences.

Nous allons prendre un exemple type, et voir quels sont les différents débouchés en fonction du choix des paramètres de départ.
Tout d’abord, considérons l’ensemble des lettres de l’alphabet, autrement dit, 26 lettres, et à partir de ces 26 lettres, nous voulons savoir combien de mots de 4 lettres on peut construire. On va essayer de déterminer, en se basant sur notre schéma plus haut, dans quelle situation nous sommes. Premièrement, nous ajouterons que les mots que l’on peut faire ne sont pas nécessairement des mots existants dans notre vocabulaire, par exemple, écrire le mot « ADVC » est un mot tout à fait compatible avec notre situation.

Ensuite, posons nous la question suivante : Sommes nous dans le cadre d’un résultat ordonné ? Oui, pourquoi ? L’ordre est important, car écrire le mot « ADVC » n’est pas pareil qu’écrire le mot « CVDA », pourtant, les même lettres sont utilisées, il y a donc bien une relation d’ordre.

A présent, allons plus loin : sommes nous dans le cadre de répétitions ? Oui, car, rien ne nous interdit d’utiliser plusieurs fois la même lettre, et par exemple d’écrire le mot « AAAA ».
Donc, si on s’en réfère au schéma, nous sommes dans la situation ou la formule à utiliser est n^p. Qu’est ce que n et qu’est-ce que p dans notre situation ? Il y a 26 lettres dans l’alphabet, donc n=26 et, nous avons p=4, car nous pouvons faire un choix de 4 lettres parmi 26, par conséquent, la formule est 26^4.

On pourrait schématiser ceci de cette manière :

Ceci s’appelle un arrangement avec répétitions et la formule est, comme dite plus haut, n^p

Situation un peu différente maintenant… Comment pourrions nous décrire la situation si les lettres que nous prenons pour écrire notre mot ne peuvent pas se répéter ? Un arrangement sans répétition évidemment, mais comment pourrions-nous décrire cela ? Voyons cela avec le schéma ci-dessous :

En effet, lorsqu’on place notre première lettre, ne pouvant plus la placer une seconde fois, il nous reste toutes les lettres de l’alphabet moins celle que nous venons de mettre. De même, lorsque la deuxième lettre est placée, on ne peut plus placer ni celle que l’on vient de placer, ni la première, il nous en reste donc 24, et ainsi de suite.

Il faut trouver un moyen d’exprimer cette situation de manière générale…
On pourrait être tentés d’écrire ceci (A_n^k l’écriture utilisée pour décrire un arrangement sans répétitions) :

A_n^k=n{!}=n \times (n-1) \times (n-2) \times ... \times 1

le problème ici, c’est que cette formule ne colle pas du tout avec notre situation. Nous n’avons pas 26 objets à placer, mais seulement 4 ! Il faut donc trouver un moyen de se débarrasser des 22 autres…

En réalité, il ne s’agit pas ici de trouver une démarche intuitive de simplification de calcul, mais plutôt une astuce… Par exemple, on pourrait poser :

A_n^k=\displaystyle{\frac{n \times (n-1) \times (n-2) \times ... \times 1 }{(n-p){!}}}

En effet, en divisant par (n-p){!}, on s’assure de ne garder que les valeurs que nous voulons. Regardez ce qui se passe quand on adapte la formule à notre situation :

\displaystyle{\frac{26{!}}{(26-4){!}}=\frac{26\times 25 \times 24 \times 23 \times 22 \times ... \times 1}{22 \times 21 \times ... \times 1}}

On voit immédiatement qu’il est possible de simplifier :

\displaystyle{ \frac{26 \times 25 \times 24 \times 23 \times 22 \times ... \times 1}{22 \times 21 \times ... \times 1}}=26 \times 25 \times 24 \times 23~

C’est exactement le résultat que nous voulions, par conséquent, la formule d’arrangement sans répétition est :

\displaystyle{A^p_n=\frac{n{!}}{(n-p){!}}}. A^p_n

Maintenant, changeons de nouveau de situation (nous verrons qu’il s’agit en fait d’un cas particulier de la situation du dessus), et supposons que nous ne possédons pas toutes les lettres de l’alphabet, mais uniquement 4 (différentes), et que nous devons faire un mot de 4 lettres également. Cette fois, n=4, mais p=4 également… Sommes nous donc dans la première situation ? Non, pourquoi ? Car nous ne pouvons pas utiliser plusieurs fois la même lettre, par conséquent, voyons ce que ça peut donner sur un schéma :

Il est assez facile de comprendre quel mécanisme on pourrait utiliser pour généraliser une formule, en effet, on voit que, étant donné que n=4, on a quelque chose qui ressemble à :

A^p_n=n \times (n-1) \times (n-2) \times ... \times 2 \times 1

En fait, c’est tout à fait la formule qui correspond, et, on va l’écrire simplement n{!}, car n{!}=n \times (n-1) \times (n-2) \times ... \times 2 \times 1

En fait, si on regarde bien ce qui se passe avec cette situation, on peut se rendre compte de quelque chose… Ceci n’est qu’une situation particulière d’arrangement sans répétition. En effet, si on considère que n=p, alors :

\displaystyle{\frac{n{!}}{(n-p){!}}=\frac{n{!}}{0{!}}=n{!}}

C’est exactement le cas de figure ou on doit arranger 4 lettres dans un mot de 4 lettres, comme vu ci -dessus.

Que se passe t-il à présent si n < p ? Ce n’est tout simplement pas possible, cela revient à vouloir arranger plus d’objets que nous avons de cases dans lesquelles les placer. Par exemple, si on veut arranger 5 éléments dans 4 cases, il nous restera toujours un cinquième élément, dont on ne pourra rien faire, par conséquent :

\displaystyle{\frac{n{!}}{(n-p){!}}=0}, si p > n