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

.128013s3o_8;bcdufvg/0lyà n7apS.r1-me,(P2=4:+twzki9][5h*)6050j0E0N0w0R0q0b0t0i0q0w0b0b0J010N0R0x010406050b0k0D0D0w0A0r040y0d0q0k0@0d0u050o0~1012140|0x041d1k051n0o1n1p1k0|0j0R0m0,0.0:0=0W0R0n0W0q1D0W0N0`050%0h0q0E1y0/0;011C1E1G1E0N1M1O1K0N0h0d0j141L0A1l0N0W0,170b0x0w0u0=0I011Q1A010l0)0E0u0w0D0E1K1=1@1|1S1 1O22240`0a0t0H0A0d0x0d0b0R1a0u0t0#1:0A0A0E0i2p1d270u1l0o1.2C0N1,1+1-0j290=1G0u212m1K1v1x0-1R2M0R2O0u1(1w1K0x2v1l2A2C2*0}1?2q2U1}2Z0A110q0`0t0B2z2.0{2-282:1S2=2@2_0I2|1@2~2A2L01330w2^040t0c372B0|3a310=3d3f0t0K3j392.3b3p2_0V3t3l3v3n3c0d2?3e2_0Z3A2 2/1z323F343g0v3K3m3N3o3P3H3g0f3T3C3V3E3G3q0S3#303%3x040B0p3,3M2V3(3Q0B2{1e2}3B3-3^3/0B363}381m2(1d2S2F0j2J3b0i1(251l4a1o482,452B054f0#2)3$410`0D0d0N0P0Q2X0e240D3t0t3L3b0d0`0J4F4H3D0_040U3t4N3%0D0R0`3|2,3U3^4P0T3A063 3@1}0Q0`0#0l4S4!1}0O2_4;4t2;0l4v4x4z2X4_401}4P0G514+320`1c4n4s521S4P0Y0L3A0t5j4G4=1S4-040R4:5b5l4`58045a2*5t5d0=4J04020n0N0g4L5s4T410h0`2c563b545P3D0u4}4y4A0u4C0E4E5b5K530`5g5i5k5,5%5v2v0~0q0%0N4M5m5B4K5^5u3o5V4 5x2}5.0=5R5$5_3c595|5A015C0C6a570=4V4X5S3%5f5+5,5j63015o0l3F6f3w0`0R6v3D0d4@5p61385z6g3c5M040A1@0n0E6k4#0`55665}016i3:6P5(040F6z3.696T6b5f5h5b066o6/6G6w6K0E5;5?6$3^5C0M5I5y6q5U044w5W506)6H654Z6U716y5J676d6`1}6W4Y62676m7d6U5C0X7g5v73606Y5e6R7v5~5w7r5`046e7n6b7i7B6c0`7E6 677b7y017m2*6.6:6q0i0B0`030t7t5X5Z0D0t6@0N0t0R0i0R2r1P0q1b0n0k0E0k0A0t6E3k6:6;5T5 7$4D7P5C0z7P710w0x0x210j7P787k7a0`5:0k5=0w5@765Q5)6n6o7V7X047Z0$0t0q0s7:8z7?7^7`7|0t0M2`8s6q5o2v0N7`7}3g70824B848p4O0`4R8X6%7A8#6Q044%6-1d4q0E2C2%8/491w4b2F2H2D1%1)2F0w1N8=0o4a0|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.