Nombres de Narayana
On admettra que 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\).
Écrire une fonction telle que narayana(n, k) renvoie le nombre d'arbres ayant n+1 nœuds et k feuilles. On utilisera un dictionnaire pour mémoriser les résultats intermédiaires.
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\]
On n'utilisera pas le module math pour cet exercice.
Exemples
>>> narayana(4, 3)
6
>>> narayana(5, 3)
20
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
.128013 ,n w-*5e9](38m=0p)rhk[uois;cb/6.S1vt_dg:ay24P+fl7 050M0i0K0P0z0W0A0d0C0W0P0A0A0p010K0z0r010406050A0x0o0o0P0t0Q040H0y0W0x0=0y0c050E0|0~10120`0r041b1i051l0E1l1n1i0`0M0z0J0*0,0.0:0u0z0N0u0W1B0u0K0^050#0D0W0i1w0-0/011A1C1E1C0K1K1M1I0K0D0y0M121J0t1j0K0u0*150A0r0P0c0:0R011O1y010V0%0i0c0P0o0i1I1:1=1`1Q1}1M20220^0a0d0T0t0y0r0y0A0z180c0d0Z1.0t0t0i0C2n1b250c1j0E1,2A0K1*1)1+0M270:1E0c1 2k1I1t1v0+1P2K0z2M0c1$1u1I0r2t1j2y2A2(0{1;2o2S1{2X0t0 0W0^0d0I2x2,0_2+262.1Q2:2=2@0R2`1=2|2y2J01310P2?040d0m352z0`382 0:3b3d0d0S3h372,393n2@0h3r3j3t3l3a0y2;3c2@0F3y2}2-1x303D323e0X3I3k3L3m3N3F3e0n3R3A3T3C3E3o0j3Z2~3#3v040I0q3*3K2T3$3O0I2_1c2{3z3+3?3-0I343{363}3=2/3V3d0I3g433i3J3u480^0I3q4c2A2#0i2A2Q2D0M2H390C1$231j4p1m2$3J2)2{054u0Z2%3!3 0^0V0P2v3D0z3c3r0d4e3B0y0^0p4R4T3#0@040w3r4Z3?0o0z4h4(3S3?4#0k3y0645390v0^0Z0V4.4I1{0e2@4~3~2/0V0^200t0P0Q1=0P53461Q4#0l5e3u575j3B4#0b4Y4/2/0^0v5m4!0^0s0O3y0d5B4S5r300^0z5q4 1Q4V044X4k5D5J3m0D0^2a5v4:0^5i4k4)5s044L4N0t4P0W5V1{4#0s5A5C5!1Q4`040e1A1M5I545F041a5O5=0:5L020N0K0B5N2(5P5}3m5G5,5g0^5z4k065C6l6b5f6d5$0L5H615E634W5|6o3a4K4M0K4O4Q5Z6u014#4%6F5Q6z046s6a62015L0f6x394+4-6K6c6H0^4=6t6L5L0g6U3B0c6e6j6m5;6G6-5$6B6D5+6Y6y5L0G6f6p0P0r0r1 0M6 6!045Y2*6=4K6r765.5:6:6Q6?6O2{6n395L0U697l6Q6W3.7g7m3B5@2t0K0x0t606P6G5h7v6l6Q7G6{5k6@5(5*7e0^6J7a6L6?7D4D7F6#6+3#5L0E0E7!4J7N6C5)6E7T6Z6I766?5u7L5n7Z6%6Z7$7(7{6y6?5%7,7P7^5w4$7=5l7 7n0^6T8a6,5t7Q040k5/6/6:7w7#0^6*8e86797X7U6A7O7.8u7:7R885 8h6$7E6(0^7%7)5#826_8h7S8z808g8r3?6S8K1Q7t3`7/6y4;8W6v048J8T8L6^7-6`8!397;857*7W368n8U8c8%6M7@8G7|0^0U8}8Y8E8k2(6k8m6Q7}8}7V7v7J5x3I0E4F4n1k4A0E4y2B4r1b2E2D1#1%2D0P1L9l9o1u2|9o0!0$0(04.
Arbres à 5+1 nœuds et 3 feuilles
Il y en a \(N(5, 3) = 20\)
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)