$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Nombres de Catalan

  Considérons une expression de la forme a1Ta2T...Tan, où T désigne l'une des opérations + ou -. On souhaite placer des parenthèses dans cette expression pour savoir dans dans quel ordre effectuer les opérations. Par exemple, 1-(3+7)=-9 est différent de (1-3)+7=5. Il s'agit donc de placer des parenthèses autour des termes de sorte que :
  • on n'ait jamais plus de deux termes non parenthésés (pas de choix à faire!).
  • on ne mette jamais des parenthèses autour d'un seul terme (pas de parenthèses inutiles!).
  Le nombre de façons de bien parenthéser cette expression s'appelle nombre de Catalan d'ordre n, et nous le noterons Cn. Calculons ce nombre dans le cas où n est petit :
  • n=1 : une seule façon : a.
  • n=2 : une seule façon : aTb.
  • n=3 : 2 façons : (aTb)Tc ou aT(bTc).
  • n=4 : 5 façons : (aTb)T(bTc), aT( (bTc)Td ), aT(bT(CTd)), ((aTb)Tc)Td, (aT(bTc))Td.
Il est facile d'obtenir une relation de récurrence pour calculer les nombres de Catalan. Si l'on a un parenthésage de (n+1) termes, on regarde l'opération la plus externe : b1Tb2, où b1 et b2 sont eux-mêmes le résultat obtenu après parenthésage de p termes pour b1, et de n+1-p termes pour b2. Comme p peut être quelconque entre 1 et n, on obtient la relation de récurrence :
On peut résoudre cette équation de récurrence avec la théorie des séries entières (ou des séries génératrices). On trouve alors :
désigne le coefficient binomial, c'est à dite le nombre de combinaisons à p éléments parmi n.

  Les nombres de Catalan interviennent dans de nombreux problèmes de combinatoire. Par exemple, Euler les avait introduit pour calculer le nombre de façons qu'il y a de partager un polygone convexe à n côtés à l'aide de ses diagonales sans que celles-ci ne se coupent.
Consulter aussi...