Énumération des expressions bien parenthésées⚓︎

Expression bien parenthésée

Une expression bien parenthésée est une chaine de caractères composée d'autant de ( que de ) et où chaque parenthèse ouvrante est placée avant la fermante qui lui correspond.

()(()) et ((()))() sont bien parenthésées
)()( et ())(() ne sont pas bien parenthésées.

Pour \(2\) paires de parenthèses, il y a \(2\) expressions bien parenthésées.
- ()()
- (())
Pour \(3\) paires de parenthèses, il y a \(5\) expressions bien parenthésées.
- ()()()
- (())()
- ()(())
- (()())
- ((()))

On admettra que le nombres d'expressions bien parenthésées contenant \(n\) paires de parenthèses est le nombre de Catalan \(C_n\) que l'on peut calculer, par exemple, avec la formule suivante :

\[C_n = \begin{cases} 1 & \quad \text{ si } n = 0\\ C_{n-1}×\dfrac{2(2n - 1)}{n + 1} & \quad \text{ si } n > 0\\ \end{cases}\]

Objectif : Écrire une fonction telle que catalan(n) renvoie le nombre de Catalan d'indice n.

On utilisera la liste catalan_mem pour conserver en mémoire les résultats, ce qui permet un accès ultérieur sans calcul.
On utilisera la variable catalan_i pour désigner \(C_i\) et catalan_im1 pour désigner \(C_{i-1}\).
On sera capable de justifier à l'oral le commentaire placé dans le code.
On complètera le code :

🐍 Script Python

catalan_mem = [1]

def catalan(n):
    i = len(catalan_mem)
    while n >= i:
        catalan_im1 = ...
        catalan_i = ... // (i + 1)
        catalan_mem.append(...)
        i = ...
    # ici n < len(catalan_mem)
    return ...

Exemples

🐍 Console Python

>>> catalan(2)
2
>>> catalan(3)
5
>>> catalan(5)
42

###

5/5

catalanpy-undmem = [1]bksl-nlbksl-nldef catalan(n):bksl-nl i = len(catalanpy-undmem)bksl-nl while n >= i:bksl-nl catalanpy-undim1 = ...bksl-nl catalanpy-undi = ... // (i + 1)bksl-nl catalanpy-undmem.append(...)bksl-nl i = ...bksl-nl # ici n < len(catalanpy-undmem)bksl-nl return ...bksl-nlbksl-nl# testsbksl-nlassert catalan(2) == 2bksl-nlassert catalan(3) == 5bksl-nlassert catalan(5) == 42bksl-nlbksl-nlbksl-nlNone