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 s3o_8;bcdufvg/0ly n7apS.r1-me,(P2=4:+twki9][5h*)6 050j0D0M0v0P0q0b0s0i0q0v0b0b0I010M0P0w010406050b0k0C0C0v0z0r040x0d0q0k0=0d0t050o0|0~10120`0w041b1i051l0o1l1n1i0`0j0P0m0*0,0.0:0U0P0n0U0q1B0U0M0^050#0h0q0D1w0-0/011A1C1E1C0M1K1M1I0M0h0d0j121J0z1j0M0U0*150b0w0v0t0:0H011O1y010l0%0D0t0v0C0D1I1:1=1`1Q1}1M20220^0a0s0G0z0d0w0d0b0P180t0s0Z1.0z0z0D0i2n1b250t1j0o1,2A0M1*1)1+0j270:1E0t1 2k1I1t1v0+1P2K0P2M0t1$1u1I0w2t1j2y2A2(0{1;2o2S1{2X0z0 0q0^0s0A2x2,0_2+262.1Q2:2=2@0H2`1=2|2y2J01310v2?040s0c352z0`382 0:3b3d0s0J3h372,393n2@0T3r3j3t3l3a0d2;3c2@0X3y2}2-1x303D323e0u3I3k3L3m3N3F3e0f3R3A3T3C3E3o0Q3Z2~3#3v040A0p3*3K2T3$3O0A2_1c2{3z3+3?3-0A343{363}3=2/3V3d0A3g433i3J3u480^0A3q4c2A2#0D2A2Q2D0j2H390i1$231j4p1m2$3J2)2{054u0Z2%3!3 0^0l0v2v3D0P3c3r0s4e3B0d0^0I4R4T3#0@040S3r4Z3?0C0P4h4(3S3?4#0R3y0645390O0^0Z0l4.4I1{0N2@4~3~2/0l0^200z0v0r1=0v53461Q4#0F5e3u575j3B4#0E4Y4/2/0^0O5m4!0^0W0K3y0s5B4S5r300^0P5q4 1Q4V044X4k5D5J3m0h0^2a5v4:0^5i4k4)5s044L4N0z4P0q5V1{4#0W5A5C5!1Q4`040N1A1M5I545F041a5O5=0:5L020n0M0g5N2(5P5}3m5G5,5g0^5z4k065C6l6b5f6d5$0e5H615E634W5|6o3a4K4M0M4O4Q5Z6u014#4%6F5Q6z046s6a62015L0B6x394+4-6K6c6H0^4=6t6L5L0V6U3B0t6e6j6m5;6G6-5$6B6D5+6Y6y5L0y6f6p0v0w0w1 0j6 6!045Y2*6=4K6r765.5:6:6Q6?6O2{6n395L0L697l6Q6W3.7g7m3B5@2t0M0k0z606P6G5h7v6l6Q7G6{5k6@5(5*7e0^6J7a6L6?7D4D7F6#6+3#5L0o0o7!4J7N6C5)6E7T6Z6I766?5u7L5n7Z6%6Z7$7(7{6y6?5%7,7P7^5w4$7=5l7 7n0^6T8a6,5t7Q040R5/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^0L8}8Y8E8k2(6k8m6Q7}8}7V7v7J5x3I0o4F4n1k4A0o4y2B4r1b2E2D1#1%2D0v1L9l9o1u2|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)