Ensembles finis (2/2)

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}}

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.}

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'injections de {A} dans {B} est {\dfrac{n!}{(n-p)!}\cdot}

Soit {A} un ensemble fini de cardinal {n}. Le nombre de bijections de {A} dans lui-même est {n!}.
On les appellent permutations de l'ensemble {A}.

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\}}

On a l'identité :{\dbinom{n}{p}=\dbinom{n}{n-p}}.

De même : {\dbinom{n}{p}=\dbinom{n-1}{p}+\dbinom{n-1}{p-1}}.

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}}

On a les égalités : {\begin{array}{c}\dbinom n{p+1}=\dfrac{n-p}{p+1}\,\dbinom np,\quad\dbinom np=\dfrac np\,\dbinom {n-1}{p-1}\\\\\dbinom np=\dfrac n{n-p}\,\dbinom {n-1}p\end{array}}

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.

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