cho số n, hỏi có bao nhiêu cách đóng mở ngoặc phù hợp với 2*n dấu ngoặc ví dụ: n=3 thì có 5 cách đóng, mở ngoặc phù hợp: ((())), (()()), (())(), ()(()), ()()()

Khanh

Bước 1: Xác định trường hợp cơ bản

- Khi n = 0 không có dấu ngoặc nào, do đó chỉ có 1 cách duy nhất là không làm gi cả. Vậy f(0) = 1

Bước 2: Xác định quy luật đệ quy

- Khi n > 0 mỗi cặp ngoặc đóng mở có thể được chia thành hai phần: phần bên trải và phần bên phải. Phần bên trái có thể có từ 0 đến n - 1 cặp ngoặc, và phần bên phải sẽ có số cặp ngoặc còn lại.

Do đó, ta có:

f(n) = sum k = 0 to n - 1 f(k) * f * (n - 1 - k)

Bước 3: Áp dụng quy luật đệ quy để tỉnh f(n)

- Ta sẽ tỉnh lần lượt từ ƒ(1) đến f(n).

f(1) = f(0) * f(0) = 1 * 1 = 1 f(2) = f(0) * f(1) + f(1) * f(0) = 1 * 1 + 1 * 1 = 2 f(3) = f(0) * f(2) + f(1) * f(1) + f(2) * f(0) = 1 * 2 + 1 * 1 + 2 * 1 = 5 f(4) = f(0) * f(3) + f(1) * f(2) + f(2) * f(1) + f(3) * f(0) = 1 * 5 + 1 * 2 + 2 ]

Bước 4: Kết luận

- Ta thấy rằng f(n) chính là dây số Catalan, và công thức tổng quát của nó là:

f(n) = 1/(n + 1) * binomial(2n,n)