пути в $n\times n$ сетка

Question

Учитывая $n\times n$квадратная сетка. Допустим, можно двигаться только вверх или вправо. Сколько путей от левого нижнего угла до правого верхнего угла, которые не пересекают диагональ квадрата, идущего от левого нижнего угла к правому верхнему углу, кроме начала и конца? .

Answer 1

Позволять $a_n$ представляют собой сумму путей, которые вы можете пройти $n\times n$сетка только с помощью движений вверх и вправо перемещается из нижнего левого угла, чтобы попасть в верхний правый, не пересекая главную диагональ, а касаясь ее только на некоторых путях. Взглянув на первые несколько случаев, мы видим, что$$a_1=1, a_2=2, a_3=5, a_4=11, a_5=21, a_6=36$$

Глядя на разницу последовательных терминов, мы обнаруживаем, что возникает знакомая закономерность: $$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 $$

Видно, что $$a_{n+1}=a_n+\frac{n(n+1)}{2}$$ с участием $a_1=1$ или, если вы хотите посчитать $a_0=1$, $$a_n=a_{n-1}+\frac{n(n-1)}{2} $$