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
.12801342ny6g3p )rPv1-=;oa_ckmi*u5(,e:ts]Shl970[wbf8+./d050X0E0G0t0y0L0H0j0v0L0t0H0H0q010G0y0i010406050H0A0x0x0t0l0e040J0s0L0A0=0s0d050W0|0~10120`0i041b1i051l0W1l1n1i0`0X0y0n0*0,0.0:0K0y0g0K0L1B0K0G0^050#0R0L0E1w0-0/011A1C1E1C0G1K1M1I0G0R0s0X121J0l1j0G0K0*150H0i0t0d0:0c011O1y010S0%0E0d0t0x0E1I1:1=1`1Q1}1M20220^0a0j0m0l0s0i0s0H0y180d0j0Z1.0l0l0E0v2n1b250d1j0W1,2A0G1*1)1+0X270:1E0d1 2k1I1t1v0+1P2K0y2M0d1$1u1I0i2t1j2y2A2(0{1;2o2S1{2X0l0 0L0^0j0o2x2,0_2+262.1Q2:2=2@0c2`1=2|2y2J01310t2?040j0h352z0`382 0:3b3d0j0b3h372,393n2@0B3r3j3t3l3a0s2;3c2@0f3y2}2-1x303D323e0N3I3k3L3m3N3F3e0T3R3A3T3C3E3o0M3Z2~3#3v040o0O3*3K2T3$3O0o2_1c2{1k2$1b2Q2D0X2H390v1$231j401m3~2*3{3605450Z2%3!3?0d0^0H0v0K2h0Z0l0u220x3r0j3J390s0^0q4w4y3B0@040P3r4E3#0x0y0^3`2*3S3?4G0D4D4R1{4M0^344d2z4K4S0^0I3y063z3+3?0w0^0Z0S4J4W1Q0Q2@4@4j2/0S4m4o4q0E0l4|4.1{4G0C553=2/0^1a4#4i561Q4G0k0F3y0j5n4x4^0:4:040y4?5f5p4}305d4V5y0:4A04020g0G0r4C5w4%2/0R0^2a5a39585R3B4l044n4p464s4u5U3#5j5l5f065o5-5x5h3m0^2t0|0L0#0G5B5:015E5K2(5/5b5i0^0C595f5M1Q4Y043H5L5q5}0^0z5{625;045e60685D0^0p6i396a3g676e5j6s3B5E6h6d5C3a505Z4r5%4(04664Q6E5W6m2{614z6q6z4L4N3.6J570^0k6V3?5E6r6D5|5T6w6O5A6+6j6f046*6n6e6a4!6N6,6#6%1{6B705z5X515!6Z636L786k6Q366S6A6U6;6t6X6|3|6x6#6$7i7g040W0W730:6-2(5,5.7A6o6F6l7v6?0U7F6a4P2{7z7B7n047p7y7A5n7C0v0o0^030j0y0v0y0j5Y525#0E0x0j0E0H0G2p1N0L190g0A0E0A0l0j2o0g101=0=5m7S7C5W7(5!4t7+7b6?0V8b5W0t0i0i1 0X8b7x7m6/045?0A5^0t5`6.6~7P837T6e5s2t0G7{7d2z7f3,6G7)894v8v6=4G4I8N3u6:6}8O4)3I0W4g0E2A2#8!3 1u412D2F2B1#1%2D0t1L8%0W400`8@0!0$0(04.