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

.1280135[tf4)+2r3,sa-o iug08àm1]P6p*nl7h.e=cy:v9z(w;S/b_dk050Y0J0d0n0r0F0m0q0L0F0n0m0m0K010d0r0C010406050m0s0x0x0n0j0M040U0p0F0s0@0p0E050V0~1012140|0C041d1k051n0V1n1p1k0|0Y0r0O0,0.0:0=0H0r0t0H0F1D0H0d0`050%0W0F0J1y0/0;011C1E1G1E0d1M1O1K0d0W0p0Y141L0j1l0d0H0,170m0C0n0E0=0i011Q1A010e0)0J0E0n0x0J1K1=1@1|1S1 1O22240`0a0q0A0j0p0C0p0m0r1a0E0q0#1:0j0j0J0L2p1d270E1l0V1.2C0d1,1+1-0Y290=1G0E212m1K1v1x0-1R2M0r2O0E1(1w1K0C2v1l2A2C2*0}1?2q2U1}2Z0j110F0`0q0y2z2.0{2-282:1S2=2@2_0i2|1@2~2A2L01330n2^040q0k372B0|3a310=3d3f0q0f3j392.3b3p2_0b3t3l3v3n3c0p2?3e2_0B3A2 2/1z323F343g0G3K3m3N3o3P3H3g0v3T3C3V3E3G3q0P3#303%3x040y0u3,3M2V3(3Q0y2{1e2}3B3-3^3/0y363}381m2(1d2S2F0Y2J3b0L1(251l4a1o482,452B054f0#2)3$410`0x0p0d0Q0Z2X0X240x3t0q3L3b0p0`0K4F4H3D0_040c3t4N3%0x0r0`3|2,3U3^4P0z3A063 3@1}0Z0`0#0e4S4!1}0S2_4;4t2;0e4v4x4z2X4_401}4P0R514+320`1c4n4s521S4P0g0N3A0q5j4G4=1S4-040r4:5b5l4`58045a2*5t5d0=4J04020t0d0T4L5s4T410W0`2c563b545P3D0E4}4y4A0E4C0J4E5b5K530`5g5i5k5,5%5v2v0~0F0%0d4M5m5B4K5^5u3o5V4 5x2}5.0=5R5$5_3c595|5A015C0o6a570=4V4X5S3%5f5+5,5j63015o0e3F6f3w0`0r6v3D0p4@5p61385z6g3c5M040j1@0t0J6k4#0`55665}016i3:6P5(040l6z3.696T6b5f5h5b066o6/6G6w6K0J5;5?6$3^5C0h5I5y6q5U044w5W506)6H654Z6U716y5J676d6`1}6W4Y62676m7d6U5C0D7g5v73606Y5e6R7v5~5w7r5`046e7n6b7i7B6c0`7E6 677b7y017m2*6.6:6q0L0y0`030q7t5X5Z0x0q6@0d0q0r0L0r2r1P0F1b0t0s0J0s0j0q6E3k6:6;5T5 7$4D7P5C0I7P710n0C0C210Y7P787k7a0`5:0s5=0n5@765Q5)6n6o7V7X047Z0$0q0F0w7:8z7?7^7`7|0q0h2`8s6q5o2v0d7`7}3g70824B848p4O0`4R8X6%7A8#6Q044%6-1d4q0J2C2%8/491w4b2F2H2D1%1)2F0n1N8=0V4a0|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.