Nombres de Motzkin

Série d'exercices

Cet exercice fait partie d'une série :

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

.12801342zny6g3p )rPv1-=;oaà_ckmi*u5(,e:ts]Shl970[wbf8+./d050Z0G0I0u0A0N0J0k0x0N0u0J0J0r010I0A0j010406050J0C0z0z0u0m0f040L0t0N0C0@0t0e050Y0~1012140|0j041d1k051n0Y1n1p1k0|0Z0A0o0,0.0:0=0M0A0h0M0N1D0M0I0`050%0T0N0G1y0/0;011C1E1G1E0I1M1O1K0I0T0t0Z141L0m1l0I0M0,170J0j0u0e0=0c011Q1A010U0)0G0e0u0z0G1K1=1@1|1S1 1O22240`0a0k0n0m0t0j0t0J0A1a0e0k0#1:0m0m0G0x2p1d270e1l0Y1.2C0I1,1+1-0Z290=1G0e212m1K1v1x0-1R2M0A2O0e1(1w1K0j2v1l2A2C2*0}1?2q2U1}2Z0m110N0`0k0p2z2.0{2-282:1S2=2@2_0c2|1@2~2A2L01330u2^040k0i372B0|3a310=3d3f0k0b3j392.3b3p2_0D3t3l3v3n3c0t2?3e2_0g3A2 2/1z323F343g0P3K3m3N3o3P3H3g0V3T3C3V3E3G3q0O3#303%3x040p0Q3,3M2V3(3Q0p2{1e2}3B3-3^3/0p363}381m2(1d2S2F0Z2J3b0x1(251l4a1o482,452B054f0#2)3$410`0z0t0I0d0y2X0w240z3t0k3L3b0t0`0r4F4H3D0_040R3t4N3%0z0A0`3|2,3U3^4P0K3A063 3@1}0y0`0#0U4S4!1}0S2_4;4t2;0U4v4x4z2X4_401}4P0E514+320`1c4n4s521S4P0l0H3A0k5j4G4=1S4-040A4:5b5l4`58045a2*5t5d0=4J04020h0I0s4L5s4T410T0`2c563b545P3D0e4}4y4A0e4C0G4E5b5K530`5g5i5k5,5%5v2v0~0N0%0I4M5m5B4K5^5u3o5V4 5x2}5.0=5R5$5_3c595|5A015C0q6a570=4V4X5S3%5f5+5,5j63015o0U3F6f3w0`0A6v3D0t4@5p61385z6g3c5M040m1@0h0G6k4#0`55665}016i3:6P5(040F6z3.696T6b5f5h5b066o6/6G6w6K0G5;5?6$3^5C0W5I5y6q5U044w5W506)6H654Z6U716y5J676d6`1}6W4Y62676m7d6U5C0B7g5v73606Y5e6R7v5~5w7r5`046e7n6b7i7B6c0`7E6 677b7y017m2*6.6:6q0x0p0`030k7t5X5Z0z0k6@0I0k0A0x0A2r1P0N1b0h0C0G0C0m0k6E3k6:6;5T5 7$4D7P5C0X7P710u0j0j210Z7P787k7a0`5:0C5=0u5@765Q5)6n6o7V7X047Z0$0k0N0v7:8z7?7^7`7|0k0W2`8s6q5o2v0I7`7}3g70824B848p4O0`4R8X6%7A8#6Q044%6-1d4q0G2C2%8/491w4b2F2H2D1%1)2F0u1N8=0Y4a0|920$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.