ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges
 

Triangle de Pascal & Analyse combinatoire      Calcul des Cnp et Anp  

Dénombrer, c'est calculer le nombre exact d'apparitions d'un phénomène, d'un événement ou la quantité (nombre entier) d'objets clairement définis. Pascal s'est intéressé aux différentes façons de combiner des objets distincts en tenant compte, ou pas, de l'ordre : étant donnés n objets distincts on parle de combinaisons et on note ici   ou C(n,p) le nombre de façons de choisir p éléments parmi ces objets (p = 0,1,...n), aucun ordre n'intervenant dans ce choix. On dit aussi que est le nombre de combinaisons de n objets pris p à p.

Parmi les 26 lettres de l'alphabet (n = 26), une combinaison de trois lettres (p = 3) peut être adk que l'on ne distinguera pas de kad, tout comme, en théorie des ensembles, {a,d,k} = {k,a,d}. Si l'ordre intervient, distinction entre adk et kad, on parle d'arrangements que l'on peut identifier à des n-uplets : (a,d,k) ne (k,a,d); et si p = n, on parle de permutation.

 Les notations à la française : et   pour les arrangements apparaissent en 1904 dans L'encyclopédie des sciences mathématiques pures et appliquées publiée de 1904 à 1916 sous la direction de Jules Molk. Une autre notation est également très utilisée : , on la doit à Euler qui utilisa en fait . Cette notation s'est simplifiée en au 19è siècle. Peu pratique pour la rédaction, elle n'est pas utilisée ici.

Dans le cas d'objets éventuellement identiques, on parle de combinaisons avec répétitions. Par exemple, combien peut-on former de mots de trois lettres ayant un sens ou non avec les lettres a, b, c (comme aaa, aba, baa, cac, ...) ? La réponse est 10. On peut aussi envisager des arrangements et des permutations avec répétition. Le dénombrement de ce type de problème est étudié en fin de page.

Le triangle arithmétique de Pascal  :

