\documentclass{article}
\usepackage{amssymb, amsmath, geometry, multicol, stmaryrd, cancel}
\usepackage[table, svgnames, dvipsnames]{xcolor}
\usepackage{makecell, cellspace, caption}
\usepackage[europeanresistors]{circuitikz}
\usepackage{empheq}
\usepackage[a]{esvect} % voir la doc pour les différents styles
\let\overrightarrow\vv

\usetikzlibrary{arrows}

\newcommand{\parspace}{\vspace{0.1cm}}
\renewcommand{\arraystretch}{1.2}
\newcommand{\Sn}{\mathrm{S}_n}
\linespread{1.25}
\geometry{tmargin=.7in, bmargin=.7in, lmargin=.7in, rmargin = .7in}

\begin{document}
\setlength{\parindent}{0mm}

\title{Dénombrement}
\author{Aubin SIONVILLE}
\date{MPI Clemenceau - 2021-2023}
\maketitle

\centering

\section*{Introduction}

\subsection*{Existence}

\[\boxed{\forall X \subsetneq \llbracket 1 n \rrbracket, \text{ non vide}, \exists p \in \mathbb{N},
    \begin{cases}
        0 < p < n \\
        \exists f \text{ une bijection de } X \text{ dans } \llbracket 1 p \rrbracket
    \end{cases}}\]

\vspace*{0.3cm}

\begin{multicols}{2}
    \subsection*{Injectivité}
    \[\boxed{\begin{array}{c}
        \text{Soit } (n,p) \in \mathbb{N^*}^2, f : \llbracket 1 n \rrbracket \to \llbracket 1 p \rrbracket \text{ injective}\\
        \text{Alors } p \leq n
    \end{array}}\]
    
    \subsection*{Surjectivité}
    \[\boxed{\begin{array}{c}
        \text{Soit } (n,p) \in \mathbb{N^*}^2, f : \llbracket 1 n \rrbracket \to \llbracket 1 p \rrbracket \text{ surjective}\\
        \text{Alors } p \geq n
    \end{array}}\]
\end{multicols}

\subsection*{Bijectivité}
\[\boxed{\begin{array}{c}
    \text{Soit } (n,p) \in \mathbb{N^*}^2, f : \llbracket 1 n \rrbracket \to \llbracket 1 p \rrbracket \text{ bijective}\\
    \text{Alors } p = n
\end{array}}\]

\vspace*{0.5cm}

\section*{Ensembles finis}

\subsection*{Relations entre les cardinaux}
\[\boxed{\begin{array}{c}
    \text{Soit } E \text{ et } F \text{ deux ensembles finis et } f : E \to F, \text{ alors}\\
    f \text{ bijective } \implies \mathrm{Card}E = \mathrm{Card}F\\
    f \text{ injective } \implies \mathrm{Card}E \leq \mathrm{Card}F\\
    f \text{ surjective } \implies \mathrm{Card}E \geq \mathrm{Card}F
\end{array}}\]

\vspace*{0.3cm}

\subsection*{Ensembles de même cardinal}
\[\boxed{\begin{array}{c}
    \text{Soit } E \text{ et } F \text{ deux ensembles finis de même cardinal et } f : E \to F\\
    Alors f \text{ est injective } \iff f \text{ est bijective } \iff f \text{ est surjective}
\end{array}}\]

\newpage

\begin{multicols}{2}
    \subsection*{Cardinal de l'union}
    \[\boxed{\begin{array}{c}
        \text{Soit } E \text{ un ensemble fini}\\
        \text{Soit } A \text{ et } B \text{ deux sous-ensembles de } E\\
        \text{Alors } \mathrm{Card}(A \cup B) = \mathrm{Card}A + \mathrm{Card}B - \mathrm{Card}(A \cap B)
    \end{array}}\]
    
    \subsection*{Principe des bergers}
    \[\boxed{\begin{array}{c}
        \text{Soit } f : E \to F \text{ où } F \text{ est fini }\\
        \text{Soit } p \text{ le nombre d'antécédents de tous les éléments de } F\\
        \text{Alors } \mathrm{Card}E = p\mathrm{Card}F
    \end{array}}\]
\end{multicols}

\vspace*{0.3cm}

\begin{multicols}{2}
    \subsection*{Cardinal et partition}
    \[\boxed{\begin{array}{c}
        \text{Soit } (A_i)_{i \in I} \text{ une partition d'un ensemble fini } E\\
        \text{Alors } \mathrm{Card}E = \sum_{i \in I} \mathrm{Card}A_i
    \end{array}}\]

    \subsection*{Cardinal du produit cartésien}
    \[\boxed{\begin{array}{c}
        \text{Soit } E \text{ et } F \text{ deux ensembles finis}\\
        \text{Alors } \mathrm{Card}(E \times F) = \mathrm{Card}E \mathrm{Card}F
    \end{array}}\]
\end{multicols}

\vspace*{0.3cm}

\subsection*{Nombre de parties}
\[\boxed{\begin{array}{c}
    \text{Soit } E \text{ un ensemble fini}\\
    \text{Alors } \mathrm{Card}P(E) = 2^{\mathrm{Card}E}
\end{array}}\]

\vspace*{0.5cm}

\section*{Dénombrement}

\begin{multicols}{2}
    \subsection*{$k$-listes}
    \[\boxed{\begin{array}{c}
        \text{Une } k \text{-liste de } E \text{ est un élement de } E^k\\
        \displaystyle\text{Il y a } n^k \, k \text{-listes de } E
    \end{array}}\]

    \subsection*{$k$-arrangements}
    \[\boxed{\begin{array}{c}
        \text{Un } k \text{-arrangement de } E \text{ est une } k \text{-liste de } E \text{ sans doublons}\\
        \displaystyle\text{Il y a } \frac{n!}{(n-k)!} \, k \text{-arrangements de } E
    \end{array}}\]
\end{multicols}

\vspace*{0.3cm}

\begin{multicols}{2}
    \subsection*{Permutations}
    \[\boxed{\begin{array}{c}
        \text{Une permutation de } E \text{ est un } n \text{-arrangement de } E\\
        \text{Il y a } n! \text{ permutations de } E
    \end{array}}\]

    \subsection*{Combinaisons}
    \[\boxed{\begin{array}{c}
        \text{Une } k \text{-combinaison de } E \text{ est un } k \text{-arrangement de } E\\
        \displaystyle\text{Il y a } \binom{n}{k} = \frac{n!}{p!(n-k)!} \, k\text{ combinaisons de } E
    \end{array}}\]
\end{multicols}

\vspace*{0.3cm}

\begin{multicols}{2}
    \subsection*{Formule de Pascal}
    \[\boxed{\begin{array}{c}
        \forall 0 \leq k \leq n,\\
        \displaystyle\binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}
    \end{array}}\]

    \subsection*{Formule de Newton}
    \[\boxed{\begin{array}{c}
        \forall 0 \leq k \leq n,\\
        \displaystyle\binom{n}{k} = \binom{n}{n-k}
    \end{array}}\]
\end{multicols}

\vspace*{0.3cm}

\subsection*{Binôme de Newton}
\[\boxed{\forall (a,b) \in \mathbb{C}^2, \forall n \in \mathbb{N}, (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}}\]

\end{document} 