Relation de récurrence pour les nombres de Catalan
Les nombres de Catalan satisfont la relation de récurrence suivante : $$C_0 = 1 \quad \text{et} \quad C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i} \quad \text{pour } n \geq 0$$
Formule explicite des nombres de Catalan
Pour tout entier naturel $n \geq 0$, le $n$-ième nombre de Catalan est donné par : $$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}$$
Théorème : Minoration du nombre chromatique par la taille de la plus grande clique
Soit $G = (V, E)$ un graphe contenant une clique d'ordre $m$ (c'est-à-dire un sous-graphe complet à $m$ sommets). Alors $\chi(G) \geq m$.
Théorème : Majoration du nombre chromatique par le degré maximal
Soit $G = (V, E)$ un graphe et $\Delta$ le degré maximum de ses sommets. Alors $\chi(G) \leq \Delta + 1$.
Formule de Legendre
Soit $n$ entier naturel et $p$ un nombre premier. Alors : $$v_p(n!)=\sum_{k\geq1} \left\lfloor \dfrac{n}{p^k} \right\rfloor. $$
Formule de Pascal
Pour tout entier naturel non nul $n$, pour tout entier naturel $k\leq n$ : $${n-1 \choose k-1}+{n-1 \choose k} = {n \choose k}.$$
Combinaison avec répétitions
Soient $n$ et $p$ deux entiers naturels, $n \geq 1$. Le nombre de combinaisons de $p$ éléments pris parmi $n$ avec répétition est : $$\Gamma_n^p={{n+p-1}\choose p}=\frac{(n+p-1)!}{p!(n-1)!}.$$
Nombre de parties d'un ensemble
Soit $E$ un ensemble fini de cardinal $n\in\mathbb{N}$. Le nombre de parties de $E$ est de $2^n$.