Il s'agit d'un simple memento, il faudra donc se référer au cours de mathématiques pour trouver les développements et précisions concernant les notions qui sont rappelées ici brièvement avec cer­tai­nes imprécisions et/ou approximations inévitables par soucis de concision.

Logique

Deux formules \(E_1\) et \(E_2\) qui ont toujours même valeur de vérité quelles que soient les valeurs logiques des variables propositionnelles qui les constituent sont dites logiquement équivalentes, ce que l'on note \(E_1\equiv E_2\). Le connecteur d'implication \(\Rightarrow\) est défini par \[P\Rightarrow Q\overset{\text{déf.}}{\equiv} \neg P\vee Q.\] On montre aisément que \(P\Rightarrow Q\equiv \neg Q\Rightarrow \neg P\), et la proposition \(\neg Q\Rightarrow \neg P\) est appelée contraposée de la proposition \(P\Rightarrow Q\). Le connecteur d'équivalence \(\Leftrightarrow\) est défini par \[P\Leftrightarrow Q\overset{\text{déf.}}{\equiv} (P\Rightarrow Q)\wedge (Q\Rightarrow P).\] On rappelle les lois de De Morgan : \begin{align*} \neg(P\vee Q)&\ \equiv\ \neg P\wedge\neg Q\\ \neg(P\wedge Q)&\ \equiv\ \neg P\vee\neg Q \end{align*}

Ensembles et prédicats

Un ensemble désigne informellement une collection d'objets. Deux symboles mathématiques sont spécifiques aux en­semb­les, le symbole d'égalité \(\def\R{\mathbf R}\def\N{\mathbf N}=\) et le symbole d'appartenance \(\in\). Si deux objets \(A\) et \(B\) sont égaux, i.e. \(A=B\) ils sont totalement interchangeables et l'un peut remplacer l'autre dans n'importe quelle expression. Si deux ensembles \(A\) et \(B\) sont égaux, cela signifie que tous les éléments de l'ensemble \(A\) sont des éléments de l'ensemble \(B\) — on dit que \(A\) est inclus dans \(B\), ce que l'on note \(A\subseteq B\) — et réciproquement, ce que l'on note cette fois \(B\subseteq A\).

Un prédicat est un énoncé bien formé contenant des variables tel qu'en substituant les variables par des valeurs choisies dans un ensemble — ce que l'on qualifie en informatique d'ins­tan­ciation des variables — le nouvel énoncé devient une proposition. Par exemple \(x\geq \pi\) est un prédicat à une variable \(x\) de l'ensemble des nombres réels \(\R\). En le notant \(P(x)\), on a par exemple l'assertion (proposition vraie) \(P(4)\). L'énoncé \(n=2k\) est un prédicat \(P(n,k)\) à deux variables \(n\) et \(k\) de l'ensemble des entiers naturels \(\N\).

Relations binaires

On appelle relation binaire sur \(E\) tout prédicat \(R(x,y)\) à deux variables dans \(E\). On note généralement une relation binaire de manière infixe \(x\ R\ y\), plus en adéquation avec la langue naturelle : \(x\) est en relation avec \(y\) pour la relation \(R\). Les relations binaires peuvent posséder des propriétés re­mar­qua­bles :

1. Réflexivité : \(\forall x\in E,\ x\ R\ x\) ;
2. Symétrie : \(\forall x,y\in E,\ x\ R\ y\Leftrightarrow y\ R\ x\) ;
3. Antisymétrie : \(\forall x,y\in E,\ (x\ R\ y\ \text{et}\ y\ R\ x)\Rightarrow y= x\) ;
4. Transitivité : \(\forall x,y,z\in E,\ (x\ R\ y\ \text{et}\ y\ R\ z)\Rightarrow x\ R\ z\).

Une relation binaire qui est à la fois réflexive, symétrique et transitive est appelée relation d'équi­valen­ce. Si \(R\) est une relation d'équivalence sur un ensemble \(E\) et \(x\in E\), le sous-ensemble de \(E\) constitué par tous les éléments en relation avec \(x\) est appelé classe d'équivalence de \(x\).

