Nombres de Catalan (2)

Il y a 1 arbre binaire de taille 0.
Il y a 1 arbre binaire de taille 1.
Il y a 2 arbres binaires de taille 2.
Il y a 5 arbres binaires de taille 3.
Il y a 14 arbres binaires de taille 4.

Arbres binaires de taille 4

Les 14 arbres binaires de taille 4, peuvent être répartis en fonction de la taille des sous arbres.

Il y a un nœud racine et 3 autres nœuds à répartir à gauche ($t_g$) et à droite ($t_d$).

\[(1 + t_g + t_d = 4)\]

$(t_g=0, t_d=3)$

$(t_g=1, t_d=2)$

$(t_g=2, t_d=1)$

$(t_g=3, t_d=0)$

Objectif : écrire une fonction telle que nb_arbres_binaires(n) renvoie le nombre d'arbres binaires de taille n. Il existe plusieurs méthodes de calcul. Voici une méthode pédagogique pour calculer ce nombre en fonction de n. Il s'agit des nombres de Catalan.

Si la taille $n$ vaut zéro,
- renvoyer $1$. Il y a un seul arbre à zéro nœud, un arbre vide.
Sinon,
- l'arbre possède une racine et deux sous-arbres. Les tailles possibles pour les sous-arbres sont :
  - $0$ à gauche et $n-1$ à droite
  - $1$ à gauche et $n-2$ à droite
  - $2$ à gauche et $n-3$ à droite
  - ...
  - $n-3$ à gauche et $2$ à droite
  - $n-2$ à gauche et $1$ à droite
  - $n-1$ à gauche et $0$ à droite
- renvoyer la somme du nombre d'arbres dans chaque cas.

Indices

Pour un arbre binaire de taille $5$, il y a un nœud racine et $4$ autres nœuds. Ces derniers peuvent se répartir en $(0, 4)$, $(1, 3)$, $(2, 2)$, $(3, 1)$, $(4, 0)$ à gauche et à droite.

Pour $(0, 4)$, il y a
- $1$ sous-arbre à gauche possible, à 0 nœud,
- $14$ sous-arbres à droite possibles à 4 nœuds,
- ainsi $1×14$ possibilités de choisir un arbre binaire de taille $0$ à gauche et de taille $4$ à droite.
Pour $(1, 3)$, il y a
- $1$ sous-arbre à gauche possible à 1 nœud,
- $5$ sous-arbres à droite possibles à 3 nœuds,
- donc $1×5$ possibilités pour ce cas.
Pour $(2, 2)$, il y a $2×2$ possibilités.
Pour $(3, 1)$, il y a $5×1$ possibilités.
Pour $(4, 0)$, il y a $14×1$ possibilités.

Il y a donc $1×14 + 1×5 + 2×2 + 5×1 + 14×1 = 42$ arbres binaires de taille $5$.

On stocke les résultats qui sont utilisés souvent dans une liste catalan_mem, cette liste commence avec [1, 1, 2, 5, 14, 42]. Il est très utile de mettre à jour cette liste dès que possible.

Exemples

🐍 Console Python

>>> nb_arbres_binaires(3)
5
>>> nb_arbres_binaires(4)
14
>>> nb_arbres_binaires(5)
42

Code à compléter :

Évaluations restantes : 10/10

