Tìm công thức của phương trình lặp lại nhị phân này? f (m, n) = f (m-1, n) + f (m, n-1)

Question

SORRY GUYS! LỖI CỦA TÔI! Cảm ơn lời nhắc của bạn, tôi phát hiện ra f (0, k) == f (k, 0) == 1. Câu hỏi này là về cách đếm số đường đi ngắn nhất từ ​​lưới (0,0) đến (m, n).

Tôi phải giải phương trình sau đây ngay bây giờ, tìm hiểu chính xác những gì f (m, n) bằng.

1) f(m,n) = 0 : when (m,n) = (0,0) 
**2) f(m,n) = 1 : when f(0,k) or f(k,0)** 
3) f(m,n) = f(m-1,n) + f(m,n-1) : when else 

ví dụ:

1) f(0,0) = 0; 
2) f(0,1) = 1; f(2,0) = 1; 
3) f(2,1) = f(1,1) + f(2,0) = f(0, 1) + f(1, 0) + f(2, 0) = 1 + 1 + 1 = 3 

Tôi nhớ có một cách tiêu chuẩn để giải quyết các loại như vậy của phương trình tái phát nhị phân như tôi học được trong lớp thuật toán của tôi cách đây vài năm, nhưng tôi chỉ không thể nhớ cho bây giờ .

Có ai có thể đưa ra bất kỳ gợi ý nào không? Hoặc một từ khóa làm thế nào để tìm câu trả lời?

Answer 1

Ugh, tôi chỉ vui vẻ trải qua các sách giáo khoa cũ của tôi về các chức năng tạo và bạn đã thay đổi câu hỏi một lần nữa!

Câu hỏi này là cách đếm số đường đi ngắn nhất từ ​​lưới (0,0) đến (m, n).

Đây là câu hỏi cơ bản về tổ hợp - không đòi hỏi phải biết bất kỳ điều gì về chức năng tạo hoặc thậm chí là các mối quan hệ lặp lại.

Để giải quyết, hãy tưởng tượng các đường dẫn được viết ra dưới dạng chuỗi U (cho "lên") và R (cho "đúng"). Nếu chúng ta di chuyển từ (0,0) đến, nói, (5, 8), phải có 5 R và 8 U. Chỉ một ví dụ:

RRUURURUUURUU 

Sẽ luôn có, trong ví dụ này, 8 U và 5 R; các đường dẫn khác nhau sẽ chỉ có chúng theo các thứ tự khác nhau. Vì vậy, chúng tôi chỉ có thể chọn 8 vị trí cho U của chúng tôi, và phần còn lại phải là của R. Như vậy, câu trả lời là

(8+5) choose (8) 

Hoặc, nói chung,

(m+n) choose (m) 

Answer 2

Hãy thử tìm kiếm "chức năng tạo" trong tài liệu. Một cách tiếp cận sẽ là tưởng tượng một hàm P (x, y) trong đó hệ số của x^m y^n là f (m, n). Dòng lặp lại (dòng 3) cho bạn biết rằng P (x, y) - xP (x, y) - yP (x, y) = (1-xy) P (x, y) nên khá đơn giản, ngoại trừ những pesky giá trị cạnh. Sau đó giải quyết cho P (x, y).

Bạn có chắc chắn f(k,0) = f(0,k) = k và không phải 1, có thể không? Nếu đúng như vậy, tôi muốn đặt cược tốt nhất là viết một số giá trị, đoán xem chúng là gì, sau đó chứng minh điều đó.

Answer 3

này chỉ đơn giản là hệ số nhị thức

f(m,n) = (m+n choose m) = (m+n choose n) 

Bạn có thể chứng minh điều này bằng cách ghi nhận rằng họ đáp ứng các mối quan hệ tái phát tương tự.

Để lấy công thức (nếu bạn không thể đoán và sau đó kiểm tra), hãy sử dụng các hàm tạo như Chris Nash đề xuất chính xác.