Chủ đề này có 5 trả lời

[Nobodyv3]

Xét các cách đi khác nhau trên lưới ô vuông đơn vị với các loại bước như sau:
a) bước 1 đơn vị về phía phải : từ (x,y) đến (x+1,y)
b) bước 1 đơn vị lên trên: từ (x,y) đến (x,y+1)
c) bước "quân mã": từ (x,y) đến (x+2,y+1)
Với các loại bước này, hỏi có bao nhiêu cách đi khác nhau từ (0,0) đến (7,7).
========
Xin sửa đề một tí xem có thú vị hơn không...

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 23-12-2023 - 17:04

[Nobodyv3]

Giải :
Ta "mã hóa đại số" các bước cơ bản như sau :
- Từ $(x,y)$ đến $ (x+1,y)$ là $x$
- Từ $(x,y)$ đến $ (x,y+1)$ là $y$
- Từ $(x,y)$ đến $ (x+2,y+1)$ là $x^2y$
Từ đó, ta lập được hàm sinh
$G(x,y)=\sum_{r=0}^{\infty }\left ( x+y+x^2y \right )^r$ với $r\geq 0$
và từ đây, ta tính được số đường đi thỏa yêu cầu như sau :
$$\begin{align*}
\left [ x^7y^7 \right ]G(x,y)&=\left [ x^7y^7 \right ]
\sum_{r=0}^{\infty }\left ( x+y+x^2y \right )^r\\
&=\left [ x^7y^7 \right ]\sum_{r=0}^{\infty }\sum_{{ a,b,c\geq 0\atop a+b+c=r}}\binom{r}{a,b,c} x^ay^b\left ( x^2y \right )^c\\
&=\left [ x^7y^7 \right ]\sum_{r=0}^{\infty }\sum_{{ a,b,c\geq 0\atop a+b+c=r}}\binom{r}{a,b,c} x^{a+2c}y^{b+c}\\
&=\left [ x^7 \right ]\sum_{r=0}^{\infty }\sum_{b=0}^{7}\sum_{{ a\geq 0\atop a+b+(7-b)=r}}\binom{r}{a,b,7-b} x^{a+14-2b}\\
&=\left [ x^7 \right ]\sum_{r=0}^{\infty }\sum_{b=4}^{7}\binom{r}{r-7,b,7-b} x^{r+7-2b}\\
&=\binom{8}{1,4,3}+\binom{10}{3,5,2}+\binom{12}{5,6,1}+\binom{14}{7,7,0}\\
&=\frac{8!}{1!4!3!}+\frac {10!}{3!5!2!}+\frac {12!}{5!6!1!}+\frac {14!}{7!7!0!}\\
&=\boldsymbol {11776}
\end{align*}$$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 23-12-2023 - 21:08

[hxthanh]

Tuyệt quá đi! Không cần học nhiều, chỉ cần tìm đọc các bài viết của @Nobodyv3 là đủ

[DOTOANNANG]

Tuyệt quá đi! Không cần học nhiều, chỉ cần tìm đọc các bài viết của @Nobodyv3 là đủ

Em cũng đồng ý hai tay luôn.

[Hoang72]

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 đó.

[hxthanh]

Lời giải của @Hoang72 rất hay và gợi mở rất nhiều thứ. Một nỗ lực rất đáng khâm phục!

Nói về dãy $(u_n)_{n\ge 0}:\, 1,2, 8, 32, 136, 592, ...$ thì dãy này xuất hiện trong OEIS là dãy A006139

Trong này cũng mô tả đầy đủ các dạng của $u_n$ (có đoạn của cả hai bài làm trên)

Bên cạnh đó cũng có một đánh giá vô cùng tốt cho $u_n$ của Vaclav Kotesovec là:

$$u_n \sim \dfrac{2^{n-3/4} (1+\sqrt 2)^{n+1/2}}{\sqrt{\pi n}}$$