Nombres de Motzkin

Arbres binaires - inutile ici

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

Soit c'est un arbre vide.
Soit c'est un arbre qui a 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.

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

Objectif : Écrire une fonction telle que motzkin(n) 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).

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

Il y en a 4 :

Énumérer les arbres unaires-binaires à $n+1$ nœuds

Si $n = 0$, alors la réponse est $1$. Il n'y a qu'un arbre unaire-binaire à $1$ nœud.
Sinon, la racine possède un ou deux sous-arbres.
- Pour un unique sous-arbre, il y a à compléter par un arbre unaire-binaire à $n$ nœuds. $n = 1 + (n-1)$, donc il y a motzkin(n-1) possibilités.
- Pour deux sous-arbres, pour un total de $n$ nœuds, la répartition peut se faire :
  - $n-1$ à gauche, $1$ à droite. Il y a motzkin(n-2) * motzkin(0) possibilités.
  - $n-2$ à gauche, $2$ à droite. Il y a ??? possibilités.
  - $n-3$ à gauche, $3$ à droite. Il y a ??? possibilités.
  - ...
  - $3$ à gauche, $n-3$ à droite. Il y a ??? possibilités.
  - $2$ à gauche, $n-2$ à droite. Il y a ??? possibilités.
  - $1$ à gauche, $n-1$ à droite. Il y a ??? possibilités.
- Les possibilités décrites sont distinctes, leur nombre est donc la somme des cas.

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

Il y en a 9 :

Exemples

>>> motzkin(4)
9
>>> motzkin(5)
21

Compléter le code :

Évaluations restantes : 10/10

.128013ben,49vi[+3àmo5_t;Phklpwf(: cg.a=ry0zS6]*-u/72)s18d050Z0c0r0G0i0w0W0C0D0w0G0W0W0H010r0i0x010406050W0R0n0n0G0I0J040M0o0w0R0@0o0d050S0~1012140|0x04051k1d1n0S1k0|0Z0i0h0,0.0:0=0u0i0E0u0w1B0u0r0`050%0b0w0c1w0/0;011A1C1E1C0r1K1M1I0r0I1l0r0u0,170W0x0G0d0=0U011O1y010z0)0c0d0G0n0c1I1+1-1=1Q1^1M1{1}0`0a0C0t0I0o0x0o0W0i1a0d0C0#1)0I0I0c0D2i1d200d1l0S1%2v1!1$1#1J0Z220=1E0d1`2f1I1t1v0-1P2F0i2H0d0o2L1I0x2o1l2t2v2Z0}1,2j2N1?2S0I110w0`0C0X2s2%0{2$212)1Q2+2-2/0U2=1-2@2t2E012|0G2.040C0l302u0|332`0=36380C0f3c322%343i2/0p3m3e3o3g350o2,372/0N3t2^2(1x2{3y2}390T3D3f3G3h3I3A390Y3M3v3O3x3z3j0g3U2_3W3q040X0K3#3F2O3X3J0X2;1e2?3u3$3.3(0X2 3?311o2X1d2L2y0Z1$2D3w0D2T1~1l431m412#3~2u05490#2Y3V3`0`0n0o0r0L0v2Q0q1}0n3m0C3E340o0`0H4z4B3w0_040j3m4H3W0n0i0`3=2#3N3.4J0O3t063^3-1?0v0`0#0z4M4U1?0y2/4+4n2*0z4p4r4t2Q4:3_1?4J0A4{4#2{0`1c4h4m4|1Q4J0V0B3t0C5d4A4,1Q4%040i4*555f4;5204542Z5n570=4D04020E0r0s4F5m4N3`0b0`2550344~5J3w0d4@4s4u0d4w0c4y555E4}0`5a5c5e5$5X5p2o0~0w0%0r4G5g5v4E5/5o3h5P4_5r2?5(0=5L5W5:35535?5u015w0Q64510=4P4R5M3W595#5$5d5}015i0z3y693p0`0i6p3w0o4.5j5{315t6a355G040I1-0E0c6e4V0`4 605@016c3)6J5Y040e6t3%636N65595b55066i6)6A6q6E0c5+5-6W3.5w0k5C5s6k5O044q5Q4`6Z6B5 4T6O6{6s5D61676;1?6Q4S5|616g776O5w0P7a5p6}5`6S586L7p5^5q7l5;04687h657c7v660`7y6_61757s017g2Z6(6*6k0D0X0`030C7n5R5T0n0C6.0r0C0i0D0i2k1N0w1b0E0R0c0R0I0C6y3d6*6+5N5_7W4x7J5w0F7J6{0G0x0x1`0Z7J727e740`5*0R5,0G5.705K5Z6h6i7P7R047T0$0C0w0m7*8t7-7/7;7?0C0k2:8m6k5i2o0r7;7@396`7|4v7~8j4I0`4L8R6X7u8V6K044X6%1d4k0c2v2W8)421u442y2B2w0G1L8,0S430|8_0$0(0*04.

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.