Énumération des arbres unaires-binaires à n+1 nœuds

Aucune connaissance sur les arbres n'est nécessaire !

Arbre binaire - rappel inutile

On rappelle la caractéristique d'un arbre binaire :

Soit c'est un arbre vide.
Soit c'est un arbre qui a exactement deux sous-arbres (un à gauche, un à droite) qui sont des arbres binaires.

Il est inutile d'utiliser ici cette propriété, nous allons définir une nouvelle classe d'arbres qui est différente.

Arbre unaire-binaire

On définit un arbre unaire-binaire comme étant :

Soit un arbre vide.
Soit un arbre ayant un ou deux sous-arbres qui sont alors des arbres unaires-binaires.
- Si le sous-arbre est unique,
  - il n'est ni à droite, ni à gauche, il est au centre.
  - Il peut être vide.
- Si les sous-arbres sont deux,
  - il y en a un à gauche, un autre à droite.
  - Ils sont alors non vides.

Un arbre vide n'a pas de nœud, sinon, un arbre possède un nœud racine et ceux de ses sous-arbres.

Un arbre unaire-binaire à $7+1$ nœuds.

Dans tout cet exercice, on parlera d'arbres à $n+1$ nœuds, comme ci-dessus à $7+1$ nœuds. En effet, on pourra plus facilement dire qu'il y a la racine et $n$ nœuds à se répartir soit au centre, soit à gauche et à droite.

Exercice

Coder une fonction motzkin qui prend un entier positif en paramètre et qui renvoie le nombre d'arbres unaires-binaires à $n+1$ nœuds.

Cette fonction est nommée ainsi d'après le mathématicien Théodore Motzkin (1908-1970).

Contraintes

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

Les arbres unaires-binaires à $3+1$ nœuds

Il y en a 4 :

Les arbres unaires-binaires à $4+1$ nœuds

Il y en a 9 :

Les 21 arbres unaires-binaires à $5+1$ nœuds

Les 9 issus d'une branche au centre, puis un arbre unaire-binaire à $5$ nœuds.

Les 1×4 issus de

sous-arbre de gauche à $1$ nœud et
sous-arbre de droite à $4$ nœuds.

Les 1×2 issus de

sous-arbre de gauche à $2$ nœuds et
sous-arbre de droite à $3$ nœuds.

Les 2×1 issus de

sous-arbre de gauche à $3$ nœuds et
sous-arbre de droite à $2$ nœuds.

Les 4×1 issus de

sous-arbre de gauche à $4$ nœuds et
sous-arbre de droite à $1$ nœud.

Évaluations restantes : ∞/∞

.128013],59/f.78rnb _o=ylaepcwgu)*vdM461z3k`RmhtsP(S0+2Cè[-i:050D0u0P0t0#0s0Q0n0w0s0t0Q0Q0q010P0#0v010406050Q0z0N0N0t0k0r040T0p0s0z0`0p0l050f111315170 0v04051n1g1q0f1n0 0D0#0C0/0;0?0^0O0#0y0O0s1E0O0P0}050*0m0s0u1z0=0@011D1F1H1F0P1N1P1L0P0k1o0P0O1R1B010g0,0u0l0t0N0u010/1a0Q0v0t0l0^0W1L1|1~1,1T1/1P1=1@0}0a0n0R0k0p0v0p0Q0#1d0l0n0(1`0k0k0u0w2l1g230l1o0f1*2y1%1)1(1M0D250^1H0l1;2i1L1w1y0:1S2I0#2K0l0p2O1L0v2r1o2w2y2$101}2m2Q1-2V0k140s0}0n0H2v2*0~2)242,1T2.2:2=0W2^1~2`2w2H012 0t2;040n0J332x0 362}0^393b0n0F3f352*373l2=0d3p3h3r3j380p2/3a2=0G3w2{2+1A2~3B303c0i3G3i3J3k3L3D3c0j3P3y3R3A3C3m0e3X2|3Z3t040H0U3(3I2R3!3M0H2@1h2_3x3)3;3+0H323_343{3:2-3T3b0H3e412x1r2!1g2O2B0D1)2G3z0w2W1^1o4f1p4d2(4a1o4l0(2#3Y3}0}0N0p0P0I0K2T0o1@0N3p0n3H370p0}0q4K4M3z0|040Z3p4S3Z0N0#0}3^2(3Q3;4U0b3w43370K0}0(0g4X4)1-0x2=4@4y2-0g4A4C4E2T4|3|1-4U0S54442~0}1f4t4Y4*0}0A0$3/374`3c0n5o59370Q0D0}015v5k3z5s2=5o0n0X0p0N0v0s0Y0P0u0c0n2j0n0m0u0Q0p2T5L0;0n1H0Q5J0n0L4B4D4F0l4H0u0N0L5x3Z5z5n5o0M1;0C5S1Q5$525)4I0Z0l0b0n0$5W1Q2V0N0m2r2n1Q0E515(2n002T1w0w655.3;5:5B0n5v013w6o5f1-4:040g3B4R4^5b040#6A4}1T0p5m534t4L6B3k0m0}0k1~0y0u5q4T0}585e6N386P04286V3Z576)4z045{5(5*4J6Z6G0^4U0A0c6F556C5d2$6M6@014O040V6|5a0^4!4$6,565h5j4t066o6t6!0l4A0o6E6L6u6H4P773s505%4G4I7c1T4U4W6?6}3k0}7o707q0^740!7t3z7a3,7z6^0}4,7g7i5B7J016w6y0k7N3*0}0K7%3;6I7G6 2_717E6#6Q6S6U7D78016+7`377P4%2_7Y4U6{7p7k7G7R7|7e6s7W7i7Y7l6.7n7+1-740V4Q86728g6/7x5+897B898g7*8o7=7L8j1T808u7T8C7K0}0B8H387v5|6;8F4V8w888z7{8B8U7 4#7Q8X3z8W7I87048y4(724+8c7W8f8N6:7y7~8$0}0h8S040t0v0v1;0D8Q6Y8,7=8q8i8^6*5h8/7;7{6w2r0P0z0k7/349d7u6.6d8s6=957{8v996-9k4b6!8.7g1g4v0u2y2Z9E4e1x4g2B2E2z0t1O9H0f4f0 9R0)0+0-04.