โปรแกรมนับจำนวน BST ที่เป็นไปได้จาก n โหนดใน Python

การนับจำนวน Binary Search Tree จาก n โหนด

จำนวน BST ที่เป็นไปได้จาก n โหนดที่แตกต่างกัน คือ Catalan number C(n)

สูตร Catalan Number

$$C(n) = \frac{(2n)!}{(n+1)! \times n!} = \frac{1}{n+1} \binom{2n}{n}$$

อัลกอริทึมคำนวณ C(n)

1. คำนวณ binomial coefficient C(2n, n) แบบ iterative (หลีกเลี่ยง factorial ใหญ่)
2. หารด้วย (n+1)

ตัวอย่างโค้ด

from math import factorial

def ncr(n, r):
    res = 1
    if r > n - r:
        r = n - r
    for i in range(r):
        res *= (n - i)
        res //= (i + 1)
    return res

def solve(n):
    c = ncr(2 * n, n)
    return c // (n + 1)

n = 3
print(solve(n))

ผลลัพธ์

5

คำอธิบาย

n=3 → C(3) = 5 BSTs ที่เป็นไปได้

ค่า Catalan เริ่มต้น: C(0)=1, C(1)=1, C(2)=2, C(3)=5, C(4)=14, C(5)=42, ...