คำนวณ Catalan numbers ด้วย Binomial Coefficients ต้องเขียนฟังก์ชันคำนวณ binomial coefficients ก่อน
ตัวอย่าง
def binomialCoefficient(n, k):
# เพิ่มประสิทธิภาพการคำนวณ C(n, k)
if (k > n - k):
k = n - k
coeff = 1
for i in range(k):
coeff *= (n - i)
coeff /= (i + 1)
return coeff
def catalan(n):
return binomialCoefficient(2*n, n) / (n + 1)
for i in range(11):
print(catalan(i))
ผลลัพธ์
1.0 1.0 2.0 5.0 14.0 42.0 132.0 429.0 1430.0 4862.0 16796.0
