Aller au contenu

Énumération des arbres à n+1 nœuds et k feuilles

Le cadre

Le nombre d'arbres ordonnés à \(n+1\) nœuds et \(k\) feuilles est égal à \(N(n, k)\), un nombre de Narayana dont on donnera la formule plus bas.

Les arbres à 4+1 nœuds et 2 feuilles

Il y en a \(N(4, 2) = 6\).

Formules

\[N(n, k) = \frac1n \binom{n}{k} \binom{n}{k-1}\]
\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]
\[n! = 1×2×3×...×(n-1)×n\quad\text{, et } 0! = 1\]

Exercice

Coder une fonction narayana qui prend en paramètres deux entiers positifs n et k et qui renvoie le nombre d'arbres ayant n+1 nœuds et k feuilles.

La fonction utilise et met à jour un objet de mémoïsation externe à choisir.

Contraintes
  • \(1 \leqslant n < 1024\)
  • \(1 \leqslant k \leqslant n\)
  • Fonction récursive interdite
  • Modules math et functools interdits
  • Code source limité à 2000 caractères
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.339.128013],59/f.78rnb _o=ylaepcwgu)*vd461`3kRmhtsP(S0+2Cè[-i:050E0v0O0u0!0t0P0o0x0t0u0P0P0r010O0!0w010406050P0A0M0M0u0l0s040S0q0t0A0_0q0m050g101214160~0w04051m1f1p0g1m0~0E0!0D0.0:0=0@0N0!0z0N0t1D0N0O0|050)0n0t0v1y0;0?011C1E1G1E0O1M1O1K0O0l1n0O0N1Q1A010h0+0v0m0u0M0v010.190P0w0u0m0@0V1K1{1}1+1S1.1O1;1?0|0b0o0Q0l0q0w0q0P0!1c0m0o0%1_0l0l0v0x2k1f220m1n0g1)2x1$1(1%1L0E240@1G0m1:2h1K1v1x0/1R2H0!2J0m0q2N1K0w2q1n2v2x2#0 1|2l2P1,2U0l130t0|0o0H2u2)0}2(232+1S2-2/2;0V2@1}2_2v2G012~0u2:040o0J322w0~352|0@383a0o0F3e342)363k2;0e3o3g3q3i370q2.392;0G3v2`2*1z2}3A2 3b0j3F3h3I3j3K3C3b0k3O3x3Q3z3B3l0f3W2{3Y3s040H0T3%3H2Q3Z3L0H2?1g2^3w3(3:3*0H313^333`3/2,3S3a0H3d403f3G3r450|0H3n493p3{443!4e3u4h424c4l3+3E4h1q2Z1f2N2A0E1(2F3y0x2V1@1n4y1o4w2%4u4E0%2!3X3|0|0h0u2s3A0!0v0t1O0p1?0M3o0o4b3y0q0|0r4(4*3Y0{040Y3o4:3:0M0!4e4^3P3:4=0c3v4p3y0K0|0%0h4~4Q1,0y2;5a4j2}0h0|1;0l0u0s1}0u5f431S4=0R5q3r5j5v3y4=0d4/4 2,0|0K5y4;0|0B0#3.365d3b0o5Q5H3:0P0E0|015X5M3y5U2;5Q0o0W0q0M0w0t0X0O0v0d0o2i0o0n0v0P0q2S5;0:0o1G0P5/0o0I4T4V0l4X4Z0v4#0v0M0I5Z3Y5#5P5Q0L1:0D5{1P1O0o2U0M0n2q2m00146t5_0o5m1}0O630m0U0H0I6q0a0A0E0-0(630K6I0h0v0A0+1O0P0i6f5T5V6i0o5X013v5%4)5D1S5604585S5c5e4u6-3j5i044E6s6=5s0|5u6^5b2}5x735g0@5A5C743j5F6 795J5L4o6+6+4_1,0P2004016k0m6m4X5 1P4E0v0h1.0x4X0m6D0n2S5*0!390o0K0o1|2.0!6q6)7j7k5R6_016/2q0O0A0l1e4h6,7c374S4U0O4W4Y4!4$7f014=4@775r7d047%2%7W517b78014,040g0g827{7+04657.677:6a7=7`367^7?0m7e8j5z0|527(7m1S8587895w8c7-7/696b4%8p5I4?8m762#7)83850Z8y3y8n045G8G508r537l7W6/0h3A8Q3)0|0!8(3:0q5O2S8,2,0n0|5l0m0z0v7?5t8m8?04278|718J8A66687;6c92040B5B8t7W8S7~2^8M8a850U8;1S4{4}8V1,4=5K6*7U9j8z0h0p8+9e7*854.9C838S8d8C988F7 7*8l9r75049B8L8u0@8O9n0@9p3+9a8s9U7W850C9Y8b9T3_9w9x8R7,968g8E7?856Y9Q7|0u0w0w1:0E9a729N9H4S9A9a0B8Y5%9V7X8@0(7#9h339;8)6|5*0na494aj2wae7a9G8a8S8Ua68a9t9,9*9,8S6}ap9}7@93aJ9g9a9d9(7*ayaD0|8Paw369!3@aA8k5JaT8688aW9=7}3F0g4N0v2x2Ya:4x1w4z2A2D2y0u1Na?0g4y0~b00(0*0,04.
Arbres à 5+1 nœuds et 3 feuilles

Il y en a \(N(5, 3) = 20\)