Progression

  • Ensemble équipotents

    2 ensembles E et F sont dits équipotents (écrit \(E\sim F\)) s'il existe une bijection \(\varphi\) de \(E\to F\)

  • Propriétés de la relation d’équipotence

    Réflextive, symétrique et transitive

  • Équipotence et cardinal

    E et F ont le m\^eme cardinal \(\iff E\sim F\)

  • Définition d’un ensemble fini

    E est fini si \(E=\varnothing\) ou s'il existe \(n\in\mathbb{N}\), tel que \(E \sim [\![1;n]\!]\)

  • Lemnes fondamentaux sur les ensemble finis

    Il existe une injection de \([\![1;n]\!] \to [\![n,m]\!] \iff n\leq m\) et Il existe une bijection de \([\![1;m]\!] \to [\![1,n]\!] \iff n=m\)

  • Cardinalité et surjectivité, injectivité, bijectivité

    Soit \(f:E\to F\) une application. Si \(f\) est injective, Card(E)\(\leq\)Card(F). Si \(f\) est surjective, Card(E)\(\geq\)Card(F). Si Card(E)=card(F), \(f\) est bijective \(\iff\) f est injective \(\iff\) f est surjective

  • Propriétés d’un sous-ensemble d’un enemble fini \(A\subset E\)

    A est fini, de cardinal inférieur ou égal à E et si le cardinal est égal à celui de E, A = E

  • \(Card(A\cup B\)

    \(\card(A\cup B) = \card(A) + \card(B) - \card(A\cap B)\)

  • \(\card(A\setminus B)\)

    \(\card(A\setminus B) = \card(A) - \card(A\cap B)\)

  • Lemme des bergers

    Compter les éléments de E revient à compter les éléments de l’application réciproque

  • Principe des tiroirs

    Soit \(E,F\) 2 ensembles finis tel que \(card(E) \geq \card(F)\) alors il n'existe pas d'affectation injective de \(E\to F\), i.e soit \(f:E\to F\), \(\exists y\in F,\) tel que \(f^{-1}(\{y\})\) contient 2 éléments.

  • Nombre d'applications de X vers Y

    Le nombre d'applications de X vers Y, de cardinaux respectifs \(n,p\geq 1\) est \(p^n\)

  • Cardinal des parties d’un ensemble

    \(2^n\)

  • Définition d’un arrangement

    Un arrangement parmi $n$ objets est une suite de \(p\) objets distincts pris parmi les \(n\) objets donnés.

  • Nombre d’arrangements

    \(A^p_n = n(n-1)\dots(n-p+1) = \frac{n!}{(n-p)!}\)

  • Nombre de bijections entre 2 ensembles de même cardinal

    \(n!\)

  • Combinaison

    On appelle combinaison de \(n\) éléments de \(X\) pris \(p\) à \(p\) toute partie de \(X\) à \(p\) éléments. On le note \(C^p_n\). L'ordre n'a pas d'importance.

  • Nombre de combinaisons

    Le nombre de parties à \(p\) éléments de \(X\) est \(C^p_n = \frac{n!}{p!(n-p)!} = \frac{A^p_n}{p!}\).

  • Valeurs importantes des combinaisons

    \(C^0_n = 1\), \(C^n_n = 0\), \(C^1_n = n\)

  • Propriété de symétrie des combinaisons

    \(C^{n-p}_n = C^p_n\)

  • Triangle de Pascal des combinaisons

    \(C^p_n + C^{p+1}_n = C^{p+1}_{n+1}\)

  • Nombre de parties d'un ensemble

    \(\sum^n_{k=0} C^p_n = 2^n\)