É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\).

Objectif : Écrire une fonction telle que schroder(n) renvoie le nombre de chemins de Schröder allant de \((0, 0)\) à \((2n, 0)\).

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.

Formule

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\).
Exemples 
>>> schroder(2)
6
>>> schroder(3)
22
>>> schroder(4)
90

Compléter le code :

⚠ La fonction doit renvoyer un nombre entier.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
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 : 5/5
.128013[(lbsS]et-ph4rd;5.f1890uma"ov+7g,_/3=in 6k:)y *2Pc030j0c0d0u0G07090O0S070u09090F0v0d0G0f0v020I03090s0t0t0u0i0N020a0w070s0,0w0H030D0?0^0`0|0;0f02031c151f0D1c0;0j0G0x0#0%0(0*0g0G0A0g071t0g0d0/030W08070c1o0'0)0v1s1u1w1u0d1C1E1A0d0i1d0d0g0#0 090f0u0H0*0Q0v1G1q0v0n0Y0c0H0u0t0c1A1Z1#1)1I1,1E1/1;0/040O0R0i0w0f0w090G120H0O0U1X0i0i0c0S29151@0H1d0D1V2m1S1U1T1B0j1_0*1w0H1.261A1l1n0$1H2w0G2y0H0w2C1A0f2f1d2k2m2Q0=1!2a2E1*2J0i0_070/0O0o2j2U0:2T1^2W1I2Y2!2$0Q2(1#2*2k2v0v2/0u2#020O0E2?2l0;2_2-0*2|2~0O0h322^2U2`382$0l3c343e362{0w2Z2}2$0J3j2+2V1p2.3o2:2 0z3t353w373y3q2 0p3C3l3E3n3p390q3K2,3M3g020o0r3R3v2F3N3z0o2'162)1g2O152C2p0j1U2u3m0S2K1=1d3-1e3+2S3(2@033?0U2P3L3!0H0/090S0g230U0i0C1;0t3c0O3u2`0w0/0F4h4j3m0.02053c4p3M0t0G0/3'2S3D3!4r0B4o4C1*4x0/2=3~2l4v4D0/0b3j0I3k3S3!0K0/0U0n4G442X0n47494b0c0i4u4H1I4r064-4$2.0/144M434V1*4r0M0L3j0O524i4.0*4X020G4!4`544?374^4#4|1I4l02000A0d0k4n5b4O2X080/1|4=5h0*4:5w3Z2X4(4a3@4d4f5A2`4~504`0I535O5c5x2{0/2f0?070W0d5g5B5i4m5Z5J0/064;4`5r1I4J023s5q550v5j0P5%3m46024_2Q5Q5!0*5j0e5_4w4y02315+5=4~643!5@6c5C02485E4c5I4q5(6l3T5f5;5d5?0/636r5R5.4A3)6a0/0M6f5#026v5~5,5y6n696s5{5}2)5 4k6u6E0*5.4L4B6s6b6w606t025^6#3f5D4*4,6M5R5z6.6$6O6U6%6H6Q6J0v6W6o4P020M6D6)3m5j0D0D6@6:2Q5N5P7c6{6?733M5j0y6@6y517c6R6m707m7d5=0S0o0/010O0G0S0G0O6i6,4e0c0t0O0c090d2b1F07130A0s0c0s0i0O2a0A0`1#0,7r5P7e6+5F7F4g6;6S020m6~6g0u0f0f1.0j7/4/6L6Y5R5{5U0s5W0u5Y7+7p727a5O6{572f0d7T6P2@7o6p6h4)7(5H843M4r4t8m456q7|6$4r4R5M15410c2m2N8A3,1m3.2p2s2n0u1D8D0D3-0;8N0V0X0Z02.