Médaille
N°1 pour apprendre & réviser du collège au lycée.

Factorielle, k-uplet, permutation et combinaison

Déjà plus de

1 million

d'inscrits !

Définitions

  • On appelle cardinal de EE, ensemble fini, le nombre de ses éléments.
  • On le note : Card(E)\text{Card}( E), et c’est un entier naturel.
  • Soit pNp\in \mathbb N^* et A1,A2,,ApA1,\,A2,\,…,\,A_p des sous-ensembles non vides d’un ensemble fini EE.
  • P={A1,A2,,Ap}\mathcal P=\lbrace A1,\,A2,\,…,\,A_p\rbrace est une partition de EE si et seulement si :
  • Le produit cartésien de deux ensembles EE et FF est noté E×FE\times F.
  • Il est défini par : E×F={(x,y) avec xE et yF}E\times F=\lbrace(x,\,y) \text{ avec $x\in E$ et $y \in F$}\rbrace.
  • Il s’agit de l’ensemble des couples dont le premier élément est un élément de EE et le second un élément de FF.
  • Le produit cartésien de nn ensembles est :

E1×E2××En={(x1,x2,,xn) avec, pour tout i{1,2,,n} : xiEi}\begin{aligned} E1\times E2\times … \times En=&\big\lbrace(x1,\,x2,\,…,\,xn) \ &\text{ avec, pour tout $i\in\lbrace1,\,2,\,…,\,n\rbrace$ : $x_i\in E_i$}\big\rbrace \end{aligned}

  • Les éléments d’un produit cartésien de kk ensembles sont appelés des k-listesk\text{-listes} ou des k-upletsk\text{-uplets}.
  • Un k-upletsk \text{-uplets} d’un ensemble fini EE de nn éléments est une liste de kk éléments choisis parmi les nn éléments de EE.
  • On appelle permutation d’un ensemble EE de nn éléments tout n-upletn \text{-uplet} d’éléments distincts.
  • Le nombre n!n! se lit : « factorielle n ».
  • n!=n×(n1)××2×1n!=n\times(n-1)\times…\times2\times1.
  • 0!=10!=1 et (n+1)!=(n+1)×n!(n+1)!=(n+1)\times n!
  • Soit EE un ensemble fini de nn éléments et kk un entier tel que 0kn0\leq k\leq n.
  • On appelle combinaison de kk éléments de EE toute partie de EE ayant kk éléments.
  • Une combinaison est un sous-ensemble.
  • Le coefficient binomial correspond au nombre de combinaisons.

Formules et propriétés

Principe additif Card(AB)= Card(A)+Card(B) Card(AB)\begin{aligned}\small {\text{Card}(A\cup B)=\ }&\small{\text{Card}(A)+\text{Card}(B)} \ &\small {-\ \text{Card}(A\cap B)}\end{aligned} AA et BB ensembles finis
Partition Card(E)= Card(A1)+Card(A2)++Card(Ap)\begin{aligned} \small \text{Card}(E)=\ &\small \text{Card}(A1)+\text{Card}(A2 ) \ &\small+…+\text{Card}(Ap)\end{aligned} {A1,A2,,Ap}\small \lbrace A1,\,A2,\,…,\,Ap \rbrace partition de E\small E, ensemble fini (p>1)\small (p>1)
Produit cartésien Card(E1××En)= Card(E1)××Card(En)\begin{aligned}\small\text{Card}( E1\times … \times En)=\ &\small\text{Card}(E1 )\times … \ &\small \times \text{Card}(En)\end{aligned} E1,,En\small E1,\,…,\,En ensembles finis (n1)\small (n\geq 1)
Nombre NN de parties N=2n\small N=2^n EE ensemble à nn éléments
Nombre NN de k-upletsk \text{-uplets} N=nk\small N=n^k EE ensemble à nn éléments (n1)\small (n\geq 1)
Nombre NN de k-upletsk \text{-uplets} distincts N=n×(n1)××(nk+1)=n!(nk)!\begin{aligned}\small N&\small= n\times (n-1)\times … \times (n-k+1) \ &\small=\dfrac{n!}{(n-k)!} \end{aligned} EE ensemble à nn éléments (n1\small (n\geq 1 et 1kn)\small 1\leq k\leq n)
Nombre NN de permutations N=n!\small N=n! EE ensemble à nn éléments (n1)\small (n\geq 1)
Nombre NN de combinaisons N=(nk)=n!k!(nk)!=n×(n1)××(nk+1)k!\begin{aligned} \small N&\small=\footnotesize {\binom nk}\small =\dfrac{n!}{k!(n-k)!} \ &\small= \dfrac{n\times(n-1)\times…\times(n-k+1)}{k!} \end{aligned} EE ensemble à nn éléments (1kn)\small (1\leq k\leq n)
Propriétés du coefficient binomial (n1)=n(n0)=(nn)=1k=0n(nk)=2n\begin{aligned} \footnotesize {\binom n1}&\small=n \ \footnotesize {\binom n0}&\small=\footnotesize{\binom nn}=1 \ \footnotesize {\sum_{k=0}^n \binom nk}&\small= 2^n \end{aligned} n0\small n\geq 0
Symétrie du coefficient binomial (nk)=(nnk)\footnotesize{\displaystyle \binom nk} \small= \footnotesize{\displaystyle\binom n{n-k}} 0kn\small 0\leq k\leq n
Formule de Pascal (nk)=(n1k)+(n1k1)\footnotesize{\displaystyle\binom nk} \small = \footnotesize{\displaystyle\binom {n-1}k+\binom{n-1}{k-1}} n2\small n\geq 2 et 1kn1\small1\leq k\leq n-1

Triangle de Pascal

  • Nous plaçons dans un premier temps les coefficients suivants (selon les propriétés vues plus haut) :
  • (n0)=1\binom n0=1 ;
  • (nn)=1\binom nn=1 ;
  • (n1)=n\binom n1=n.
  • Nous faisons la somme du coefficient juste au-dessus et de celui à gauche de ce dernier.
  • Nous pouvons également utiliser la propriété de symétrie.
  • Triangle de Pascal, jusqu’à n=9n=9 :

nk^{k\,\rightarrow}_{n\,\downarrow} 00 11 22 33 44 55 66 77 88 99
00 11
11 11 11
22 11 22 11
33 11 33 33 11
44 11 44 66 44 11
55 11 55 1010 1010 55 11
66 11 66 1515 2020 1515 66 11
77 11 77 2121 3535 3535 2121 77 11
88 11 88 2828 5656 7070 5656 2828 88 11
99 11 99 3636 8484 126126 126126 8484 3636 99 11