La définition donnée en introduction montre que n'est autre que le nombre de parties de p éléments dans un ensemble de cardinal n (ayant n éléments). On en déduit accessoirement que le nombre de parties d'un ensemble (y compris lui-même, 1 cas correspondant à Cnn, et l'ensemble vide, 1 cas correspondant à Cn0) est :

Cn0 + Cn1 + Cn2 + ... Cnn-1 + Cnn  = (1 + 1)n = 2n
formule du binôme de Newton , application

 
On vous distribue 5 cartes d'un jeu de 32 sans jokers. Combien y a-t-il de possibilités de recevoir 3 rois ?  
Rép : .

Le triangle arithmétique de Pascal est une table à double entrée dont l'algorithme de construction permet de calculer aisément les combinaisons Cnp en vertu de la formule de récurrence :


 
0
1
2
3
4
5
6
7
8

9

10

0
1
   
1
1
1
   
2
1
2
1
   
3
1
3
3
1
   
4
1
4
6
4
1
   
5
1
5
10
10
5
1
   
6
1
6
15
20
15
6
1
   
7
1
7
21
35
35
21
7
1
   
8
1
8
28
56
70
56
28
8
1
   

9

1 9 36 84 126 126 84 36 9 1  

10

1 10 45 120 210 252 210 120 45 10 1

Explication et usage, programmation sur tableur :                     Calcul des combinaisons (JavaScript) :

Le fameux triangle était cependant connu depuis fort longtemps car on le retrouve dans des travaux d'arithmétique chinoise au début du 14è siècle en tant que compilation de résultats antérieurs, sans doute du 11è siècle, époque à laquelle Omar Khayyam l'utilisa indépendamment dans ses travaux sur l'arithmétique. Plus tard Al-Kashi, le décrira dans sa Clé de l'arithmétique (1427).

Dénombrement des arrangements, permutations et combinaisons ainsi que des applications, injections et bijections  :

Voici l'arbre d'un choix ordonné de 3 objets parmi 4. On parle d'arrangement de 3 objets parmi 4. Par ordonné, on veut signifier par exemple que :

Un arrangement de p éléments est assimilable à un p-uplet (a1, a2, ..., ap). Une combinaison est assimilable à un ensemble {a1, a2, ..., ap}.


A
np = 4 x 3 x 2 = 24.

On déduit facilement de cet exemple (principe de la multiplication) que le nombre d'arrangements distincts de p objets parmi n est donné par le nombre noté tel que : Ano  = 1 et, pour p non nul : 

= n(n - 1)(n - 2)(...)(n - p + 1).

  Remarquer que Ann = n! (factorielle n) : lorsque n = p, on parle de permutations de n objets distincts. Rappelons que la notation n!, factorielle de n, est le nombre 1 x 2 x 3 x ... x n.

Christian Kramp et la notion de factorielle :             Stirling

Un exercice de dénombrement niveau 3ème/2nde , Dénombrement et probabilités (Bac S/ES)

à chaque arrangement de p éléments correspond p! façons (factorielle p) de changer l'ordre. Par suite :

Cnp = Anp / p!

Lien avec le nombre d'injection et de bijections :   

Le nombre est le nombre d'injections d'un ensemble Ep vers un ensemble Fn (p n). Lorsque p = n, il s'agira donc du nombre de bijections de En vers un ensemble Fn. Il y a donc Ann = n! bijections.

Injections, surjections, bijections :                     Nombre de surjections :

Rappelons aussi que l'on peut définir np applications d'un ensemble Ep vers un ensemble Fn (attention à l'ordre). En effet, une telle application s'identifie à un n-uplet (im1, im2, ..., imp), les images imk étant choisies parmi n (deux éléments de Ep peuvent avoir ici la même image), d'où l'existence de  n x n x ... x n = np cas possibles (p facteurs).

Arrangement avec répétition :  

                  


1. En construisant une application convenable, montrer qu'un ensemble de cardinal n admet 2n parties (y compris lui-même et l'ensemble vide).
Le résultat donné, 2n, vous aidera logiquement (0 ou 1...) à exhiber cette application.

2. Un ascenseur part du rez-de-chaussée d'un immeuble de 8 étages avec 10 personnes à bord. On sait que 2 personnes descendront au 3ème étage et 3 au 7ème. Sachant que tout le monde descendra au plus tard au 8ème étage, de combien de façons distinctes ces
10 personnes peuvent-elles quitter l'ascenseur ?
Rép : C102 x C83 × 65 = 19 595 520 façons ! Le 65 s'explique par le fait que 6 étages peuvent être desservis de façon quelconque par les 5 passagers restants. Tout se passe comme si on applique un ensemble de cardinal 5 vers un ensemble de cardinal 6 : il y a 65 applications possibles.


Trois exercices de Dénombrement et probabilités (niveau Bac S/ES)

Programme JavaScript calculant combinaisons et arrangements :

  Le programme est très simple. Les fonctions comb() et fac() sont identiques à celles présentes dans le calcul des combinaisons à la page Blaise Pascal.

  Au-delà de 16 chiffres significatifs, on dépasse la capacité de traitement en nombres entiers du langage JavaScript. Les résultats n'on alors plus guère de sens, sinon un ordre de grandeur.



<SCRIPT LANGUAGE=JavaScript>
function go()
{
var nn,n,k
nn="";;k="";
ok=1;
while (ok=1)
{
nn=eval(prompt("Entrez n :",nn))
if(nn==null) return
k=eval(prompt("Entrez p :",k))
if(k==null){ok=0}
if(k<nn-k) {c=comb(nn,k)} else {c=comb(nn,nn-k)}
a=c*fac(k)
if(ok==1){alert("A("+nn+","+k+") = "+a+" , C("+nn+","+k+") = "+c)};
if(!confirm("Autre calcul ?")) return
}
}

function fac(n)
{
if (n<=1){return 1};
f=1;
for(i=2;i<=n;i++){f=f*i}
return f
}

function comb(n,p)
{
if (n==p || p==0){return 1};
if (p==1){return n};
num=n;
for(i=1;i<=p-1;i++){num=num*(n-i)}
return num/fac(p)
}
</SCRIPT>  

Arrangements, permutations et combinaisons avec répétition :

a/  Arrangement avec répétition :    

Un arrangement avec répétition de p éléments parmi n objets distincts  a1, a2, ..., an consiste en un choix ordonné de p objets choisis parmi les n en tenant compte de l'ordre de ces éléments : c'est un p-uplet (ai1, ai2, ..., aip)

Un arrangement avec répétition s'identifie donc une application d'un ensemble Ep de cardinal p vers un ensemble Fn de cardinal n. En notant à leur nombre (à = "A tilda") , on a ainsi :

b/  Permutation avec répétition :    

Une permutation avec répétition de n éléments consiste en un rangement de n objets (n-uplet) distincts ou non sachant qu'il n'y a que k objets distincts parmi les n. Notons p1, p2, ..., pk les nombres de répétition des objets 1, 2, ..., k dans la collection. On a p1 + p2 + ... + pk = n. Si tous les objets étaient distincts, nous aurions n! permutations distinctes. Les permutations des objets 1, 2, ..., k laissent invariante une permutation donnée, le nombre total de permutations avec répétition est donc ( factorielle) :

  Combien y a-t-il de "mots" distincts, n'ayant pas nécessairement de sens, obtenus à partir du mot pape, ? Il y a 4 lettres, dont 2 "p". Le dénominateur de notre formule est 2!1!1! = 2. On a donc 4!/2 mots, soit 12 : Vérifions cela : commençant par p, on a ppae, ppea, paep, pape, pepa, peap (3! = 6 cas); commençant par a, on a aepp, apep, appe (3!/2! = 3 cas), de même si on commence par e : on a bien en tout 6 + 3 + 3 = 12 cas.
  Combien y a-t-il de "mots" distincts, n'ayant pas nécessairement de sens, obtenus à partir du mot abracadabra ? Il y a 11 lettres, dont 5 "a", 2 "b", 2 "r", 1 "c" et 1 "d". Le dénominateur de notre formule est 5!2!2!1!1! = 480. On a donc 11!/480 mots, soit 83160. Faisant confiance à la formule, nous ne ferons pas la liste de tous ces cas...

c/  Combinaison avec répétition :   

Une combinaison avec répétition de p éléments parmi n objets distincts consiste en un choix de p objets distincts ou non parmi les n en ne tenant pas compte de l'ordre des éléments choisis. Le dénombrement de ces combinaisons est un peu plus difficile à évaluer. Leur notation n'est pas normalisée, on rencontre un peu de tout. On utilisera ici Č(n,p).

  Première formule de récurrence :

Comme pour les combinaisons "ordinaires", on peut donner sans difficulté une première formule de récurrence : parmi les combinaisons avec répétition contenant un élément a, notons A (resp. B) l'ensemble des combinaisons qui contiennent (resp. ne contiennent pas) a. On a Č(n,p) = Card A + Card B.

Dans l'ensemble A, retirons une seule fois a à chacune des combinaisons : on a Č(n,p-1) combinaisons de cette sorte, et c'est le cardinal de A. L'ensemble B est constitué des combinaison avec répétition ne contenant pas a : on en a Č(n-1,p) et c'est le cardinal de B. Finalement, ce raisonnement, qui sous-entend n ≥ 2 et 2 ≤ p ≤ n-1, fournit :

 Č(n,p) =  Č(n,p-1) +  Č(n-1,p)          (r)

On peut donner un sens aux cas particuliers permettant le bon "fonctionnement" de cette relation de récurrence :

Finalement, on peut écrire :

Č(n,p) =  Č(n,p-1) +  Č(n-1,p) , n ≥ 2, 0 ≤  p ≤ n-1

n = p ne peut convenir à cause de Č(n-1,p). C'est dire que le calcul de Č(n,n) pose problème mais il y a une solution étudiée plus loin...

Č(n,2) = Č(n,1) + Č(n-1,2)
Č(n-1,2) = Č(n-1,1) + Č(n-2,2)
Č(n-2,2) = Č(n-2,1) + Č(n-3,2)
...
Č(3,2)    = Č(3,1) + Č(2,2)

Faisons la somme membre à membre :

Č(n,2) = Č(n,1) + Č(n-1,1) + Č(n-2,1) + ... + Č(3,1) + Č(2,2)
          =     n     +   (n-1)    +   (n-2)    + ... +    3      +    3

Mais 3 = 2 + 1. On voit donc que Č(n,2) est la somme des n premiers entiers naturels : Č(n,2) = n(n + 1)/2.

  Seconde formule de récurrence et calcul direct :

Vu les difficultés du calcul par récurrence des Č(n,p), on aimerait avoir une formule simple et directe ! La voici : chaque combinaison avec répétition contient p éléments distincts ou non, donc lorsqu'on écrit toutes les combinaisons, on écrit en tout pČ(n,p) éléments où chacun d'eux jouent le même rôle. C'est dire que si on se fixe un élément a comme nous l'avons fait dans la recherche de la formule de récurrence, celui-ci est utilisé pČ(n,p)/n fois.

Supposons avoir ordonné chaque combinaison avec répétition en commençant par a et, comme précédemment, nous allons supprimer une seule fois a en début d'écriture en illustrant le raisonnement avec le cas de 4 éléments a, b, c, d pris 3 à 3. Nous avons dans ce cas 20 combinaisons à répétions que l'on peut ordonner ainsi :

aaa, aab, aac, aad, abb, abc, abd, acc, acd, add || bbb, bbc, bbd, bcc, bcd, bdd || ccc, ccd, cdd || ddd

La partie bleue ne contient pas de a (on les a épuisés dans la partie rouge), négligeons-la :

aaa, aab, aac, aad, abb, abc, abd, acc, acd, add         (1)

Selon le résultat précédent, on a écrit 3Č(4,3)/4 = 15 fois la lettre a, ce que l'on vérifie facilement. Plus généralement on en aurait pČ(n,p)/n.

Mettons maintenant le premier a à part :

aa , ab , ac , ad , bb , bc , bd , cc , cd , dc , dd         (2)

la liste de la ligne (2) représente les combinaisons à répétition de 4 éléments pris 2 à 2 au nombre de Č(4,2), plus généralement Č(n,p-1) et cette ligne contient donc 2Č(4,2)/4 = 4(4+1)/4 = 5 fois la lettre a, ce que l'on vérifie. Plus généralement, on en aurait (p-1)Č(n,p-1)/n.

Pour dénombrer tous les a, il nous faut maintenant ajouter ceux que l'on a retirés ! : il y en a autant que de combinaisons dans la ligne 2, soit Č(4,2) et plus généralement Č(n,p-1) comme déjà dit. Finalement, nous obtenons une formule de récurrence plus opérationnelle que la précédente car seul p est affecté :

pČ(n,p)/n = (p-1)Č(n,p-1)/n + Č(n,p-1)

Ce qui s'écrit plus simplement : 

pČ(n,p) = (n + p - 1)Č(n,p-1) , n ≥ 1, 1 ≤  p ≤ n

Faisons décroître p par pas de 1 :

pČ(n,p) = (n + p - 1)Č(n,p-1)
(p-1)Č(n,p-1) = (n + p - 2)Č(n,p-2)

(p-2)Č(n,p-2) = (n + p - 3)Č(n,p-3)

...
3
Č(n,3) = (n + 2)Č(n,2)
2
Č(n,2) = (n + 1)Č(n,1)
 

Multiplions membre à membre et simplifions : p!Č(n,p) = (n + 1)(n + 2)...(n + p - 1)Č(n,1). On a vu que Č(n,1) = n. Donc, en divisant par p! et sachant que :

On en déduit la formule, fort simple :


 


© Serge Mehl - www.chronomath.com