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 42ny6g3p )rPv1-=;oa_ckmi*u5(,e:ts]Shl970[wbf8.+/d 050X0E0G0t0y0L0H0j0v0L0t0H0H0q010G0y0i010406050H0A0x0x0t0l0e040J0s0L0A0=0s0d050W0|0~10120`0i041b1i051l0W1l1n1i0`0X0y0n0*0,0.0:0K0y0g0K0L1B0K0G0^050#0R0L0E1w0-0/011A1C1E1C0G1K1M1I0G0R0s0X121J0l1j0G0K0*150H0i0t0d0:0c011O1y010S0%0E0d0t0x0E1I1:1=1`1Q1}1M20220^0a0j0m0l0s0i0s0H0y180d0j0Z1.0l0l0E0v2n1b250d1j0W1,2A0G1*1)1+0X270:1E0d1 2k1I1t1v0+1P2K0y2M0d1$1u1I0i2t1j2y2A2(0{1;2o2S1{2X0l0 0L0^0j0o2x2,0_2+262.1Q2:2=2@0c2`1=2|2y2J01310t2?040j0h352z0`382 0:3b3d0j0b3h372,393n2@0B3r3j3t3l3a0s2;3c2@0f3y2}2-1x303D323e0N3I3k3L3m3N3F3e0T3R3A3T3C3E3o0M3Z2~3#3v040o0O3*3K2T3$3O0o2_1c2{3z3+3?3-0o343{363}3=2/3V3d0o3g433i3J3u480^0o3q4c2A2#0E2A2Q2D0X2H390v1$231j4p1m2$3J2)2{054u0Z2%3!3 0^0S0t2v3D0y3c3r0j4e3B0s0^0q4R4T3#0@040P3r4Z3?0x0y4h4(3S3?4#0I3y0645390w0^0Z0S4.4I1{0Q2@4~3~2/0S0^200l0t0e1=0t53461Q4#0C5e3u575j3B4#0D4Y4/2/0^0w5m4!0^0k0F3y0j5B4S5r300^0y5q4 1Q4V044X4k5D5J3m0R0^2a5v4:0^5i4k4)5s044L4N0l4P0L5V1{4#0k5A5C5!1Q4`040Q1A1M5I545F041a5O5=0:5L020g0G0r5N2(5P5}3m5G5,5g0^5z4k065C6l6b5f6d5$0u5H615E634W5|6o3a4K4M0G4O4Q5Z6u014#4%6F5Q6z046s6a62015L0p6x394+4-6K6c6H0^4=6t6L5L0z6U3B0d6e6j6m5;6G6-5$6B6D5+6Y6y5L0U6f6p0t0i0i1 0X6 6!045Y2*6=4K6r765.5:6:6Q6?6O2{6n395L0V697l6Q6W3.7g7m3B5@2t0G0A0l606P6G5h7v6l6Q7G6{5k6@5(5*7e0^6J7a6L6?7D4D7F6#6+3#5L0W0W7!4J7N6C5)6E7T6Z6I766?5u7L5n7Z6%6Z7$7(7{6y6?5%7,7P7^5w4$7=5l7 7n0^6T8a6,5t7Q040I5/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^0V8}8Y8E8k2(6k8m6Q7}8}7V7v7J5x3I0W4F4n1k4A0W4y2B4r1b2E2D1#1%2D0t1L9l9o1u2|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)