Em xin thử một hướng tiếp cận để đi đến công thức tổng quát cho số cách đi từ $\left(0,0\right)$ đến $\left(n,n\right)$.
Gọi số bước từ $\left(x,y\right)$ đến $\left(x + 1,y\right)$ là $a$; số bước từ $\left(x,y\right)$ đến $\left(x,y+1\right)$ là $b$; số bước từ $\left(x,y\right)$ đến $\left(x+2,y+1\right)$ là $c$.
Khi đó, ta có $a + 2c = b + c = n\Rightarrow b = a+c$
$\Rightarrow a+b+c=2b$.
Ngoài ra, với mỗi $a,b,c$ ta có số cách di chuyển là $\frac{\left(a+b+c\right)!}{a!b!c!}$.
Do đó, số cách đi từ $\left(0,0\right)$ đến $\left(n,n\right)$ là $$u_n = \sum_{b = \left\lceil n/2\right\rceil}^{n}\frac{\left(2b\right)!}{\left(2b-n\right)!b!\left(n-b\right)!} = \sum_{b = \left\lceil n/2\right\rceil }^n\binom{n}{b}\binom{2b}{n}$$
Tuy nhiên, khai triển ta thấy $\left[\left(x+1\right)^2+1\right]^n = \sum_{k = 0}^n \binom{n}{k}\left(x+1\right)^{2k}$.
Như vậy, $u_n$ thực chất là hệ số của $x^n$ trong đa thức $\left[\left(x + 1\right)^2 + 1\right]^n = \left(x + i + 1\right)^n\left(x + 1 - i\right)^n$
$\Rightarrow u_n = \sum_{k=0}^n \left(i+1\right)^k \left(1 - i\right)^{n - k} \binom{n}{k}^2 = \left(1-i\right)^n \sum_{k=0}^n i^k\binom{n}{k}^2$.
Mặt khác, ta chứng minh được (tham khảo ở đây) $$P_n\left(\frac{z+1}{z-1}\right) = \frac{1}{\left(z-1\right)^n}\sum_{k=0}^n z^k\binom{n}{k}^2$$
với $P_n\left(x\right)$ là đa thức Legendre thứ $n$.
Dẫn đến $u_n =\left(-1\right)^n\left(1-i\right)^{2n}P_n\left(\frac{i+1}{i-1}\right) =\left(2i\right)^nP_n\left(-i\right)$.
Ta lại có công thức truy hồi $$\begin{cases} P_0\left(x\right) = 1, P_1\left(x\right) = x \\ \left(n+1\right)P_{n+1}\left(x\right) = \left(2n+1\right)xP_n\left(x\right) - nP_{n-1}\left(x\right)\end{cases}$$
Như vậy, dễ dàng thu được $$\begin{cases} u_0 = 1,u_1 = 2 \\ \left(n+1\right)u_{n+1} = 2\left(2n+1\right)u_n + 4nu_{n-1}\end{cases}$$
Ta tính được các số hạng đầu là $1,2,8,32,136,592,2624,11776$.
Tuy nhiên, công thức trên vẫn mất $O\left(n\right)$ thời gian khi tính $u_n$ cụ thể nào đó.
Hy vọng mọi người sẽ có sự cải tiến nào đó.