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
.128013s3o_8;bcdufvg/0ly n7apS.r1-me,(P2=4:+twki9][5h*)6050j0D0M0v0P0q0b0s0i0q0v0b0b0I010M0P0w010406050b0k0C0C0v0z0r040x0d0q0k0=0d0t050o0|0~10120`0w041b1i051l0o1l1n1i0`0j0P0m0*0,0.0:0U0P0n0U0q1B0U0M0^050#0h0q0D1w0-0/011A1C1E1C0M1K1M1I0M0h0d0j121J0z1j0M0U0*150b0w0v0t0:0H011O1y010l0%0D0t0v0C0D1I1:1=1`1Q1}1M20220^0a0s0G0z0d0w0d0b0P180t0s0Z1.0z0z0D0i2n1b250t1j0o1,2A0M1*1)1+0j270:1E0t1 2k1I1t1v0+1P2K0P2M0t1$1u1I0w2t1j2y2A2(0{1;2o2S1{2X0z0 0q0^0s0A2x2,0_2+262.1Q2:2=2@0H2`1=2|2y2J01310v2?040s0c352z0`382 0:3b3d0s0J3h372,393n2@0T3r3j3t3l3a0d2;3c2@0X3y2}2-1x303D323e0u3I3k3L3m3N3F3e0f3R3A3T3C3E3o0Q3Z2~3#3v040A0p3*3K2T3$3O0A2_1c2{1k2$1b2Q2D0j2H390i1$231j401m3~2*3{3605450Z2%3!3?0t0^0b0i0U2h0Z0z0e220C3r0s3J390d0^0I4w4y3B0@040S3r4E3#0C0P0^3`2*3S3?4G0E4D4R1{4M0^344d2z4K4S0^0R3y063z3+3?0O0^0Z0l4J4W1Q0N2@4@4j2/0l4m4o4q0D0z4|4.1{4G0F553=2/0^1a4#4i561Q4G0W0K3y0s5n4x4^0:4:040P4?5f5p4}305d4V5y0:4A04020n0M0g4C5w4%2/0h0^2a5a39585R3B4l044n4p464s4u5U3#5j5l5f065o5-5x5h3m0^2t0|0q0#0M5B5:015E5K2(5/5b5i0^0F595f5M1Q4Y043H5L5q5}0^0V5{625;045e60685D0^0B6i396a3g676e5j6s3B5E6h6d5C3a505Z4r5%4(04664Q6E5W6m2{614z6q6z4L4N3.6J570^0W6V3?5E6r6D5|5T6w6O5A6+6j6f046*6n6e6a4!6N6,6#6%1{6B705z5X515!6Z636L786k6Q366S6A6U6;6t6X6|3|6x6#6$7i7g040o0o730:6-2(5,5.7A6o6F6l7v6?0L7F6a4P2{7z7B7n047p7y7A5n7C0i0A0^030s0P0i0P0s5Y525#0D0C0s0D0b0M2p1N0q190n0k0D0k0z0s2o0n101=0=5m7S7C5W7(5!4t7+7b6?0y8b5W0v0w0w1 0j8b7x7m6/045?0k5^0v5`6.6~7P837T6e5s2t0M7{7d2z7f3,6G7)894v8v6=4G4I8N3u6:6}8O4)3I0o4g0D2A2#8!3 1u412D2F2B1#1%2D0v1L8%0o400`8@0!0$0(04.