p-listes et combinaisons

Plan du chapitre "Dénombrements"
Définition (p-listes d'éléments quelconques d'un ensemble de cardinal n)
Soit {B} un ensemble fini de cardinal {n\ge1}. Soit {p} un entier, avec {p\ge1}.
Les {p}-uplets {(b_{1},b_{2},\ldots,b_{p})}, où les {b_{k}\in B}, sont appelés {p}-listes d’éléments de {B}.
Le nombre de {p}-listes d’un ensemble {B} de cardinal {n} est {\text{card}(B^{p})=n^{p}}.

Il faut bien noter que dans la définition précédente, les {b_{k}} ne sont pas supposés distincts.
En revanche, l’ordre dans lequel les {b_{k}} apparaissent est important.

Ainsi, si {a,b,c} sont distincts dans {A}, les six {3}-listes suivantes sont distinctes : {\begin{array}{l}(a,b,c),\;(a,c,b),\;(b,a,c),\\(b,c,a),\;(c,a,b),\;(c,b,a)\end{array}}
De même, si {a,b} sont distincts, les huit {3}-listes suivantes sont distinctes : {\begin{array}{l}(a,a,a),\;(a,a,b),\;(a,b,a),\;(a,b,b)\\(b,a,a),\;(b,a,b),\;(b,b,a),\;(b,b,b)\end{array}}

Proposition (p-listes d'éléments distincts d'un ensemble de cardinal n)
Soit {B} un ensemble fini de cardinal {n\ge1}. Soit {p} un entier, avec {1\le p\le n}.
Il y a {\dfrac{n!}{(n-p)!}} {p}-listes {(b_{1},b_{2},\ldots,b_{p})} d’éléments distincts deux à deux dans {B} .

On a supposé {p\le n} car si {p>n} on ne peut former d e{p}-liste d’éléments distincts de {B}.

Si par exemple {B=\{x,y,z,t\}} :

  • le nombre de {2}-listes d’éléments distincts de {B} est {\dfrac{4!}{2!}=12}; les voici : {\begin{array}{rl}(x,y),\;(x,z),\;(x,t),\;(y,x)\\(y,z),\;(y,t),\;(z,x),\;(z,y)\\(z,t),\;(t,x),\;(t,y),\;(t,z)\end{array}}
  • le nombre de {3}-listes d’éléments distincts de {B} est {\dfrac{4!}{1!}=24}; les voici : {\left\{\begin{matrix}(x,y,z)&(x,y,t)&(x,z,y)&(x,z,t)&(x,t,y)&(x,t,z)\\(y,x,z)&(y,x,t)&(y,z,x)&(y,z,t)&(y,t,x)&(y,t,z)\\(z,x,y)&(z,x,t)&(z,y,x)&(z,y,t)&(z,t,x)&(z,t,y)\\(t,x,y)&(t,x,z)&(t,y,x)&(t,y,z)&(t,z,x)&(t,z,y)\end{matrix}\right.}
Proposition (nombre d'injections entre deux ensembles finis)
Soit {A} et {B} deux ensembles finis, avec {\text{card}(A)=p}, {\text{card}(B)=n}, et {1\le p\le n}.
Le nombre d’applications injectives de {A} dans {B} est {\dfrac{n!}{(n-p)!}\cdot}
Démonstration
  Pour voir ce contenu, vous devez : 
Proposition (nombre de permutations d'un ensemble de cardinal n)
Soit {A} un ensemble fini de cardinal {n}. Le nombre de bijections de {A} dans lui-même est {n!}.
Ces applications sont appelées permutations de l’ensemble {A}.
Démonstration
  Pour voir ce contenu, vous devez : 
Définition (p-combinaisons d'éléments d'un ensemble de cardinal n)
Soit {B} un ensemble fini de cardinal {n\ge1}. Soit {p} un entier, avec {p\ge1}.
On dit que {\{b_{1},b_{2},\ldots,b_{p}\}}, où les {b_{k}} sont distincts dans {B}, est une {p}-combinaison d’éléments de {B}.
Le nombre de {p}-combinaisons d’un ensemble {B} de cardinal {n} est {\displaystyle\dbinom{n}{p}=\dfrac{n!}{p!(n-p)!}}.

L’expression “{p}-combinaison d’éléments de {B}” est synonyme de “partie à {p} éléments de {B}“.
Quand on parle de {p}-combinaison, les {p} éléments concernés sont forcément distincts deux à deux (puisque seul compte l’ensemble formé par ces éléments). Si par exemple {B=\{x,y,z,t\}} :

  • il y a {\dbinom{4}{2}=6}{2}-combinaisons” : {\{x,y\},\;\{x,z\},\;\{x,t\},\;\{y,z\},\;\{y,t\},\;\{z,t\}}
  • il y a {\dbinom{4}{3}=4}{3}-combinaisons” : {\{x,y,z\},\;\{x,y,t\},\;\{x,z,t\},\;\{y,z,t\}}

Rappels sur les coefficients binomiaux

Les coefficients {\displaystyle\dbinom{n}{p}} sont appelés “coefficients binomiaux”.
Ils ont été vus au chapitre “Calculs algébriques”. On se contente ici de quelques rappels :

Proposition (les deux relations fondamentales sur les coefficients binomiaux)
On a les identités {\dbinom{n}{p}=\dbinom{n}{n-p}}, et {\dbinom{n}{p}=\dbinom{n-1}{p}+\dbinom{n-1}{p-1}}.
Proposition (formule du binôme dans ℂ)
Pour {x,y} de {\mathbb{C}}, et pour {n} de {\mathbb{N}} : {(x+y)^n=\displaystyle\sum_{k=0}^n\dbinom nk\,x^k\,y^{n-k}}.
En particulier : {(1+x)^n=\displaystyle\sum_{k=0}^n\dbinom nk\,x^k}.

Par exemple, pour tous {x} et {y} de {\mathbb{C}} : {\begin{array}{c}(x+y)^2=x^2+2xy+y^2\\\\(x-y)^2=x^2-2xy+y^2\\\\(x+y)^3=x^3+3x^2y+3xy^2+y^3\\\\(x-y)^3=x^3-3x^2y+3xy^2-y^3\\\\(x+y)^4=x^4+4x^3y+6x^{2}y^2+4xy^3+y^{4}\\\\(x-y)^4=x^4-4x^3y+6x^{2}y^2-4xy^3+y^{4}\end{array}}

Proposition (propriétés de conversion des coefficients binomiaux)
On a les égalités : {\dbinom n{p+1}=\dfrac{n-p}{p+1}\,\dbinom np,\quad\dbinom np=\dfrac np\,\dbinom {n-1}{p-1},\quad\dbinom np=\dfrac n{n-p}\,\dbinom {n-1}p}

Les coefficients binomiaux peuvent être calculés de proche en proche, en les disposant dans un tableau triangulaire connu sous le nom de “triangle de Pascal”.
On écrit ici une fonction (rustique!) pour former le triangle de Pascal sous forme de liste de listes.

def trpascal(N):
from math import factorial as f
return [[f(n)//f(p)//f(n-p) for p in range(n+1)] for n in range(N+1)]

On importe le module pprint pour obtenir un affichage agréable :

>>> from pprint import pprint
>>> pprint(trpascal(9))
[[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1],
[1, 5, 10, 10, 5, 1],
[1, 6, 15, 20, 15, 6, 1],
[1, 7, 21, 35, 35, 21, 7, 1],
[1, 8, 28, 56, 70, 56, 28, 8, 1],
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]

Page précédente : calculs de quelques cardinaux usuels
Page suivante : ensembles dénombrables