Énumération des arbres unaires-binaires à n+1 nœuds⚓︎

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 : 5/5

.128013[(lbzsS]et-ph4rd;5.f1890uma"ov+w7g,_/3=in 6k:)y *à2Pc030k0d0e0v0I070a0Q0V070v0a0a0H0w0e0I0g0w020K030a0t0u0u0v0j0P020b0x070t0/0x0J030F0_0{0}0 0@0g02031f181i0F1f0@0k0I0y0'0)0+0-0h0I0C0h071w0h0e0=030Z08070d1r0*0,0w1v1x1z1x0e1F1H1D0e0j1g0e0h0'120a0g0v0J0-0T0w1J1t0w0o0#0d0J0v0u0d1D1$1'1,1L1/1H1=1@0=040Q0U0j0x0g0x0a0I150J0Q0X1!0j0j0d0V2c181`0J1g0F1Y2p1V1X1W1E0k1|0-1z0J1;291D1o1q0(1K2z0I2B0J0x2F1D0g2i1g2n2p2T0^1%2d2H1-2M0j0|070=0Q0p2m2X0?2W1{2Z1L2#2%2(0T2+1'2-2n2y0w2=0v2'020Q0G2_2o0@2|2:0-2 310Q0i352{2X2}3b2(0m3f373h392~0x2$302(0L3m2.2Y1s2;3r2?320B3w383z3a3B3t320q3F3o3H3q3s3c0r3N2/3P3j020p0s3U3y2I3Q3C0p2*192,3n3V3%3X0p2^3+2`1j2R182F2s0k1X2x3p0V2N1^1g3{1h3_2V3?2o03410X2S3O3/0=0u0x0e090M2K0E1@0u3f0Q3x2}0x0=0H4r4t3p0;02053f4z3P0u0I0=3*2V3G3%4B0c3m0K3-3$1-0M0=0X0o4y4M2!0o4h4j4l2K4E4!1L4B064*4f2!0=17494e3.1-4B0O0N3m0Q4 4s4+0-4V020I4Y4@514:2;4=4Z5a0-4v02000C0e0l4x584F3/080=1 4/4_4,0=4.4@5o4;024i4k4m0J4o0d4q5y520w4{4}4@0K505Q595u3a0=2i0_070Z0e5d5T0w5g5m2T5S4T5b5B4'5E5t5+0-4-5:3i5c5n5K5g0f5#5;0w4H4J5@4A0=0O4~5R4 5z1L540o3r5~5^556f3p0x0A0=4)5`5e2~5q020j1'0C0d633P5?5J6p613Y6x4N0=0D6i3W5_4L6p5M67685Q6a5U6s0d5X5Z6I3%5g0z5(2,5*6g5C4(4?6L5$6z6+5 0J6m6X1-5|6=1L6C4K2,6R5L656^5f0=0R702~4%5D6n6.2}6-6|5K6:026*6$6}6@6o5$6`747j5)6}7e0I6E4`6 5O6P6%400p0=010Q6(5E5G0u0Q6U0e0Q0I0V0I2e1I07160C0t0d0t0j0Q7g2`5P6P7q766)7G7t1L5g0n7*6S0v0g0g1;0k7.6~025x793p7e5W0t5Y0v5!6A6,7v2T7#686}0V7A027C0Y0Q070S7P8g7S7U7W7Y0Q0z2)6O7y3P542i0e7W7Z2o8t4g5-775F4p7^4B4D846/6K7c6M0=4P5O184c0d2p2Q8U3`1p3|2s2v2q0v1G8X0F3{0@8*0Y0!0$02.

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.