Nombres de Schröder

Série d'exercices

Cet exercice fait partie d'une série :

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.

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 de la fonction schroder(n) qui renvoie un entier correspondant au nombre de chemins de Schröder allant de \((0, 0)\) à \((2n, 0)\).:

###(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
.128013,n w-*5e9](38m=0p)rhk[uois;cb/6.S1vt_dg:ay24P+fl7050M0i0K0P0z0W0A0d0C0W0P0A0A0p010K0z0r010406050A0x0o0o0P0t0Q040H0y0W0x0=0y0c050E0|0~10120`0r041b1i051l0E1l1n1i0`0M0z0J0*0,0.0:0u0z0N0u0W1B0u0K0^050#0D0W0i1w0-0/011A1C1E1C0K1K1M1I0K0D0y0M121J0t1j0K0u0*150A0r0P0c0:0R011O1y010V0%0i0c0P0o0i1I1:1=1`1Q1}1M20220^0a0d0T0t0y0r0y0A0z180c0d0Z1.0t0t0i0C2n1b250c1j0E1,2A0K1*1)1+0M270:1E0c1 2k1I1t1v0+1P2K0z2M0c1$1u1I0r2t1j2y2A2(0{1;2o2S1{2X0t0 0W0^0d0I2x2,0_2+262.1Q2:2=2@0R2`1=2|2y2J01310P2?040d0m352z0`382 0:3b3d0d0S3h372,393n2@0h3r3j3t3l3a0y2;3c2@0F3y2}2-1x303D323e0X3I3k3L3m3N3F3e0n3R3A3T3C3E3o0j3Z2~3#3v040I0q3*3K2T3$3O0I2_1c2{1k2$1b2Q2D0M2H390C1$231j401m3~2*3{3605450Z2%3!3?0c0^0A0C0u2h0Z0t0L220o3r0d3J390y0^0p4w4y3B0@040w3r4E3#0o0z0^3`2*3S3?4G0b4D4R1{4M0^344d2z4K4S0^0k3y063z3+3?0v0^0Z0V4J4W1Q0e2@4@4j2/0V4m4o4q0i0t4|4.1{4G0l553=2/0^1a4#4i561Q4G0s0O3y0d5n4x4^0:4:040z4?5f5p4}305d4V5y0:4A04020N0K0B4C5w4%2/0D0^2a5a39585R3B4l044n4p464s4u5U3#5j5l5f065o5-5x5h3m0^2t0|0W0#0K5B5:015E5K2(5/5b5i0^0l595f5M1Q4Y043H5L5q5}0^0g5{625;045e60685D0^0f6i396a3g676e5j6s3B5E6h6d5C3a505Z4r5%4(04664Q6E5W6m2{614z6q6z4L4N3.6J570^0s6V3?5E6r6D5|5T6w6O5A6+6j6f046*6n6e6a4!6N6,6#6%1{6B705z5X515!6Z636L786k6Q366S6A6U6;6t6X6|3|6x6#6$7i7g040E0E730:6-2(5,5.7A6o6F6l7v6?0U7F6a4P2{7z7B7n047p7y7A5n7C0C0I0^030d0z0C0z0d5Y525#0i0o0d0i0A0K2p1N0W190N0x0i0x0t0d2o0N101=0=5m7S7C5W7(5!4t7+7b6?0G8b5W0P0r0r1 0M8b7x7m6/045?0x5^0P5`6.6~7P837T6e5s2t0K7{7d2z7f3,6G7)894v8v6=4G4I8N3u6:6}8O4)3I0E4g0i2A2#8!3 1u412D2F2B1#1%2D0P1L8%0E400`8@0!0$0(04.