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

.128013*yl29àutgmro;Sp)_8:w+v/.5(6n,b13]d0ce 4k[=-Pziasfh7050I0L0i0V0U0d0W0M0K0d0V0W0W0Q010i0U0p010406050W0h0k0k0V0l0c040o0m0d0h0@0m0C050x0~1012140|0p041d1k051n0x1n1p1k0|0I0U0w0,0.0:0=0Y0U0j0Y0d1D0Y0i0`050%0E0d0L1y0/0;011C1E1G1E0i1M1O1K0i0E0m0I141L0l1l0i0Y0,170W0p0V0C0=0e011Q1A010X0)0L0C0V0k0L1K1=1@1|1S1 1O22240`0a0M0S0l0m0p0m0W0U1a0C0M0#1:0l0l0L0K2p1d270C1l0x1.2C0i1,1+1-0I290=1G0C212m1K1v1x0-1R2M0U2O0C1(1w1K0p2v1l2A2C2*0}1?2q2U1}2Z0l110d0`0M0F2z2.0{2-282:1S2=2@2_0e2|1@2~2A2L01330V2^040M0G372B0|3a310=3d3f0M0N3j392.3b3p2_0z3t3l3v3n3c0m2?3e2_0B3A2 2/1z323F343g0Z3K3m3N3o3P3H3g0s3T3C3V3E3G3q0f3#303%3x040F0J3,3M2V3(3Q0F2{1e2}3B3-3^3/0F363}381m2(1d2S2F0I2J3b0K1(251l4a1o482,452B054f0#2)3$410`0k0m0i0T0O2X0r240k3t0M3L3b0m0`0Q4F4H3D0_040P3t4N3%0k0U0`3|2,3U3^4P0H3A063 3@1}0O0`0#0X4S4!1}0u2_4;4t2;0X4v4x4z2X4_401}4P0A514+320`1c4n4s521S4P0q0t3A0M5j4G4=1S4-040U4:5b5l4`58045a2*5t5d0=4J04020j0i0n4L5s4T410E0`2c563b545P3D0C4}4y4A0C4C0L4E5b5K530`5g5i5k5,5%5v2v0~0d0%0i4M5m5B4K5^5u3o5V4 5x2}5.0=5R5$5_3c595|5A015C0R6a570=4V4X5S3%5f5+5,5j63015o0X3F6f3w0`0U6v3D0m4@5p61385z6g3c5M040l1@0j0L6k4#0`55665}016i3:6P5(040D6z3.696T6b5f5h5b066o6/6G6w6K0L5;5?6$3^5C0v5I5y6q5U044w5W506)6H654Z6U716y5J676d6`1}6W4Y62676m7d6U5C0b7g5v73606Y5e6R7v5~5w7r5`046e7n6b7i7B6c0`7E6 677b7y017m2*6.6:6q0K0F0`030M7t5X5Z0k0M6@0i0M0U0K0U2r1P0d1b0j0h0L0h0l0M6E3k6:6;5T5 7$4D7P5C0y7P710V0p0p210I7P787k7a0`5:0h5=0V5@765Q5)6n6o7V7X047Z0$0M0d0g7:8z7?7^7`7|0M0v2`8s6q5o2v0i7`7}3g70824B848p4O0`4R8X6%7A8#6Q044%6-1d4q0L2C2%8/491w4b2F2H2D1%1)2F0V1N8=0x4a0|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.