Ensemble fini E∃n∈N,[[1;n]] est en bij avec E n est unique !
\( \textbf{Bonux cardinal} \\ \text{$E$ fini, $A \subset E$} \\ \text{card } A \leqslant \text{card } E \text{ avec égalité ssi $A = E$} \)
\( \textbf{Caractérisation des ens. infinis} \\ E \text{ est infini } \\ \Leftrightarrow \text{ E en bij avec une de ses parties }\textit{strictes} \)
\( \varphi : n \longmapsto 2n \text{ est une bij entre} \\ \text{$\mathbb N$ et $2\mathbb N$ donc } \mathbb N \text{ est infini} \)
\( \textbf{Techniques de dénombrement} \\ \begin{array}{l|l} \ \textit{Principe du "ou bien"} & \text{card }(E\sqcup F) = \text{card } E + \text{card } F \\ \textit{Lemme des bergers} & \text{on "départitionne ! (on compte plusieurs fois, et on divise)} \\ \textit{Formule de Poincaré} & \text{card } E \cup F = \text{card } E + \text{card } F - \text{card }(E \cap F) \\ \textit{$\rightarrow$ Formule du Crible} & \text{généralisation de Poincaré} \\ \textit{Passage au contraire} & \text{card } (E \text{ \\ } A) = \text{card } E - \text{card } A \\ \textit{Principe du et} & \text{Avec $p$ étapes à $n_1, \dots, n_p$ possibilités, on a $n_1\times\dots\times n_p$ possibilités} \\ \textit{Bijecter} & \text{en bijectant sur des ens. finis, $\large \text{ç}$a peut faciliter} \\ \textit{Principe des tiroirs} & \text{pour mettre $c > t$ chaussettes dans $t$ tiroirs, il faut qu'un tiroir ait 2 chaussettes } \ \end{array} \)
\( \textbf{Formule du Crible} \\ \text{card }(E_1 \cup \dots \cup E_p) = \\ \sum_{k = 1}^p (-1)^{k+1} \sum_{1 \leqslant i_1 \leqslant \dots \leqslant i_k \leqslant p} \text{card }(E_{i_1} \cap \dots \cap E_{i_k}) \)
\( \textbf{Choix successifs (l'ordre compte)} \\ \begin{array}{r|c|l} \ \textit{$p$-liste ($p$-uplet)} & \text{Choix successifs avec éventuelles répétitions} & \text{$n^p$ $p$-listes dans $E$} \\ \textit{$p$-liste sans rep. ($p$-arrangement)} & \text{Choix successifs sans répétitions} & n(n-1)\dots(n - p + 1) \text{ $p$-arrangements dans $E$} \\ \textit{permutations} & \text{Ordonner les éléments de $E$} & n! \text{ permutations dans $E$} \ \end{array} \)
\( \textbf{Choix simultanés (l'ordre ne compte pas)} \\ \begin{array}{r|c|l} \ \textit{$p$-combinaisons $\in \mathscr P_p(E)$} & \text{Choix simultanés sans répétitions} & \binom{n}{p} \text{ $p$-combinaisons dans $E$} \ \end{array} \)
\( \textbf{Coefficients binomiaux} \\ \binom{n}{p} = \frac{\text{« $p$ qui descendent depuis $n$ »}}{\text{« $p$ qui montent depuis $1$ »}} \)
\( \begin{array}{rl} \ \textit{Formule de symétrie} & \binom{n}{p} = \binom{n}{n - p} \\ \textit{Formule du pion, $p \neq 0$} & \binom{n}{p} = \frac{n}{p}\binom{n - 1}{p - 1} \\ \textit{Formule de Pascal, $n \neq 0$} & \binom{n}{p} + \binom{n}{p + 1} = \binom{n + 1}{p + 1} \ \end{array} \)
\( \text{Ensemble des combinaisons} \\ \mathscr P(E) = \mathscr P_0(E) \sqcup \dots \sqcup \mathscr P_n(E) \quad \text{donc} \\ \text{card }\mathscr P(E) = \sum \binom{n}{p} = 2^n \)
\( \textbf{Jections et cardinal} \\ \text{Avec $F$ fini, $\exists$ inj de $E$ dans $F$ $\Leftrightarrow$ card $E \leqslant$ card $F$} \\ \text{Avec $E$ fini, $\exists$ surj de $E$ sur $F \Leftrightarrow$ card $E \geqslant$ card $F$ } \\ \text{Avec $E \textbf{ ou } F$ fini, $E$ bij $F \Leftrightarrow E \textbf{ et } F$ sont finis et card $E = $ card $F$ } \\ \quad \\ \text{Pour tout $f$, card $f(E) \leqslant$ card $E$, avec égalité ssi $f$ est injective} \\ \quad \\ \text{! À même cardinal $\textbf{fini}$, inj $\Leftrightarrow$ bij $\Leftrightarrow$ surj ! ($\text{Bonux}^{TM}$)} \)
\( \text{D'où la technique de bijecter pour mieux compter} \)
\( \textbf{Principe des tiroirs} \\ \text{(ii) dit que si $F$ est plus petit que $E$, il ne peut y avoir injectivité.} \\ \text{Donc si $c > t$, il y a forcément deux objets dans le même tiroir} \)
très intéressant !
\( \textbf{Dénombrement d'applications entre ens finis} \\ \begin{array}{ll} \ \textit{Nombre d'app.} & \text{card } F^E = (\text{card } F)^{\text{card } E} \\ \textit{Nombre de bij} & n! \\ \textit{Nombre d'inj} & n(n-1)\dots(n - p + 1) \quad \scriptsize (\text{avec $n = \text{card } E$ et $p = \text{card } F$}) \\ \textit{Nombre de surj} & \text{Compliqu$\large \text{é}$ } \quad (\scriptsize S_n^p = \sum_{k = 0}^n (-1)^k\binom{p}{k}(p - k)^n\normalsize) \ \end{array} \)
\( \textbf{Th$\large\textbf é$or$\large\textbf è$me de $\large \color{beige}{\textbf{Cantor-Bernstein}}$} \\ \begin{cases} E \text{ est subpotent $\large\text à$ } F \\ F \text{ est subpotent $\large\text à$ } E \end{cases} \Rightarrow E \text { et } F \text{ sont $\large\text é$quipotents} \)
\( \textbf{Subpotence} \\ \text{$E$ sub $F$ lorsqu'il ex. une inj. de $E$ dans $F$} \\ \text{(i.e une surj. de $F$ sur $E$ si $E \neq \varnothing$)} \)
\( \textbf{$\large\textbf É$quipotence} \\ \text{$E$ et $F$ sont équipotents lorsqu'ils sont en bijection} \)
\( \text{Tout ensemble $E$ est strictement subpotent $\large\text à$ $\mathscr P(E)$} \)
Démonstration la plus difficile de l'année
\( \textbf{D$\large\textbf é$nombrabilit$\large\textbf é$} \\ \text{$E$ est d$\large\text é$nombrable lorsqu'il est subpotent $\large\text à$ $\mathbb N$} \)
\( \begin{array}{rl} \text{(i)} & \text{Si $F$ s'injecte dans $E$ dénombrable, alors $F$ est dénombrable} \\ \text{(ii)} & \text{Si $E$ et $F$ sont dénombrables, alors $E\times F$ l'est} \\ \text{(iii)} & \text{La réunion $\textit{dénombrable}$ d'ensembles dénombrables est dénombrable} \end{array} \)