Aller au contenu

Énumération des chemins de Schröder

Dans une grille, on souhaite compter tous les chemins allant de \((0, 0)\) à \((2n, 0)\), en restant au-dessus ou sur l'axe des abscisses, et avec les mouvements possibles suivants :

  • Nord-Est (↗), donc suivi plus tard d'un Sud-Est (↘)
  • Sud-Est (↘), qui est donc précédé d'un Nord-Est (↗) correspondant
  • Deux fois de suite à l'Est (→→)

Chaque paire (↗, ↘) est associée à un déplacement de deux unités vers l'Est. Ainsi, un chemin de Schröder fait globalement un déplacement horizontal d'un nombre pair d'unités, que l'on note \(2n\).

Chemins de Schröder de longueur \(2×2\)

Il y en a 6.

Chemins de Schröder de longueur \(2×3\)

Il y en a 22.

Exercice

Coder une fonction schroder qui prend un entier positif n en paramètre et qui renvoie le nombre de chemins de Schröder allant de \((0, 0)\) à \((2n, 0)\) à l'aide des trois déplacements proposés ↗, ↘, →→. La fonction complète, si besoin, la liste des résultats mémorisés schroder_mem.

On admettra qu'une relation pour calculer ces nombres \(S_n\) est :

  • \(S_0 = 1\), \(S_1 = 2\)
  • \((n+1)S_n = (6n-3)S_{n-1} - (n-2)S_{n-2}\), pour \(n>1\).
Contraintes
  • \(n < 10^3\)
  • 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 : ∞/∞
.128013],59/f.78rnb _o=ylaepcwgu)*vd461`3kRömhtsP(S0+2Cè[-i:050D0u0O0t0!0s0P0n0w0s0t0P0P0q010O0!0v010406050P0z0M0M0t0k0r040S0p0s0z0_0p0l050f101214160~0v04051m1f1p0f1m0~0D0!0C0.0:0=0@0N0!0y0N0s1D0N0O0|050)0m0s0u1y0;0?011C1E1G1E0O1M1O1K0O0k1n0O0N1Q1A010g0+0u0l0t0M0u010.190P0v0t0l0@0V1K1{1}1+1S1.1O1;1?0|0a0n0Q0k0p0v0p0P0!1c0l0n0%1_0k0k0u0w2k1f220l1n0f1)2x1$1(1%1L0D240@1G0l1:2h1K1v1x0/1R2H0!2J0l0p2N1K0v2q1n2v2x2#0 1|2l2P1,2U0k130s0|0n0G2u2)0}2(232+1S2-2/2;0V2@1}2_2v2G012~0t2:040n0I322w0~352|0@383a0n0E3e342)363k2;0d3o3g3q3i370p2.392;0F3v2`2*1z2}3A2 3b0i3F3h3I3j3K3C3b0j3O3x3Q3z3B3l0e3W2{3Y3s040G0T3%3H2Q3Z3L0G2?1g2^3w3(3:3*0G313^333`3/2,3S3a0G3d402w1q2Z1f2N2A0D1(2F3y0w2V1@1n4e1o4c2%491n4k0%2!3X3|0|0P0w0N2e0%0k0o1?0M3o0n3G360p0|0q4J4L3y0{040Y3o4R3Y0M0!0|3@2%3P3:4T0c4Q4(1,4Z0|3 4%4x1,4T0b3v42360J0|0%0g4W4-1S0x2;514?2}0g4z4B4D0u0k563{4@0|0R5f432}0|1e4s4X4)0|0A0#3.36543b0n5z5k360P0D0|015G5v3y5D2;5z0n0W0p0M0v0s0X0O0u0c0n2i0n0m0u0P0p2S5W0:0n1G0P5U0n0H4A4C4l4F4H0H5I3Y5K5y5z0K1:0C5%1P5;5c5@0u0M0Y0l0b0n0#5+1P2U0M0m2q2m1P0S5b0L4E2m002S1v0w6f5`3:5|5M0n5G013v6z5q1,4}040g3A4,573j0|0!6L5g1S0p5x2S6Q5l3j0m0|0k1}0y0u5B4S5i6)3)6Z04276,5r045j5p526N04645?4G676;5h040A4+4s4K6_375n6W4M0|0U7a3y4/3+701S4T5t6D6z5M6F5m040D2e2j6(757p0@4N044P7w774T6@4=6R6`6P7C6M017z0Z7e4Y4!044;2^7x017k7P3:7z0B7Y2,5a5=4E6~4I6^7L4T4V7-7H78047J2#767L7N7$1S7g7T337V4^7m7n7`7=0l0|0y0t0z4B7v7_7V7z7B8f7D6+7;6X017g3E7K7=7!7}7I8u7M0|7O8r8n7g487G8n7X8A7b047#8H3y886{5b6}4H7i0@7/8S7?7^2^868n7|8L7Q4#8V834s06855A778N0S0o8X338Z8I8i8Y828l8E3r898b8d8w8#8j7L8N7s5%5U8)5s930|0f0f8w7E8V8N8?2w8^3y7z7d8$3:7g4$7U8k72847n7V8N6|7*8R8m8I0h9j0|0t0v0v1:0D9b6?9I178=9P0A9y7V6H2q0O0z0k5o95877(657+9P7:8~8M799F6*044_8+1f4u0u2x2Y9|4d1w4f2A2D2y0t1N9 0f4e0~a90(0*0,04.