.1280135qN/(ê+0L=._a1ki o4m2:fedw,y]-cIrCvpsO3[*nPgJ)ul;jSétx9àMRbèh867050z0y0#0n0q0W0L0r0F0W0n0L0L0k010#0q0K010406050L0V0u0u0n0H0C040Z0s0W0V140s0Q0r020n0u0K0X0r0*0y1e0H0c0V0y0L050e1b1d1f1h190K04051M1F1P0e1M190z0q0J0|0~10120-0q0S0-0W1%0-0#17050@0+0W0y1Y0 11011$1(1*1(0#1:1=1.0#0H1N0#0-0|1k0L0K0n0Q120v011@1!010x0_0y0Q1s0y1.2a2c2h1_2k1=2n0u2p040a0r0R0H0s0K0s0L0q1n1p0=280H0H0y0F2K1F2r0Q1N0e262W2325241/0z2t121*0Q2m2H1.1V1X0}1^2*0q2,0Q0s2:1.0K2P1N2U2W311a2b1p2=2i2`0H1e0W170r0o2T3518342s371_393b3d0v3g2c3i2U2)013n0n3c040r0N3r2V193u3l123x3z0r0t3D3t353v3J3d0b3N3F3P3H3w0s3a3y3d0/3U3j361Z3m3Z3o3A0:3(3G3+3I3-3#3A0.3;3W3?3Y3!3K0%3|3k3~3R040o0i433*2?3 3.0o3f1G3h3V444c460o3q4h3s1Q2 1F2:2Z0z252(3X0F2{2z0;1W1N2~0y303h3N054A0=4I4k2i0F0o17030r0G0Q2J0q3y0q0L0n2K0r0z0n0r0~0r1b2J1?0=0{0H0!1b0W0@0#1E4p3E3)3Q170F4%3y2c0m2y0u3N0r503X0s170k5a5c3~16040O4K3=4c0u0q174g335o2i5k0D3U064j4b2i0p170=0x5n3}4c0A3d5I4P3m0x170Q0+0m1f0+2P0L0m0+2^0^5X5N5C1_5k0f5(51040Q5-3X5k0U0w3U0r5`5b5v1_5E040q5H4~3A5i4l5R5h5}125e04020S0#0X5g635|5J380+172w5;5j175,63653852540~0Q571y6p4c5?5^63065{6I6j5O3I170L0s1d0y0m534}316K5)6a5f686k1_5q17496G6J5{6u5~170x3Z6!6L3w170q6=6X010s5L605:6i6-3I6m040H2c0S0y6C5w6r7a3m676t69016E5_6+6J726@046O6Q6S0 6`3v6b0h6h6V7n0Q5R5T5V5X5Z5#0q5%7g6#125+7d6M607O7i170U7u5d170P7V457C5U0H5W1D7G2n7I1D7R7N7K6?7B5/7Z4c6b0E7@2i6%477{1_7_7 7P6_7:6{5?7k6+7n4R4T4V0F0q0B0|6x56584.0y764)1?0W1o0S1C0V0H0r70316H7l7A6w0@6y6A59857v170l7R7=0n0K0K2m0z7.7c8H3X7=7q2y7s6U4J7h876*6,7h5 2P0#8u8x3h6W5.538D8j6B8U6q5l8L7f5u7L7S045y6G1F4M4H4r970e4u1F0#4w9c2$2X0n1;994u1L4O6{2P0u0m0x0n0p6R0-0N171x1z1B1D0r6F331S3i1k3i1*040j4+4G5q0,2P0r2b0H141?0(281t0W0!0#8m0r1D0#0r9X4-2k1p4L4B3v1{1)1+1-9n3v8+0?8.827o8?556z588S8|8`667?a77b924K0e96048g1o4.0s0V0-0^9$4,4+0J3y0y8u4)002^1V0F1?7n1f2J0-1e9$0$17090f0Q097U6i2Maz1 8p4#9$0l0r0M0V0r5!2m5b969=1+1}1,2q907=8/3s8;7W6c6e6g9 5S6n2ma56s8 7;8Ca28Fa5aN9Faf0r0n0V9B0W8h0{ai8P1m0r4@2G0Q0z9R1V2P2R1y2m0#8g2I2`0Q8g0_0r9sbh1=8h0W0F0V1=8v0?4,000n0Yak9$8v9,4+1*0L9$8gaz0r1B0q8lbAan9+ap4,1%2,9S4@0F0!0=0QaU1F9K199K9:4N8X6R6T954B3A9)0r0Vb-b~8o0{6Tby4X144!0L0!9Wa;3~aC26aF0yaH04aJ0iaM5abSb+0Sb-0/aV0Gbc0Cb8cj4cclaE4%coaIaKct6i6Tb)9#0V1V9%2MaB0HaDcncpaJ0f0i8g0Q0E0o0UcN318gcWcYcJc!0f0f0oc(0E0vc,b53hc/7hcHcZcL090F0z0s4|c-c cF2id2c=cLaKc{8gc+da3sd090deaGdgc)c_0r0ic}3NaV9MaZak0}aAa%3X9?a*9_7n5 6:0Ha_6^9 6}6^a/2Vdc3m74760Q78a}8}a9a 867T9E4Jaec2bA8m4+a!9/d1cXcmdfcqcMc~a:0#ak0H0L8KbH9J0q04b9b.1y0q9%d~auc:d^dqd`0q0kcsd|2V8g0WbM1m9R0!9!2yb?4)aY4A0V0KbD0=0J8n0g23aAd?c;egaJdsdl2Vb^e5b`e5e7ec8v4/areveecIeK0fei0oeNagbLb9eG0res0!eu9*0zexakeA4;0yeD4+eF9ReZd3d`c)0ve)ePe4042M1e4X9Q1?0S0!0Q0!761=enepe-e/e;ew28ezeBe{eEe-f0d_eLc*0E0qf50eb_1Fe319fDeQ059KdzdL0ubH1?2GaubDcPa#fwe#fBelc3bV4)1o0Fa$9;dFa)9^a,b05/7D7%7F5!7+7Jd%3v7/f`8VdOaa5*7TdP7XdNf:7$7(5Yf@5$7-g07M8Tf}7!d$8:7n81717h7}5tgj7hgl7z7h7=84gg6Dg26td,4Nf6eR040T0VbV610q1o0{fT6Pe;gbcwb-0%f)4N4U0G8ebX8ia31y8l8n2M8qdY8t8v70af05fGfKe50Zb#aic4bs4@4)2cgM4+bV0H0V2R8u1?4Abl4Y1o2,0Wfj0|00c49BgU4H1p024`1v2w0fa18E58aNg/fIf70)0^0{9,aw101C8ob*0+dBbDb|hjf;g87*gb0LaK0r0E3ehtd-4+9#0!b88O0y9!8gbKd70Qf(hJ04hq8^8Gb74+0z0!0Y9XhX0r5qhz0rbOauf92c0qfcbi0!bGe01W0yh%9*bzc4h)f(g)8rg,hia9af8KhvgE0M1pbg9*0^0Q2I9YeA9#9%4-1}b-48hia(1|f-9`f~h-g!b3gd6|8Jd#8N8Pbld!iO8WgOb 7tiO8%b6c2infE0eg;io1F9I191;0s0F0p1Bd84H9mcB9(0$aT4;00054+0-2P0x1#1 0K0L0w0e0e0x0H0l0A0q0p150y1V0n0l3Z0S0ejhjj0e0d6P7(0m0=0m0Ig!17e,5Xh{9#0-4B0{aP3ybG0W1F0ne*eAgH9(0x2k53aze11Q3i0ei;i?i^9$j#0=0@0_0L04.