Dans l'exemple qui suit nous listons à droite toutes les paires de
l'ensemble donné E à gauche en exemple.
C2,n désigne le nombre de
paires d'un ensemble à n éléments.
Générez plusieurs exemples comme ci-dessus.
Pouvez vous prévoir la formule pour C2,n?
n
C2,n
0
0
1
0
2
1
3
3
4
6
5
10
6
15
Triplets
Nous désignons ici par triplet
tout ensemble à 3 éléments.
Dans l'exemple qui suit nous listons à droite toutes les parties à 3
éléments de
l'ensemble donné F à gauche en exemple.
C3,n désigne le nombre de
triplets dans un ensemble à n éléments.
Générez plusieurs exemples comme ci-dessus.
Pouvez vous prévoir la formule pour C3,n?
n
C3,n
0
0
1
0
2
0
3
1
4
4
5
10
6
20
Coefficients Cp,n
Nous notons Cp,n le nombre de
parties à p éléments dans un ensemble E à n éléments. On
dit
encore le nombre
de combinaisons de p dans n.
En pratique les notations standard, au lieu de Cp,n sont plutôt:
C
p
n
et
(
n
)
p
c'est uniquement pour des raisons typographiques liées au langage html que nous avons adopté ici ce particularisme.
Voici quelques propriétés évidentes:
Cp,n= 0 si p>n
Co,n =1 ∀ n (une seule
partie vide)
Cn,n = 1 ∀ n (une seule
partie pleine)
C1,n
= n ∀ n (n singletons)
Cp,n=Cn-p,n ∀ n et
∀p<n (le complémentaire d'une
partie à p éléments est une partie à n-p éléments, il y en a donc
autant de chaque sorte)
Co,n+C1,n+C2,n+...+Cn-1,n+Cn,n=2n
(parce que le membre de gauche donne toutes les parties de E)
Voici maintenant une propriété moins évidente:
Cp,n=Cp-1,n-1+Cp,n-1
pour n ≥ 1
et n-1 ≥ p>1
Il s'agit d'une relation de récurrence qui se démontre un peu de la
même manière que pour la formule qui donne le nombre total de
toutes
les parties d'un ensemble.
Soit F un ensemble
à n-1 élément. Soit maintenant x un élément qui
n'appartient pas à F et soit E=F ∪ {x}, de sorte que E est un ensemble
à n éléments dont F est une partie.
Les parties de E à p éléments se divisent en deux catégories:
Celles qui ne contiennent pas l'élément x, qui sont donc des parties de F, leur nombre est
donc Cp,n-1
Celles qui contiennent l'élément x, obtenues par adjonction
de x à une partie de F à p-1 éléments, leur nombre est donc Cp-1,n-1
d'où le résultat.
La relation qui précède permet d'organiser les coefficients Cp,n en une
structure triangulaire où chaque ligne se déduit de celle qui précède,
il s'agit du
triangle dit 'de Pascal', connu en fait depuis le début du
14° siècle par les mathématiciens chinois (Chu Shï-kié), et en occident
par Petrus Apianus dès 1527.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
Partant de la relation de récurrence et de la définition de factorielle
n
n!= 1 si n<=1
n!=1x2x3x.....x(n-1)xn pour n ≥ 2
on a: Cp,n=n!/((n-p)!p!)=n(n-1)(n-p+1)/p!
Formule de fait peu adaptée au calcul pratique de ces coefficients à
cause de la croissance extrêmement rapide de la factorielle.
Les Cp,n sont
des nombres très importants intervenant dans toutes les
branches des mathématiques:
En algèbre (coefficients du développement de (a+b)n,
entre autres).
En calcul des probabilités.
Et dans bien d'autres domaines.
Café Python
Ce programme calcule toutes les parties à p éléments d'un ensemble à n
éléments:
Ce programme calcule le triangle de Pascal et les coefficients Cp,n, en faisant appel à la notion de 'générateur':
Ce programme calcule toutes les parties à p éléments d'un ensemble à
n
éléments sans récursivité et sans filtrage, en faisant appel à la
notion de 'générateur'. Il suppose que l'ensemble E est muni d'un ordre
naturel:
En pratique les notations standard, au lieu de Cp,n sont plutôt: