Bài toán đếm đường đi theo bước

Cho tứ diện ABCD, một con bọ đang đậu ở đỉnh A của tứ diện. Mỗi lần nghe một tiếng trống thì nó nhảy sang một đỉnh bất kỳ của tứ diện ABCD mà kề với đỉnh nó đang đậu. Hỏi sau 4 tiếng trống, nó có bao nhiêu cách trở về đỉnh A?

Bài toán này là một bài toán đếm đường đi theo bước, áp dụng kiến thức về đệ quy tổ hợp trên đồ thị

Bài 1: Tam giác đều 3 đỉnh Một con bọ bắt đầu tại một đỉnh của tam giác đều. Mỗi bước nó nhảy sang một đỉnh kề. Sau 10 bước, hỏi có bao nhiêu cách để trở về đỉnh ban đầu?

Bài 2 : Khối lập phương – trở về đỉnh ban đầu Một con bọ bắt đầu ở một đỉnh của khối lập phương. Mỗi bước nó nhảy sang một đỉnh kề qua cạnh. Hỏi sau 6 bước, có bao nhiêu cách để trở về đỉnh ban đầu?

Bài 3: Đi lại trên đồ thị hình sao 4 đỉnh Có 1 đồ thị gồm 4 đỉnh: đỉnh trung tâm A nối với 3 đỉnh ngoài B,C,D. Một con bọ ở đỉnh $A$. Mỗi bước, nó đi sang 1 đỉnh kề. Hỏi sau n bước, có bao nhiêu cách để trở lại đỉnh $A$?

Bài 4: Hình vuông – về lại đỉnh A Một con kiến đang ở đỉnh A của hình vuông ABCD, mỗi bước nó đi sang một đỉnh kề (cạnh vuông). Hỏi sau 6 bước, có bao nhiêu cách để trở lại đỉnh A?

Đệ quy tổ hợp trên đồ thị là một kỹ thuật giải toán đếm số cách di chuyển/trạng thái trong các cấu trúc đồ thị (graph) sử dụng công thức truy hồi (đệ quy) để mô tả sự chuyển tiếp giữa các trạng thái theo thời gian (hoặc theo bước).

---

🧠 I. Định nghĩa cơ bản

1. Đồ thị:

• Là tập hợp gồm các đỉnh (vertex) và cạnh (edge).

• Có thể là có hướng hoặc vô hướng, có thể trọng số hoặc không.

2. Bài toán tổ hợp trên đồ thị thường hỏi:

• Có bao nhiêu cách đi từ đỉnh A đến đỉnh B sau đúng $n$ bước?

• Có bao nhiêu cách trở về đỉnh ban đầu sau $n$ bước?

• Có bao nhiêu đường đi khác nhau dài ≤ $n$?

• Hoặc xác suất đứng ở một đỉnh nào đó sau $n$ bước (liên quan đến Markov).

---

🔄 II. Tư duy đệ quy tổ hợp

Tư tưởng cốt lõi:

Đếm số cách đi đến một đỉnh tại bước $n$ bằng cách cộng số cách đi đến các đỉnh kề nó ở bước $n-1$.

Gọi $f(v,n)$ là số cách đến đỉnh $v$ sau $n$ bước. Khi đó:

f(v,n)=∑u∈keˆˋ với vf(u,n−1)f(v, n) = \sum_{u \in \text{kề với } v} f(u, n-1)f(v,n)=u∈keˆˋ với v∑​f(u,n−1)

---

📘 III. Một số mô hình điển hình

1. Chu trình (Cycle)

Ví dụ: tam giác đều 3 đỉnh, hình vuông 4 đỉnh, n-gon

Cách giải:

• Gọi trạng thái là: “ở đỉnh gốc” hoặc “ở đỉnh khác”

• Dùng đệ quy 2 biến: an;bn​

---

2. Tứ diện, khối lập phương, khối bát diện... (Đồ thị đối xứng không phẳng)

• Tận dụng tính đối xứng → nhóm trạng thái: "ở A", "không ở A" (giống bài tứ diện con bọ)

• Xây dựng hệ phương trình đệ quy với các trạng thái tương ứng

---

3. Đồ thị hình sao, cây, đường thẳng, lưới ô vuông

Ví dụ: đi từ (0,0) đến (m,n) theo các bước đi hợp lệ → dùng quy hoạch động với quy tắc:

f(i,j)=f(i−1,j)+f(i,j−1)(neˆˊu đi phải hoặc xuoˆˊng)

---

🔧 IV. Cách tiếp cận để giải bài toán đệ quy tổ hợp trên đồ thị

1. Xác định trạng thái:

• Ở bước n, ta cần biết con bọ/điểm đang ở đâu → đó là trạng thái.

2. Công thức chuyển trạng thái:

• Từ trạng thái nào có thể chuyển đến trạng thái hiện tại? Bao nhiêu cách?

3. Khởi tạo (Base case):

• Bước 0 (hoặc ban đầu): vị trí ban đầu duy nhất.

4. Tính từng bước:

• Duyệt từ 1 đến $n$, tính dần theo công thức truy hồi.

---

🧮 V. Công cụ bổ trợ

• Quy hoạch động (DP): lưu kết quả trung gian để tránh lặp lại

• Ma trận chuyển trạng thái: dùng khi mô hình có thể viết dưới dạng tuyến tính → áp dụng lũy thừa ma trận

• Xác suất Markov: nếu có xác suất kèm theo

---

🔬 VI. Ví dụ minh họa ngắn

🔹 Bài toán: Chu trình 3 đỉnh, quay về A sau $n$ bước

Gọi:

• an​: số cách ở A sau n bước

• bn​: số cách ở đỉnh khác

Công thức:

an+1=bn,bn+1=2an+bn​

---

🔹 Bài toán: Tứ diện 4 đỉnh, quay về A

Gọi:

• an​: số cách ở A

• xn​: số cách ở đỉnh khác

Công thức:

an+1=xn,xn+1=3an+2xn​

---

✅ Tổng kết: