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:pbv(40i2+edm3;s7= 1o5w_lSnatf-)9h]6,crg.*[yPku8/050m0l0D0C0i0z0q0t0M0z0C0q0q0s010D0i0c010406050q0V0n0n0C0N0S040A0v0z0V0=0v0B050X0|0~10120`0c041b1i051l0X1l1n1i0`0m0i0e0*0,0.0:0I0i0O0I0z1B0I0D0^050#0d0z0l1w0-0/011A1C1E1C0D1K1M1I0D0d0v0m121J0N1j0D0I0*150q0c0C0B0:0j011O1y010E0%0l0B0C0n0l1I1:1=1`1Q1}1M20220^0a0t0T0N0v0c0v0q0i180B0t0Z1.0N0N0l0M2n1b250B1j0X1,2A0D1*1)1+0m270:1E0B1 2k1I1t1v0+1P2K0i2M0B1$1u1I0c2t1j2y2A2(0{1;2o2S1{2X0N0 0z0^0t0u2x2,0_2+262.1Q2:2=2@0j2`1=2|2y2J01310C2?040t0o352z0`382 0:3b3d0t0g3h372,393n2@0w3r3j3t3l3a0v2;3c2@0K3y2}2-1x303D323e0r3I3k3L3m3N3F3e0W3R3A3T3C3E3o0H3Z2~3#3v040u0h3*3K2T3$3O0u2_1c2{1k2$1b2Q2D0m2H390M1$231j401m3~2*3{3605450Z2%3!3?0B0^0q0M0I2h0Z0N0y220n3r0t3J390v0^0s4w4y3B0@040R3r4E3#0n0i0^3`2*3S3?4G0L4D4R1{4M0^344d2z4K4S0^0J3y063z3+3?0U0^0Z0E4J4W1Q0x2@4@4j2/0E4m4o4q0l0N4|4.1{4G0f553=2/0^1a4#4i561Q4G0G0b3y0t5n4x4^0:4:040i4?5f5p4}305d4V5y0:4A04020O0D0p4C5w4%2/0d0^2a5a39585R3B4l044n4p464s4u5U3#5j5l5f065o5-5x5h3m0^2t0|0z0#0D5B5:015E5K2(5/5b5i0^0f595f5M1Q4Y043H5L5q5}0^0Q5{625;045e60685D0^0F6i396a3g676e5j6s3B5E6h6d5C3a505Z4r5%4(04664Q6E5W6m2{614z6q6z4L4N3.6J570^0G6V3?5E6r6D5|5T6w6O5A6+6j6f046*6n6e6a4!6N6,6#6%1{6B705z5X515!6Z636L786k6Q366S6A6U6;6t6X6|3|6x6#6$7i7g040X0X730:6-2(5,5.7A6o6F6l7v6?0k7F6a4P2{7z7B7n047p7y7A5n7C0M0u0^030t0i0M0i0t5Y525#0l0n0t0l0q0D2p1N0z190O0V0l0V0N0t2o0O101=0=5m7S7C5W7(5!4t7+7b6?0P8b5W0C0c0c1 0m8b7x7m6/045?0V5^0C5`6.6~7P837T6e5s2t0D7{7d2z7f3,6G7)894v8v6=4G4I8N3u6:6}8O4)3I0X4g0l2A2#8!3 1u412D2F2B1#1%2D0C1L8%0X400`8@0!0$0(04.