ngoặc Kết hợp với Ngoài

Question

Tôi có một vấn đề kết hợp thú vị và tôi là kinda mắc kẹt

Cho phép định nghĩa một hàm p (xn) mà trả về số '()' cho phương trình x Bây giờ x chỉ có thể là theo hình thức x1 + x2 + x3 ... xn chức năng này được định nghĩa cho n> = 2

Ví dụ:

P (x2) = (x1 + x2) = 1

p (x3) ​​= ((x1 + x2) + x3) và (x1 + (x2 + x3))

p (x4) =

((x1 + x2) + (x3 + x4))

(((x1 + x2) + x3) + x4)

((x1 + (x2 + x3)) + x4)

(x1 + ((x2 + x3) + x4))

(x1 + (x2 + (x3 + x4)))

và do đó trên Thông báo (x1 + (x2 + x3) + x4) không phải là ví dụ hợp lệ phải có một() cho mỗi +

Bây giờ, tôi đang cố gắng đưa ra công thức cho P sẽ xác định số lượng kết hợp Tôi không chắc chắn nếu có một công thức cố định hoặc định nghĩa đệ quy phụ thuộc vào các điều khoản trước đó của nó. Các bạn có thể giúp tôi tìm ra công thức không?

Answer 1

Về cơ bản, bạn đang tìm cách đếm số cây biểu thức nhị phân duy nhất trong đó các nút là tổng hợp và các lá là x đến x _n. Hãy gọi số này là P (n).

Bạn có thể chọn bất kỳ tóm tắt n-1 nào làm nút gốc. Hãy chọn tổng kết thứ k'th. Có các biến k ở bên trái của thư mục gốc, vì vậy bạn có thể tổ chức cây con trái theo cách P (k). Có các biến n-k ở bên phải, do đó, các cây con bên phải có thể được sắp xếp theo cách P (n-k). Vì vậy, trong tổng số bạn có thể tổ chức cây trong P (k) P (n-k) cách khác nhau.

Vì bạn có thể chọn k tự do từ 1 đến n-1, tổng số mà bạn có thể tổ chức các cây biểu thức với n lá là:

P(n) = P(1)P(n-1) + P(2)P(n-2) + ··· + P(n-2)P(2) + P(n-1)P(1) 

Theo ghi nhận của @DSM trong các ý kiến ​​tái phát này mối quan hệ tạo ra các số Catalan. Có một giải pháp hình thức khép kín, nhưng đó là một chút khó khăn để lấy được từ công thức lặp lại. Bạn có thể tìm thấy một số bằng chứng về công thức trong Wikipedia article for Catalan numbers. Giải pháp là:

P(n) = C(2n,n)/(n+1)    where C(n,k) = n!/(k!(n-k)!)