Chủ đề này có 3 trả lời

[vuhung]

Bài này mình sưu tầm trong một quyển sách về algorithm, khá dễ hiểu và mình nhớ là đã từng có attempt tính http://dientuvietnam...mimetex.cgi?b_n vào năm lớp 11, tất nhiên là không giải được.

ok, đề bài nhé:

Đặt http://dientuvietnam...mimetex.cgi?b_n là số những những cây nhị phân với n nodes.

a. Chứng minh và với ,

( Bỏ qua, không chứng minh).

b. Gọi B(x) là hàm sinh bởi b_k
.
Chứng minh
và từ đó suy ra


c. Chứng minh


d. Chứng minh

Bài viết đã được chỉnh sửa nội dung bởi thuantd: 20-01-2005 - 10:11

[AJin]

Cái này phải là binary search tree(BST) chứ không chỉ là binary tree.
Câu b thì chắc là em chịu, câu c em nghĩ dùng quy nạp nhưng vẫn chưa cm được

[ntson]

Dãy số b(n) như trên gọi là số catalan và bằng (2n!)/(n!*n!*(n+1))

Bài viết đã được chỉnh sửa nội dung bởi ntson: 18-04-2005 - 17:10

[AJin]

Bài này trong phần Algorithm(Computer) nhưng bản chất chỉ đơn thuần là pure math, các bạn có thể coi giả thuyết là câu a) còn yêu cầu là bắt cm các câu tiếp theo.