$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Résumé de cours : Dénombrement

Cardinal
  • On appelle cardinal d'un ensemble fini $E$ le nombre d'éléments de $E$. On le note $|E|$, $\#E$ ou $\textrm{card}(E)$.
  • Soient $E$ et $F$ deux ensembles finis. Alors
    • Si $E\subset F$, on a $\textrm{card}(E)\leq \textrm{card}(F)$, avec égalité si et seulement si $E=F$.
    • $\textrm{card}(E\times F)=\textrm{card}(E)\times \textrm{card}(F)$.
    • $\textrm{card}(E\cup F)=\textrm{card}(E)+\textrm{card}(F)-\textrm{card}(E\cap F)$.
    • Le cardinal des applications de $E$ dans $F$ vaut $(\textrm{card F})^\textrm{card(E)}.$
    • $\textrm{card}(\mathcal P(E))=2^{\textrm{card}(E)}$.
  • Théorème : Une application entre deux ensembles finis de même cardinal est injective si et seulement si elle est surjective si et seulement si elle est bijective.
Listes, permutations, combinaisons
  $E$ désigne un ensemble de cardinal $n$.
  • On appelle $p$-liste d'éléments de $E$ tout $p$-uplet $(x_1,\dots,x_p)$ d'éléments de $E$. Il y a $n^p$ $p$-listes d'éléments de $E$.
  • Le nombre de $p$ listes d'éléments distincts de $E$ vaut $n(n-1)\dots (n-p+1)$. Une telle $p$-liste est parfois appelée un arrangement.
  • En particulier, le nombre de permutations de $E$ est égal à $n!$.
  • Proposition : Le nombre d'injections d'un ensemble à $p$ éléments dans un ensemble à $n$ éléments vaut $n(n-1)\dots(n-p+1)$.
  • On appelle combinaison de $p$ éleménts de $E$, ou encore $p$-combinaison de $E$ toute partie à $p$ éléments de $E$.
  • Théorème : Le nombre de combinaisons de $p$ éléments de $E$ (de cardinal $n$) est $\binom np$.