Paires et triplets

Nous désignons ici par 'triplet' tout ensemble à 3 éléments.
Le programme ci-dessus génère des ensembles et montre pour chacun d'eux toutes les paires et tous les triplets.

Parties à 2 élements de E:

Parties à 3 élements de E:

Générez plusieurs exemples comme ci-dessus.
Cn2 désigne le nombre de paires d'un ensemble à n éléments et Cn3 celui de ses triplets.
Voici deux tableaux récapitulatifs.
Pouvez vous prévoir
la formule pour Cn2?
Pouvez vous prévoir
la formule pour Cn3?
n Cn2
0 0
1 0
2 1
3 3
4 6
5 10
6 15
n Cn3
0 0
1 0
2 0
3 1
4 4
5 10
6 20

Coefficients Cnp

Nous notons Cnp 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 au lieu de Cnp on trouve aussi n p
Voici quelques propriétés évidentes:
Cnp= 0 si p>n
Cn0 =1 ∀ n (une seule partie vide)
Cnn = 1 ∀ n (une seule partie pleine)
Cn1 = n ∀ n (n singletons)
Cnp= C n n p  ∀ 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)
p = 0 n C n p = 2 n (parce que le membre de gauche donne toutes les parties de E)
Voici maintenant une propriété moins évidente:
C n p = C n 1 p 1 + C n 1 p 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:
d'où le résultat.
La relation qui précède permet d'organiser les coefficients Cnp 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:
C n p = 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 Cnp sont des nombres très importants intervenant dans toutes les branches des mathématiques:

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 Cnp, 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:

Les versions récentes de python proposent une fonction 'combinations' dans le module standard 'itertools'.