É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.

Exemples

🐍 Console Python

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

Code à compléter :

###

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-nlcatalanpy-undmem = [1]bksl-nlbksl-nldef catalan(n):bksl-nl i = len(catalanpy-undmem)bksl-nl while n >= i:bksl-nl catalanpy-undim1 = catalanpy-undmem[i - 1]bksl-nl catalanpy-undi = catalanpy-undim1 py-str 2 py-str (2py-stri - 1) // (i + 1)bksl-nl catalanpy-undmem.append(catalanpy-undi)bksl-nl i += 1bksl-nl # ici n < len(catalanpy-undmem)bksl-nl return catalanpy-undmem[n]bksl-nlbksl-nlbksl-nl# testsbksl-nlassert catalan(2) == 2bksl-nlassert catalan(3) == 5bksl-nlassert catalan(5) == 42bksl-nlbksl-nlbksl-nl

Pour un appel de catalan(n) deux cas peuvent se produire.

n est plus petit que la longueur de la liste, alors le résultat est déjà stocké, il suffit de renvoyer catalan_mem[n].
n est supérieur ou égal à la longueur de la liste. On va alors faire grandir cette liste en utilisant la formule de récurrence, tant que nécessaire. On se retrouve alors dans le cas 1.

Preuve de la formule⚓︎

\[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}\]

Nous montrons ici une partie seulement de la preuve. La suite sera dans un autre exercice.

Nous partirons du fait (admis) que \(C_n = \dfrac{(2n)!}{(n+1)!n!}\) pour \(n\geqslant 0\).

Pour \(n = 0\), on a bien \(C_0 = \dfrac{0!}{1!0!} = \dfrac11=1\)
Pour \(n>0\), on a \(C_{n-1} = \dfrac{(2n-2)!}{(n-1)!n!}\), de sorte que
- \(C_{n-1} × \dfrac{(2n)×(2n-1)}{n(n+1)} = \dfrac{(2n)!}{(n+1)!n!} = C_n\)
- \(C_{n-1} × \dfrac{2×(2n-1)}{n+1} = C_n\)

Pour la formule : \(C_n = \dfrac{(2n)!}{(n+1)!n!}\) pour \(n\geqslant 0\).

Un autre exercice sera consacré à cela.

Variante sans `while`⚓︎

🐍 Script Python

catalan_mem = [1]

def catalan(n):
    for i in range(len(catalan_mem), n):
        catalan_im1 = catalan_mem[i - 1]
        catalan_i = catalan_im1 * 2 * (2*i - 1) // (i + 1)
        catalan_mem.append(catalan_i)
    # ici n < len(catalan_mem)
    return catalan_mem[n]

Culture⚓︎

Eugène Charles Catalan, né le 30 mai 1814 à Bruges et mort le 14 février 1894 à Liège, est un mathématicien franco-belge, spécialiste de la théorie des nombres.

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

Preuve de la formule⚓︎

Variante sans while⚓︎

Culture⚓︎

Variante sans `while`⚓︎