Cho lưới hình chữ nhật $ABCD$ gồm $m\times n$ ô vuông cạnh bằng 1 (với $m,n\in {\mathbb{N}}^{\ast }$). Xét đường đi có độ dài $(m+n)$ từ $A$ đến $C$ dọc theo các đường lưới và đổi hướng đúng $k$ lần $(k\in {\mathbb{N}}^{\ast })$.

a) Tính số đường đi ứng với $m=n=4$ và $k=2$ (hình vẽ dưới đây mô tả một trong số các đường đi).



b) Tính số đường đi ứng với $m=8,n=10$ và $k=4$ (hình vẽ dưới đây mô tả một trong số các đường đi).

Vì độ dài đường đi bằng $m+n$ nên trong suốt quá trình đi từ A đến C:
- Ta chỉ được đi theo hai hướng:
- Song song với cạnh AB (đi sang phải)
- Song song với cạnh AD (đi lên trên)
- Tổng số đơn vị đi sang phải là $m$
- Tổng số đơn vị đi lên trên là $n$

Mỗi lần đổi hướng thì đường đi bị chia thành các đoạn thẳng liên tiếp. Do đổi hướng đúng $k$ lần nên toàn bộ đường đi gồm đúng $k+1$ đoạn thẳng.

a) Khi $m=n=4$ và $k=2$

Bước 1. Xác định số đoạn của đường đi
Vì đổi hướng đúng 2 lần nên đường đi gồm: $2+1=3$ đoạn thẳng
Ba đoạn này lần lượt song song với các cạnh của hình chữ nhật và hai đoạn kề nhau phải khác hướng

Bước 2. Xét các khả năng về hướng đi
Với 3 đoạn thẳng, chỉ có hai khả năng:
- Khả năng 1:
Đoạn thứ nhất song song với cạnh AB
Đoạn thứ hai song song với cạnh AD
Đoạn thứ ba song song với cạnh AB
- Khả năng 2:
Đoạn thứ nhất song song với cạnh AD
Đoạn thứ hai song song với cạnh AB
Đoạn thứ ba song song với cạnh AD

Bước 3. Đếm số đường đi cho từng khả năng

- Khả năng 1

Tổng độ dài theo phương song song với cạnh AB là 4
Độ dài này được phân chia vào hai đoạn (đoạn thứ nhất và đoạn thứ ba), mỗi đoạn phải có độ dài dương.
$$\Rightarrow \text{Soˆˊ caˊch phaˆn chia: }{C}_{4-1}^{2-1}=C_3^1=3$$
$$\Rightarrow \text{Tổng độ daˋi theo phương song song với cạnh AD laˋ 4, chỉ coˊ một đoạn, neˆn chỉ coˊ 1 caˊch}$$
Vậy số đường đi trong khả năng này là: $3.1=3$ cách

- Khả năng 2: Lập luận hoàn toàn tương tự, ta cũng được 3 đường đi

Do đó khi $m=n=4$ và $k=2$, ta có 6 đường đi.

b) Vì đổi hướng đúng 444 lần nên đường đi gồm: $4+1=5$ đoạn thẳng
Các khả năng vẽ hướng đi: với 5 đoạn thẳng, có hai khả năng

- Khả năng 1:

Các đoạn song song với cạnh AB chiếm 3 đoạn
Các đoạn song song với cạnh AD chiếm 2 đoạn

- Khả năng 2:

Các đoạn song song với cạnh AD chiếm 3 đoạn
Các đoạn song song với cạnh AB chiếm 2 đoạn

Ở khả năng 1:

- Tổng độ dài theo phương song song với cạnh AB là 8, được chia vào 3 đoạn, mỗi đoạn có độ dài dương.

$$\text{Soˆˊ caˊch: }{C}_{8-1}^{3-1}=C_7^2=21$$

- Tổng độ dài theo phương song song với cạnh AD là 10, được chia vào 2 đoạn.

$$\text{Soˆˊ caˊch: }{C}_{10-1}^{2-1}=C_9^1=9$$

$$\Rightarrow \text{Tổng soˆˊ caˊch ở khả na˘ng 1 laˋ: }21.9=189$$

Tương tự khả năng 2 có: $C_9^2.C_7^1=252$ cách

Do đó khi $m=8,n=10$ và $k=4$, ta có $189+252=441$ đường đi.