Énumération des arbres binaires de taille n

Il y a 1 arbre binaire de taille 0.
Il y a 1 arbre binaire de taille 1.
Il y a 2 arbres binaires de taille 2.
Il y a 5 arbres binaires de taille 3.
Il y a 14 arbres binaires de taille 4.

Arbres binaires de taille 4

Les 14 arbres binaires de taille 4, peuvent être répartis en fonction de la taille des sous arbres.

Il y a un nœud racine et 3 autres nœuds à répartir à gauche ($t_g$) et à droite ($t_d$).

\[(1 + t_g + t_d = 4)\]

$(t_g=0, t_d=3)$

$(t_g=1, t_d=2)$

$(t_g=2, t_d=1)$

$(t_g=3, t_d=0)$

Exercice

Coder une fonction nb_arbres_binaires qui prend un entier n en paramètre et qui renvoie le nombre d'arbres binaires de taille n après avoir complété, si besoin, la liste des résultats mémorisés catalan_mem.

Contraintes

$0 \leqslant n < 256$
Fonction récursive interdite
Modules math et functools interdits
Code source limité à 2000 caractères

Un algorithme de calcul

Il existe plusieurs méthodes de calcul. Voici une méthode pédagogique pour calculer ce nombre en fonction de n, il s'agit des nombres de Catalan.

Si la taille $n$ vaut zéro,
- renvoyer $1$. Il y a un seul arbre à zéro nœud, un arbre vide.
Sinon,
- l'arbre possède une racine et deux sous-arbres. Les tailles possibles pour les sous-arbres sont :
  - $0$ à gauche et $n-1$ à droite
  - $1$ à gauche et $n-2$ à droite
  - $2$ à gauche et $n-3$ à droite
  - ...
  - $n-3$ à gauche et $2$ à droite
  - $n-2$ à gauche et $1$ à droite
  - $n-1$ à gauche et $0$ à droite
- renvoyer la somme du nombre d'arbres dans chaque cas.

Évaluations restantes : ∞/∞

.128013],59/f.78rnb _o=ylaepcwgu)*vd461`3kRImhétsP(S0+2Cè[-i:050D0u0P0t0#0s0Q0n0w0s0t0Q0Q0q010P0#0v010406050Q0z0M0M0t0k0r040T0p0s0z0`0p0l050f111315170 0v04051n1g1q0f1n0 0D0#0C0/0;0?0^0N0#0y0N0s1E0N0P0}050*0m0s0u1z0=0@011D1F1H1F0P1N1P1L0P0k1o0P0N1R1B010g0,0u0l0t0M0u010/1a0Q0v0t0l0^0W1L1|1~1,1T1/1P1=1@0}0a0n0R0k0p0v0p0Q0#1d0l0n0(1`0k0k0u0w2l1g230l1o0f1*2y1%1)1(1M0D250^1H0l1;2i1L1w1y0:1S2I0#2K0l0p2O1L0v2r1o2w2y2$101}2m2Q1-2V0k140s0}0n0G2v2*0~2)242,1T2.2:2=0W2^1~2`2w2H012 0t2;040n0I332x0 362}0^393b0n0E3f352*373l2=0d3p3h3r3j380p2/3a2=0F3w2{2+1A2~3B303c0i3G3i3J3k3L3D3c0j3P3y3R3A3C3m0e3X2|3Z3t040G0U3(3I2R3!3M0G2@1h2_3x3)3;3+0G323_343{3:2-3T3b0G3e413g3H3s460}0G3o4a2y2Z0u2y2O2B0D1)2G3z0w2W1^1o4n1p2!3H2%2_054t0(2#3Y3;0w0G0}030n0L0l2k0#3a0#0Q0t2l2n1Q0;0n1H0Q0P1Q0(0.0k0O110s0*0P0Q3/3s0}0w4V3a1~0o1@0M3p0n4c3z0p0}0q4 513Z0|040Z3p573;0M0#4f5c3Q3;590b3w43370J0}0(0g5i4H1-0x2=5u3|2-0g0}0l0m0o150m2r0Q0o0m2T0+5J5z441T590S5Q4?041f4i5d1-590A0$4=3z5x3c0n5-5V3z0Q0D0}015@5)3Z5;2=5-0n0X0p0M0v0s0Y4%0c0n2j0n0m0u0Q0p2T664Z4#4%0n0H4^0*0;0l4|0u0M0H5_3;5{5,5-0K1;0C6d1Q6l4`6o4}0Z0l0b0n0$4!1Q2V0M5I4(1Q0X4_6n2n002T1w0w6N6t1-6v5}0n5@013w6)5!1T5q040g3B565j2-0}0J6^5v1T0p5+2T6}5A2~0m0}0k1~0y0u5/580}5U5Z6_750}287c5k7e7l6`046D6n6p4~7g6~0^5$0c735R3k5D7A3753040V7E3z5f5h7v747x0}5%6-6)5}6/7C7q0o6|4i507h0^7G557!7V017L043.4i067T7U7$016;6?0k7J3*0}0#7|3;707~5Y2$7#7w387604780l7a7o5S7n7N7B386{8e7P047R7:7=7=7+0l4@7Y801-7G0V7)858s4@6U4{4}8l01595b8h5W7 8L3z5l8w6 0}0B8R7W7r8F6q8H8J8H8t047Z8B7@7G0!8V7,5g3,8.8,8.8%8N2(7@8Q8p8q8C7q8E6F8Z8O3Z7G0h8$0}0t0v0v1;0D8!8g8`878%0w8v947m8n7S5.7@6;2r0P0z0k842_867O8j906m8Y7u9h9A8#9m7p9x347+8|2$0 0f4E4l1r4z0f4x2z4p1g2C9!0t1O9T9W1x2`9W0)0+0-04.