Aller au contenu

Énumération des chemins dans une grande grille

Dans une grande grille de taille \(n×m\), on souhaite compter tous les chemins allant du coin inférieur gauche (au Sud-Ouest) vers le coin supérieur droit (au Nord-Est).

⚠ Dans cet exercice, on pourra avoir \(0\leqslant n \leqslant 1000\) et \(0\leqslant m \leqslant 1000\).

Les seuls mouvements autorisés sont :

  • ↑ Aller au Nord d'une unité.
  • → Aller à l'Est d'une unité.

Les chemins pour aller de \((0, 0)\) à \((4, 3)\)

Il y en a 35.

Exercice

Coder une fonction nb_chemins qui prend deux entiers positifs n et m en paramètres et renvoie le nombre de chemins allant de \((0, 0)\) jusqu'à \((n, m)\) avec deux types de mouvements autorisés (→ et ↑).

👍 Pour ce faire, on admettra que nb_chemins(n, m) est égal à \(\binom{n}{n+m}\).

\[\binom{n}{n+m} = \dfrac{(n+m)!}{n!m!}\]

Où :

  • \(n! = 1×2×3×\cdots×(n-1)×n\)
  • \(m! = 1×2×3×\cdots×(m-1)×m\)
  • \((n+m)! = 1×2×3×\cdots×(n+m-1)×(n+m)\)

On vous décrit, plus bas, comment simplifier cette expression.

Contraintes
  • \(0 \leqslant n < 1024\)
  • \(0 \leqslant m < 1024\)
  • Fonction récursive interdite
  • Modules math et functools interdits
  • Code source limité à 2000 caractères

Utilisation pour nb_chemins(4, 3)

  • \(4! = 1×2×3×4\)
  • \(3! = 1×2×3\)
  • \((4+3)! = 1×2×3×4×5×6×7\)
\[\binom{4}{4+3} = \dfrac{1×2×3×4×5×6×7}{1×2×3×4~×~1×2×3}\]
\[\binom{4}{4+3} = \dfrac{5×6×7}{1×2×3} = 35\]

Utilisation pour nb_chemins(n, m)

  • \(n! = 1×2×3×\cdots×n\)
  • \(m! = 1×2×3×\cdots×m\)
  • \((n+m)! = 1×2×3×\cdots×(n+m) = 1×2×3×\cdots×n×(n+1)×\cdots×(n+m)\)
\[\binom{n}{n+m} = \dfrac{1×2×3×\cdots×(n+m)}{1×2×3×\cdots×n~×~1×2×3\cdots×m}\]
\[\binom{n}{n+m} = \dfrac{\xcancel{(1×2×3×\cdots×n)}~×~(n+1)×\cdots×(n+m)}{\xcancel{1×2×3×\cdots×n}~×~1×2×3×\cdots×m}\]

En conclusion

On déduit la formule simple, à utiliser ici :

nb_chemins(n, m) est égal à \(\dfrac{(n+1)×(n+2)×(n+3)×\cdots×(n+m)}{1×2×3×\cdots×m}\)

