Nombres 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)
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 : 10/10
.128013ben,49vi[+3mo5_t;Phklpwf(: cg.a=ry0S6]*-u/72)s18d050X0c0q0F0i0v0U0B0C0v0F0U0U0G010q0i0w010406050U0P0m0m0F0H0I040K0n0v0P0=0n0d050Q0|0~10120`0w04051i1b1l0Q1i0`0X0i0h0*0,0.0:0t0i0D0t0v1z0t0q0^050#0b0v0c1u0-0/011y1A1C1A0q1I1K1G0q0H1j0q0t0*150U0w0F0d0:0S011M1w010y0%0c0d0F0m0c1G1)1+1:1O1?1K1_1{0^0a0B0s0H0n0w0n0U0i180d0B0Z1%0H0H0c0C2g1b1~0d1j0Q1#2t1Y1!1Z1H0X200:1C0d1^2d1G1r1t0+1N2D0i2F0d0n2J1G0w2m1j2r2t2X0{1*2h2L1;2Q0H0 0v0^0B0V2q2#0_2!1 2%1O2)2+2-0S2:1+2=2r2C012`0F2,040B0l2~2s0`312^0:34360B0f3a302#323g2-0o3k3c3m3e330n2*352-0L3r2?2$1v2_3w2{370R3B3d3E3f3G3y370W3K3t3M3v3x3h0g3S2@3U3o040V0J3Z3D2M3V3H0V2/1c2;1m2V1b2J2w0X1!2B3u0C2R1|1j3_1k3@2Z3;2 053 0Z2W3T3,0d0^0U0C0t2a0Z0H0p1{0m3k0B3C320n0^0G4q4s3u0@040j3k4y3U0m0i0^3:2Z3L3,4A0e4x4L1;4G0^2}472s4E4M0^0M3r063s3!3,0u0^0Z0y4D4Q1O0x2-4.4d2(0y4g4i4k0c0H4?4(1;4A0z4 3+2(0^1a4V4c501O4A0T0A3r0B5h4r4/0:4*040i4-595j4@2_574P5s0:4u04020D0q0r4w5q4X2(0b0^235432525L3u4f044h4j404m4o5O3U5d5f59065i5%5r5b3f0^2m0|0v0#0q5v5*015y5E2X5)555c0^0z53595G1O4S043A5F5k5@0^0N5=5|5+04585`625x0^0O6c32643961685d6m3u5y6b675w334`5T4l5X4Y04604K6y5Q6g2;5{4t6k6t4F4H3%6D510^0T6P3,5y6l6x5?5N6q6I5u6#6d69046!6h68644U6H6$6V6X1;6v6`5t5R4{5U6T5}6F726e6K2 6M6u6O6+6n6R6?3=6r6V6W7c7a040Q0Q6}0:6%2X5$5(7u6i6z6f7p6-0k7z644J2;7t7v7h047j7s7u5h7w0C0V0^030B0i0C0i0B5S4|5V0c0m0B0c0U0q2i1L0v190D0P0c0P0H0B2h0D101+0=5g7M7w5Q7Y5U4n7#756-0E855Q0F0w0w1^0X857r7g6)045-0P5/0F5;6(6^7J7}7N685m2m0q7=772s793#6A7Z834p8p6,4A4C8H3n6*6@8I4Z3B0Q4a0c2t2U8U3^1s3`2w2z2u0F1J8X0Q3_0`8+0!0$0(04.