Pfade in einem $n\times n$ Gitter

Question

Gegeben ein $n\times n$quadratisches Gitter. Angenommen, es ist nur erlaubt, sich nach oben oder rechts zu bewegen. Wie viele Pfade gibt es von der unteren linken Ecke zur oberen rechten Ecke, die nicht die Diagonale des Quadrats kreuzen, das von der unteren linken Ecke zur oberen rechten Ecke verläuft, erwarten Sie am Anfang und am Ende .

Answer 1

Lassen $a_n$ Stellen Sie die Summe der Pfade dar, die Sie auf einem nehmen können $n\times n$Das Gitter, das nur nach oben und rechts verwendet wird, bewegt sich von der unteren linken Ecke nach oben rechts, ohne die Hauptdiagonale zu überschreiten, und berührt es nur auf einigen Pfaden. Wenn wir uns die ersten Fälle ansehen, sehen wir das$$a_1=1, a_2=2, a_3=5, a_4=11, a_5=21, a_6=36$$

Wenn wir den Unterschied aufeinanderfolgender Begriffe betrachten, stellen wir fest, dass ein bekanntes Muster auftritt: $$a_2-a_1=1 $$ $$a_3-a_2=3=1+2$$ $$a_4-a_3=6=1+2+3$$ $$a_5-a_4=10=1+2+3+4$$ $$a_6-a_5=15=1+2+3+4+5 $$

Das kann man sehen $$a_{n+1}=a_n+\frac{n(n+1)}{2}$$ mit $a_1=1$ oder wenn du zählen willst $a_0=1$, $$a_n=a_{n-1}+\frac{n(n-1)}{2} $$