```

###(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 : ∞/∞
.8593.128203.128013.8594x/.Tr;nbOylaeê%u)*dJçm(P+0è-U],fq!} N_o=${pcgv`1kRIéhtsSàCD[ji:E050w0q0)0p0;0o0*0N0V0o0p0*0*0R010)0;0U010406050*0t0z0z0p0i0n040+0Q0o0t170Q0k050f1e1g1i1k1c0U04051A1t1D0f1A1z040Y1K0U0n0)0(1r0N170)0o0q150c0N0B0i0Q0U0Q0*0;1q0k0N0^0 0Q0i0i0q0V1*010N0o0;0k0q0k1f14010Z01060^0J0N0k0l0P0V0(0q0z1{0*0A0k0I0N0z0u0=060N2p0N010#1}0X0Q0;0q1_2y0k0Q0z0l1;1,2y2b2d2f0N0p0o110k0)2G0N0A0D2j0D0u0N0,2S2i2k2X0p0X1=0N0d0N0Q0t0N0a232q271f0%0i0p0)0q0t0i0N0R0N0Z2o2q0J1/0N0;381+2`0k0W0q2h0N0C322j1+3i0z3h322m342?2p1~0z2_2{2}2 0v310;1E1b0@0;0X0 1113150(0;0W0(1`3O0)1a1d0U0p1+1012200J0|1}0p0z0q1a0b0N0h0q0e2|1t0*3V0k1B0U1;1B3?3W1B1u3@1B0V0Q0^040w0%2B2e0k3x2~303206362 391{0N3c3e0A0Z2j3n3i0Z3q2?47491{4c3z3B06061;0)2~1+3u3w2|4d0f0f1,482C4y4K0i1c0f43451E3{1t0w3G3E1A1K0Y3D4U0^0`0|0*3E4#3H3Y3K010p0w0z1r1)0;1Q2B2|1a1z3I3Z154`4|0k4~1r0F1S1U1a1Z440t1)0N0X0;1-0q0*2Q0%0W2M2Y324+1C040B2.2 0V2M0V0t1U2 0t1+3`5i1)2j1Q1{4~2M0;0*2y1U0N5L0w5j2Q2Z4p0N0_271Q2Z0D0g5x5G3E1`040G1|0N0*2C3)5l5n2y5p5r5t5W5,5.0f5=1c5=5@5X1!5Z5k5m5o5q0N5s5u5$65671t5:4,4$1c4=554^584}1*3a36531C6u206w5a1*5d1)5f040m0U4J3y0~1}0F0U110V0q5x1A5A4d110N0l2.100q5O5K2}5r0V0i0;2F0p2/2b2w0e0N0=5/0o5;0;42440q040i0%1e0o0`2Q3A0N0J0p1?3y1t4W731t6n5=057i74765G794e75777s0v7c7e4S7h72046m704U6p5y0.5V0p2k0r5|1h5a0E2F0K0t001Q0U6-6i6/6;6*2L6@1P0;0e6}6 71457u7r2{3h312|0i3)7B4X667F057m7o7:787=31827s3i7^7`4V7C7k7~0f7H1A0$0o5(0e5T2|7%13391U0~6?0)1;0~1#6O2~6Q0k6S6U6*7,68707n7C0F0R7{732j1$6!7L5`0t5q2`1?4 1s7}7-8I454M8L8b458O5B1_7L4=5T8X5(2P0;7R6W8Z8G7.730s8(7o8+6!2y4|5Z0o0Q8d8!7o0f8 7C912 6#8/1(1Q438?1~0%8_7l8H7o0v3A8M049e8-5X5j133W6V988{8#7302780j9H0)0j9c455X8,5W475D113e2R0l1)0~2Z5t0t2I9D7 9q7C020W9L9,9L9N739P924O9T0p9V1-9X0)9Z1,1!1)9o8e7H0f4=4;3G6D574{6x8;17194%aa4_ac6G8X6I1T3*040x8T173#5D6y1-6#4h0z5G2y0w1r0k9n6X8|04282a2c4a2g2#2l9u5(6h6j8j2Z3U3Wai1i1)0(1h2|0e1a090A099X490T0k0Ma:0C0z0M090u3=41651H3F4?3J6E6:1Oa%3/a*0/a-1{2Ca:a=0ka@0M4e090w0J8V0T2ha@0u0Lbe0L0zbr090H4!6r050l960V0!7T0Q2|4%6L3b0p0U7X2N2y7T2y8P5C2C0U7^2z5*2D2F1-7d0y1r0~1-6^8:2 aX3Xb257b4a$3xa)04a+0!a`a|3~6i0o0%3)2P0~3V7_39b.aZb=b6b^a+0kb|403~6+0N1p0|5T5V2H0Q0q0Jau2x2P6$bb2e5u0Sbaa/0!be0M0Ya~3E0fbB0QbDbFbH1I6a2I4a2L2N3W2Q1-c84@b3a#cba*0A2T2V0ucf3}3^0N0:8T7T00aWc,c9c!b@c$2h4qc*a{cgc-7X1p0N0r8uaC0%7!2Qc5cj5^1ea22R9F040?aR5)cW7o0OaR0j0Ndhdj8)9=bScS5H5v0o000?5q2jdhdodu049?2 2Mdy6?0N0O1/0w0g0N8i1,2w2Q0n2L2v6;drc@cYb;c_a(c$cec c,dI365T9x3`761}6Vdg7odt905(2QcXb:4_cac`b_0A0zc+417c2w0~6#d@5U0kd`dm7CdG7ocG1IdUdY7L8tcU2RcQ2KdLetcWd%e2a!b5e5a+c(0N2We9b~c/0*c;c?3@c^eDd+e6c|2$eJc-bQ2R4|9~dgeA56e3d*b7e6bfe8d.ea1U0)d60~430z1$0*76e$ePd(e)eRe+cdeWdIdsdke0e%6ve4eSa+e.b}c-dF9udS6ZbTe_bW6V0~e!0*2j0|5_0tcr5kb*bUbW5W492EaC2yb$b(eu7)1(b-f9cZf1cc2hf49P1(1*c41i2e2z0~e1e(eCb?fcbofed0dIdw6T7e0q9f5pdrd|fi0N0m3b2d1ibQ2`0NeYf!fae*fPcAbca;a?a^bia.bca^g9a_e/chd 0 fJd#8rf?ekaR0;e_1%cnfZf@dH1R2.2Qes2PdS0-bP5jc.as0;3#7Keb7_aBdV0kaF0qenby0X04.