Tìm số cây nhị phân chứa n nút

Tìm số cây nhị phân chứa n nút

Em chào các hảo thủ của box Toán học. Hiện nay, em đang mắc một bài này, hi vọng mọi người giải giúp em.

Đề bài: tìm số cây nhị phân (binary tree) có thể tạo ra khi cây có n nút (node), giá trị lần lượt các nút là 1, 2,..., n. Ví dụ f(1) = 1, f(2) = 2, f(3) = 5, f(4) = 14,...

Chú thích (chắc mọi người chẳng cần, nhưng em nói cho chắc): cây nhị phân là đồ thị có hướng, mỗi nút gồm 2 nhánh, nút con bên trái nhỏ hơn giá trị nút mẹ và nút con bên phải lớn hơn giá trị nút mẹ.

hateMU!!!

Đáp số là (1/(n+1) ) * (2n)!/ (n!*n!) , nhưng nếu bác muốn chứng minh cụ thể thì phải để anh em suy nghĩ đã.
Được username sửa chữa / chuyển vào 18:48 ngày 20/04/2003

Tớ không biết bài này, không hiểu đề bài lắm. Bác có thể nói lại không?
----------------
Còn nếu kết quả như username nói thì đó là số Kaplan
=số khả năng ghép n dấu "( "và n dấu " )" để tạo thành dãy dấu ngoặc có ý nghĩa, hay là số cách để chia một hình đa giác lồi n+1 cạnh thành các tam giác bằng các đường chéo, và hình như còn một số cái khác nữa ví dụ bài toán trên.
--------------
Matek

Em nói lại vậy. Cây nhị phân là đồ thị có hướng, gồm 1 đỉnh là gốc, mỗi đỉnh nối với nhiều nhất 2 đỉnh khác. Giá trị tại mỗi đỉnh lớn hơn đỉnh nối tới bên trái nó và nhỏ hơn đỉnh nối tới bên phải nó. Ví dụ về một cây nhị phân như dưới đây.
Gốc là 15.
15 có 2 con là 10 và 21.
10 có 1 con là 5, 21 có 2 con là 18 và 23
5 có 1 con là 6, 23 có 1 con là 26
26 có 1 con là 22
22 có 1 con là 24
........................15
.............10.................21
........5..................18.........23
............6..................................26
..........................................22
..............................................24
Bài toán em muốn hỏi là: nếu biết trước cây gồm n nút với giá trị khác nhau từ 1 đến n, hỏi có bao nhiêu cách xây dựng cây (một tập hợp nút có thể xây dựng nhiều cây khác nhau, tuỳ thuộc vào thứ tự các nút lần lượt được thêm vào).
hateMU!!!
Được hateMU sửa chữa / chuyển vào 00:46 ngày 21/04/2003
Được hateMU sửa chữa / chuyển vào 00:47 ngày 21/04/2003

Mình cũng hỏi cái, thế sao f(3) lại bằng 5 nhỉ?
-----2
-1------3
----------3-------------------2-----------------------3
----2-------------------1-----------------------1
1-----------------------------3-----------------------2
--1---------------------2-----------------------1
-----3------------------------3-----------------------2
--2---------------------1----------------------------------3
Không hiểu mình hiểu có đúng không?

Strawhero

Được thanhha sửa chữa / chuyển vào 01:09 ngày 21/04/2003

À, f(3) = 5 ở đây là cây chưa điền số, điền vào thì phải hơn.

Strawhero

Xin lỗi mọi người vì em đã trình bày không được rõ ràng lắm về khái niệm binary tree. Trong binary tree, tất cả mọi node thuộc nhánh bên trái của đều nhỏ hơn node đó, và tất cả mọi node thuộc nhánh bên phải đều lớn hơn node đó. Vì vậy, 2 trường hợp sau không phải là binary tree:
.......2
..1
.......3 (vì 3 thuộc nhánh trái của 2 mà 3 > 2)
......2
...........3
......1 (vì 1 thuộc nhánh phải của 2 mà 1 < 2)
hateMU!!!
Được hateMU sửa chữa / chuyển vào 07:25 ngày 21/04/2003

Theo tôi được học thì định nghĩa cây nhị phân khác với của bác 1 tẹo : một cây nhị phân hoặc là tập rỗng hoặc tạo bởi một gốc, một cây nhị phân gọi là cây con trái, và một cây nhị phân gọi là cây con phải (cây nhị phân hoàn toàn khác với cây bình thường trong đó bậc của mỗi đỉnh <= 2 ).
Thực ra định nghĩa này và định nghĩa của bác là tương đương nhau ( khi có một cây nhị phân như trên, có duy nhất một cách đánh các số 1, 2,.. n vào các đỉnh sao cho chúng thoả mãn điều kiện của bác, CM điều này cũng không dễ ) nhưng định nghĩa này tỏ ra có ích hơn trong việc đếm số cây nhị phân n đỉnh.
Nếu u(n) là số cây nhị phân n đỉnh thì nó được tạo bởi một cây con bên trái với i đỉnh và một cây con bên phải với n-i-1 đỉnh, do đó ta có công thức truy hồi u(n) = tổng (i = 0 đến n-1) u(i)*u(n-1-i)
Muốn giải cái này thì đặt hàm sinh F(x) = tổng u(n) x^n => F(x) thoả mãn phương trình xF^2(x) - F(x) + 1 =0 rồi so sánh hệ số ta được kết quả như đã nói ở trên :
u(n) = C(n,2n)/(n+1)
Số này người ta gọi là số Catalan, rất quen thuộc trong một số bài toán tổ hợp như bác matek có nói ở trên như đếm số cách chia đa giác hay số đường đi giữa 2 điểm trên mạng lưới nguyên.

Nếu như vậy có lẽ bài toán sẽ đơn giản đi nhiều.
Với n nút, nút mẹ đầu tiên có thể lấy bất cứ giá trị nào trong khoảng từ 1 đến n, đặt là k. Khi đó nhánh bên trái sẽ có (k-1) nút, và nhánh bên phải có (n-k) nút. Trong đó thì nhánh bên trái có f(k-1) cách, nhánh bên phải có f(n-k) cách. Như vậy ta có công thức truy hồi:
f(n) = (tổng k = 1 đến n) f(k-1) * f(n-k)
f(0) = 1
Sau đấy chỉ cần chứng minh bằng phương pháp quy nạp f(n) = (2n)!/n!*(n+1)!.

Strawhero

Lại gửi cùng lúc rồi .

Strawhero