Une relation binaire qui est à la fois réflexive, antisymétrique et transitive est appelée relation d'ordre. Si \(R\) est une relation d'ordre sur un ensemble \(E\), on dit que deux éléments \(x\) et \(y\) sont comparables si \(x\ R\ y\) ou \(y\ R\ x\). Si tous les éléments sont comparables deux-à-deux, il s'agit d'un ordre total sinon d'un ordre partiel. Si \(R\) est une relation d'ordre sur un ensemble \(E\), la relation \(R'\) définie sur \(E\) par \(x\ R\ y\) et \(x\not=y\) est appelée ordre strict associé à \(R\), ce n'est pas une relation d'ordre.

L'ordre naturel \(\leq\) sur l'ensemble \({\mathbf N}\) des entiers naturels est une relation d'ordre total alors que l'inclusion \(\subseteq\) sur l'ensemble \({\mathcal P}(E)\) des parties d'un ensemble \(E\) est une relation d'ordre partiel, tout comme la relation de divisibilité \(|\) sur l'ensemble des entiers naturels \({\mathbf N}\). Le couple \((E,\preceq)\) constitué d'un ensemble \(E\) et d'une relation d'ordre \(\preceq\) sur \(E\) est appelé ensemble ordonné. Par analogie avec l'ordre naturel, si \(a\preceq b\), on dit que \(a\) est plus petit que \(b\). De la même manière, si \(A\subset E\) et s'il existe un élément \(m\in A\) tel que \(\forall x\in A\), \(m\preceq x\) (respectivement \(\forall x\in A\), \(x\preceq m\)) il est nécessairement unique et on dira que \(m\) est le plus petit élément de \(A\) ou minimum de \(A\) que l'on note \(\min A\) (respectivement plus grand élément de \(A\) ou maximum de \(A\) que l'on note \(\max A\)). Dans un ensemble partiellement ordonné, on appelle élément minimal (resp. élément maximal) un élément \(m\in E\) (resp. \(M\)) plus petit (resp. plus grand) que tous les éléments auxquels il est com­pa­ra­ble.

Correspondances, fonctions, applications

Soient \(E\) et \(F\) deux ensembles. Une cor­res­pon­dan­ce de \(E\) dans \(F\) est un triplet \(c:=(E,F,\Gamma)\) où \(E\) est l'ensemble de départ, \(F\) l'ensemble d'arrivée et \(\Gamma\subseteq E\times F\) le graphe de \(c\). Si de plus le graphe \(\Gamma\) ne contient jamais deux couples distincts \((x,a)\) et \((x,b)\) il s'agit d'une correspondance fonctionnelle ou encore d'une fonction. On note alors de manière condensée \(f:E\rightarrow F\) pour spécifier les ensembles de départ et d'arrivée, le graphe étant défini explicitement pas l'ensemble des couples \((x,y)\) ou par un prédicat à deux variables \(P(x,y)\) (supposé être satisfait pour au plus un \(y\) par \(x\) donné). Ainsi, si \((x,y)\in \Gamma\), on note \(y=f(x)\) et \(y\) est l'image de \(x\) par \(f\) et \(x\) est un antécédent de \(y\) par \(f\). Le domaine de définition d'une fonction \(f:E\rightarrow F\) est le sous-ensemble de \(E\) des éléments qui ad­met­tent une image, on le note \({\mathcal D}_f\). Si \({\mathcal D}_f=E\), on dit que \(f\) est une application.

On appelle injection toute application \(f:E\rightarrow F\) telle que deux éléments distincts de \(E\) ont des ima­ges distinctes, ce que l'on exprime souvent par la contraposée: \[\forall (x,y)\in E\times E,\ \ f(x)=f(y)\Rightarrow x=y.\] On appelle surjection toute application \(f:E\rightarrow F\) telle que tout élément de l'ensemble d'arrivée \(F\) admet au moins un antécédent: \[\forall y\in F,\ \exists x\in E,\quad f(x)=y.\] On appelle bijection toute application \(f:E\rightarrow F\) qui est à la fois une injection et une surjection, au­tre­ment dit telle que tout \(y\in F\) admet un unique antécédent \(x\).

Permutations

Soit \(n\) un entier naturel. On appelle permutation toute bijection \(\sigma:[1,n]\rightarrow[1,n]\). On note gé­né­ra­le­ment une per­mu­ta­tion \(\sigma\) sous la forme d'une matrice \(2\times n\) : \[\sigma=\begin{pmatrix} 1&2&3&\cdots&n\\ \sigma(1)&\sigma(2)&\sigma(3)&\cdots&\sigma(n) \end{pmatrix} \] L'ensemble de toutes les permutations des entiers de l'intervalle \([1,n]\) est noté \({\mathfrak S}_n\) et constitue un groupe (non commutatif dès que \(n\geq 3\)) quand il est muni de la loi de composition des applications, c'est le groupe symétrique. On appelle inversion d'une permutation \(\sigma\), tout couple \((i,j)\) tel que \(i < j\ \text{et}\ \sigma(i) > \sigma(j)\). Une permutation \(\sigma\) qui laisse tous les termes fixes, sauf deux d'entre eux s'appelle une trans­po­si­tion. S'il existe \(k\) entiers \(x_0,x_1,\ldots,x_{k-1}\in[1,n]^k\) tels que \[\forall i\in[0,k-1],\quad \sigma(x_i)=x_{i+1\pmod k}\] et \(\sigma(x)=x\) pour toutes les autres valeurs \(x\) de l'intervalle \([1,n]\), la permutation \(\sigma\) est appelée k-cycle, ou cycle de longueur \(k\geq 2\) que l'on note plus simplement \(\sigma=(x_0,x_1,\ldots,x_{k-1})\). Un \(2\)-cycle est donc une transposition que l'on note également \(\tau_{i,j}\) si elle échange les entiers \(i\) et \(j\), i.e. \(\tau(i) = j\) et \(\tau(j)=i\). On montre que toute permutation se décompose en produits de cycles (le produit désignant la com­po­si­tion des applications). La permutation suivante se décompose en deux cycles, un \(4\)-cycle et un \(3\)-cycle : \[\sigma=\begin{pmatrix} \color{yellow}1&2&\color{yellow}3&\color{yellow}4&\color{#AAF}5&\color{#AAF}6&7&\color{yellow}8&\color{#AAF}9\\ \color{yellow}3&2&\color{yellow}8&\color{yellow}1&\color{#AAF}6&\color{#AAF}9&7&\color{yellow}4&\color{#AAF}5 \end{pmatrix}={\color{yellow}(1,3,8,4)}{\color{#AAF}(5,6,9)} \]

Cardinalité, suites

Deux ensembles \(E\) et \(F\) sont dits équipotents, Équipotent signifie mê­me puis­san­ce ce que l'on note \(E\approx F\), s'il existe une bijection \(f:E\rightarrow F\). Si \(a\) et \(b\) sont deux entiers naturels, on définit l'intervalle \([a,b]:=\{n\in{\mathbf N}\mid a\leq n\leq b\}\). Un ensemble \(E\) est dit fini s'il existe un entier \(n\), appelé cardinal de \(E\) tel que \(E\approx[1,n]\), on le note \(\#E\) ou \(|E|\). Dans le cas contraire, \(E\) est dit infini. Un ensemble infini équipotent à \(\mathbf N\) est dit dénombrable. Un ensemble fini ou dénombrable est dit au plus dénombrable.

Soit \(E\) un ensemble. Une application \(u:{\mathbf N}\rightarrow E\) est appelée suite d'éléments de \(E\), on la note \((u_n)_{n\in {\mathbf N}}\) ou par commodité \((u_n)\) et la notation indicée \(u_n\) est utilisée au lieu de \(u(n)\), c'est le terme général de rang \(n\) de la suite. Si \(u:I\rightarrow E\) où \(I\) est un ensemble fini totalement ordonné de cardinal \(n\) (souvent \([1,n]\) ou \([0,n-1]\)), on parle de séquence ou de suite finie de longueur \(n\in{\mathbf N}\) indexée par \(I\) ou d'ensemble d'in­de­xa­tion \(I\).

Soient \(I\) et \(E\) deux ensembles quelconques. Une famille d'ensembles indexée par \(I\) est une application \(A\) de \(I\) dans \({\mathcal P}(E)\). On la note \((A_i)_{i\in I}\) avec \(A_i:=A(i)\).

Une partition d'un ensemble \(E\) est une famille \((E_i)_{i\in I}\) de parties de \(E\) telle que

1. \(\forall i\in I,\quad E_i\not=\varnothing\),
2. \(\forall (i,j)\in I\times I,\ i\not=j\Rightarrow E_i\cap E_j=\varnothing\),
3. \(\displaystyle\bigcup_{i\in I}E_i=E\).

Formulaire de combinatoire

Des extraits de ce paragraphe sont disponibles en mémo pdf. Dans toute la suite, \(E\) et \(F\) désignent deux ensembles finis et totalement ordonnés quand cette propriété est nécessaire avec \(n=\#E\) et \(p=\#F\). On rappelle que l'application factorielle est l'appli­cation de \(\mathbf N\) dans \(\mathbf N\) définie par \begin{equation} n!:=n(n-1)(n-2)\ldots 2\times 1\quad\text{et par convention}\quad 0!:=1. \end{equation}

On dénombre le

• Nombre de couples de \(E\times F\) : \[\#(E\times F)=n.p\]
• Nombre d'applications de \(E\rightarrow F\) : \[\#(F^E)=p^n\]
• Nombre de parties de \(E\) : \[\#{\mathcal P}(E)=2^n\]
• Nombre de bijections de \(E\rightarrow E\) (ou de permutations de \({\mathfrak S}_n\))  : \[\#{\frak S}_n=n!:=n(n-1)(n-2)\ldots1\]
• Nombre total d'inversions pour le groupe \({\frak S}_n\) : \[n!\ \frac{n(n-1)}{4}\]
• Nombre d'injections de \(E\rightarrow F\) (\(n\leq p\)) : \[A_p^n:=\frac{p!}{(p-n)!}\]
• Nombre de parties de \(E\) de cardinal \(p\) : \[C_n^p=\binom{n}{p}:=\frac{n!}{(n-p)!p!}\]
• Nombre de rangements de \(n\) objets dans \(p\) boites numérotées : \[R_n^p:=\frac{(p+n-1)!}{(p-1)!}\]
• Nombre d'applications croissantes de \(E\rightarrow F\) : \[\frac{R_n^p}{n!}\]
• Nombre de partitions de \(E\) (nombres de Bell) : \[B_{n+1}:=\sum_{k=0}^n\binom{n}{k}B_k,\quad\text{avec \(B_0=1\)}.\]
• Nombre de partitions de \(E\) en \(p\) classes (nombres de Stirling) : \[S_{n+1}^p:=S_{n}^{p-1}+pS_{n}^p=\sum_{k=0}^n\binom{n}{k}S_k^{p-1},\quad\text{avec}\ S_n^1=S_n^n=1\]
• Nombre de surjections de \(E\) dans \(F\) : \[p!S_n^p\]

Compléments

• Formule de sommation : soit \((E_i)_{i\in I}\) une partition d'un ensemble fini \(E\), \begin{equation}\label{eq:sommation} \#E=\sum_{i\in I}\#E_i. \end{equation}
• Séries arithmétiques et séries géométriques : soit \(S_n:=\sum_{i=0}^na_i\) la somme partielle de la série arithmétique (resp. géométrique) de terme général \(a_n\) et de raison \(r\not=1\). \begin{equation*} S_n=(n+1)(a_0+\frac{nr}{2})\qquad(\text{resp.}\ S_n=a_0\left(\frac{r^{n+1}-1}{r-1}\right)). \end{equation*}
• Triangle de Pascal : soient \(p\) et \(n\) deux entiers, \(0\leq p\leq n\), \begin{equation}\label{eq:pascal} \binom{n}{p}=\binom{n}{n-p}=\binom{n-1}{p}+\binom{n-1}{p-1}\quad\text{et}\quad \sum_{p=0}^n\binom{n}{p}=2^n. \end{equation}
• Formule de Stirling : soit \(n\) un entier naturel : \[\lim_{n\rightarrow+\infty}\frac{n!}{\sqrt{2\pi n}(n/e)^n}=1.\]
• Binôme de Newton : soient \(a, b\) deux éléments d'un anneau commutatif, \[(a+b)^n=\sum_{p=0}^{n}\binom{n}{p}a^pb^{n-p}.\]
• Lemme des tiroirs : si on range \(n\) objets dans \(p\) tiroirs, alors un des tiroirs contient au moins \([n/p]\) objets où \([x]\) est la partie entière du réel \(x\).
• Lemme des bergers : soient \(E\) et \(F\) finis et \(f:E\rightarrow F\) une surjection telle que tout élément de \(F\) admet exactement \(k\) antécédents, alors \(\#E=k\#F\).
• Quelques résultats utiles : soient \(q\not=1\) et \(n\) deux entiers: \begin{align*} \sum_{k=0}^nkq^k &= \frac{q}{(q-1)^2}[q^{n}(n(q-1)-1)+1] \\ \sum_{p=0}^np\binom{n}{p} &= n2^{n-1}\\ \sum_{k=0}^nk^2 &= \frac{n(n+1)(2n+1)}{6}\\ \prod_{k=1}^n(2k) &=2^n n!\\ \prod_{k=1}^n(2k-1) &=\frac{(2n)!}{2^n n!} \end{align*}

Exercices