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:pbvà(40i2z+edm3;s7= 1o5w_lSnatf-)9h]6,crg.*[yPku8/050o0n0F0E0j0B0s0v0O0B0E0s0s0u010F0j0c010406050s0X0p0p0E0P0U040C0x0B0X0@0x0D050Z0~1012140|0c041d1k051n0Z1n1p1k0|0o0j0e0,0.0:0=0K0j0Q0K0B1D0K0F0`050%0d0B0n1y0/0;011C1E1G1E0F1M1O1K0F0d0x0o141L0P1l0F0K0,170s0c0E0D0=0k011Q1A010G0)0n0D0E0p0n1K1=1@1|1S1 1O22240`0a0v0V0P0x0c0x0s0j1a0D0v0#1:0P0P0n0O2p1d270D1l0Z1.2C0F1,1+1-0o290=1G0D212m1K1v1x0-1R2M0j2O0D1(1w1K0c2v1l2A2C2*0}1?2q2U1}2Z0P110B0`0v0w2z2.0{2-282:1S2=2@2_0k2|1@2~2A2L01330E2^040v0q372B0|3a310=3d3f0v0h3j392.3b3p2_0y3t3l3v3n3c0x2?3e2_0M3A2 2/1z323F343g0t3K3m3N3o3P3H3g0Y3T3C3V3E3G3q0J3#303%3x040w0i3,3M2V3(3Q0w2{1e2}3B3-3^3/0w363}381m2(1d2S2F0o2J3b0O1(251l4a1o482,452B054f0#2)3$410`0p0x0F0l0W2X0A240p3t0v3L3b0x0`0u4F4H3D0_040T3t4N3%0p0j0`3|2,3U3^4P0L3A063 3@1}0W0`0#0G4S4!1}0z2_4;4t2;0G4v4x4z2X4_401}4P0g514+320`1c4n4s521S4P0I0b3A0v5j4G4=1S4-040j4:5b5l4`58045a2*5t5d0=4J04020Q0F0r4L5s4T410d0`2c563b545P3D0D4}4y4A0D4C0n4E5b5K530`5g5i5k5,5%5v2v0~0B0%0F4M5m5B4K5^5u3o5V4 5x2}5.0=5R5$5_3c595|5A015C0H6a570=4V4X5S3%5f5+5,5j63015o0G3F6f3w0`0j6v3D0x4@5p61385z6g3c5M040P1@0Q0n6k4#0`55665}016i3:6P5(040N6z3.696T6b5f5h5b066o6/6G6w6K0n5;5?6$3^5C0m5I5y6q5U044w5W506)6H654Z6U716y5J676d6`1}6W4Y62676m7d6U5C0S7g5v73606Y5e6R7v5~5w7r5`046e7n6b7i7B6c0`7E6 677b7y017m2*6.6:6q0O0w0`030v7t5X5Z0p0v6@0F0v0j0O0j2r1P0B1b0Q0X0n0X0P0v6E3k6:6;5T5 7$4D7P5C0R7P710E0c0c210o7P787k7a0`5:0X5=0E5@765Q5)6n6o7V7X047Z0$0v0B0f7:8z7?7^7`7|0v0m2`8s6q5o2v0F7`7}3g70824B848p4O0`4R8X6%7A8#6Q044%6-1d4q0n2C2%8/491w4b2F2H2D1%1)2F0E1N8=0Z4a0|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.