# See https:#www.geeksforgeeks.org/program-nth-catalan-number/
# for reference of below code.
# A function to find factorial of a given number
def factorial(n) :
res = 1
# Calculate value of [1*(2)*---*
#(n-k+1)] / [k*(k-1)*---*1]
for i in range(1, n + 1):
res *= i
return res
def binomialCoeff(n, k):
res = 1
# Since C(n, k) = C(n, n-k)
if (k > n - k):
k = n - k
# Calculate value of [n*(n-1)*---*(n-k+1)] /
# [k*(k-1)*---*1]
for i in range(k):
res *= (n - i)
res //= (i + 1)
return res
# A Binomial coefficient based function to
# find nth catalan number in O(n) time
def catalan(n):
# Calculate value of 2nCn
c = binomialCoeff(2 * n, n)
# return 2nCn/(n+1)
return c // (n + 1)
# A function to count number of BST
# with n nodes using catalan
def countBST(n):
# find nth catalan number
count = catalan(n)
# return nth catalan number
return count
# A function to count number of binary
# trees with n nodes
def countBT(n):
# find count of BST with n numbers
count = catalan(n)
# return count * n!
return count * factorial(n)
# Driver Code
if __name__ == '__main__':
n = 8
# find count of BST and binary
# trees with n nodes
count1 = countBST(n)
count2 = countBT(n)
# print count of BST and binary trees with n nodes
print("Count of BST with", n, "nodes is", count1)
print("Count of binary trees with", n,
"nodes is", count2)
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)
IyBTZWUgaHR0cHM6I3d3dy5nZWVrc2ZvcmdlZWtzLm9yZy9wcm9ncmFtLW50aC1jYXRhbGFuLW51bWJlci8KIyBmb3IgcmVmZXJlbmNlIG9mIGJlbG93IGNvZGUuCgojIEEgZnVuY3Rpb24gdG8gZmluZCBmYWN0b3JpYWwgb2YgYSBnaXZlbiBudW1iZXIKZGVmIGZhY3RvcmlhbChuKSA6CglyZXMgPSAxCgkKCSMgQ2FsY3VsYXRlIHZhbHVlIG9mIFsxKigyKSotLS0qCgkjKG4taysxKV0gLyBbayooay0xKSotLS0qMV0KCWZvciBpIGluIHJhbmdlKDEsIG4gKyAxKToKCQlyZXMgKj0gaQoJcmV0dXJuIHJlcwoKZGVmIGJpbm9taWFsQ29lZmYobiwgayk6CgoJcmVzID0gMQoKCSMgU2luY2UgQyhuLCBrKSA9IEMobiwgbi1rKQoJaWYgKGsgPiBuIC0gayk6CgkJayA9IG4gLSBrCgoJIyBDYWxjdWxhdGUgdmFsdWUgb2YgW24qKG4tMSkqLS0tKihuLWsrMSldIC8KCSMgW2sqKGstMSkqLS0tKjFdCglmb3IgaSBpbiByYW5nZShrKToKCQoJCXJlcyAqPSAobiAtIGkpCgkJcmVzIC8vPSAoaSArIDEpCgkKCXJldHVybiByZXMKCiMgQSBCaW5vbWlhbCBjb2VmZmljaWVudCBiYXNlZCBmdW5jdGlvbiB0bwojIGZpbmQgbnRoIGNhdGFsYW4gbnVtYmVyIGluIE8obikgdGltZQpkZWYgY2F0YWxhbihuKToKCgkjIENhbGN1bGF0ZSB2YWx1ZSBvZiAybkNuCgljID0gYmlub21pYWxDb2VmZigyICogbiwgbikKCgkjIHJldHVybiAybkNuLyhuKzEpCglyZXR1cm4gYyAvLyAobiArIDEpCgojIEEgZnVuY3Rpb24gdG8gY291bnQgbnVtYmVyIG9mIEJTVAojIHdpdGggbiBub2RlcyB1c2luZyBjYXRhbGFuCmRlZiBjb3VudEJTVChuKToKCgkjIGZpbmQgbnRoIGNhdGFsYW4gbnVtYmVyCgljb3VudCA9IGNhdGFsYW4obikKCgkjIHJldHVybiBudGggY2F0YWxhbiBudW1iZXIKCXJldHVybiBjb3VudAoKIyBBIGZ1bmN0aW9uIHRvIGNvdW50IG51bWJlciBvZiBiaW5hcnkKIyB0cmVlcyB3aXRoIG4gbm9kZXMKZGVmIGNvdW50QlQobik6CgoJIyBmaW5kIGNvdW50IG9mIEJTVCB3aXRoIG4gbnVtYmVycwoJY291bnQgPSBjYXRhbGFuKG4pCgoJIyByZXR1cm4gY291bnQgKiBuIQoJcmV0dXJuIGNvdW50ICogZmFjdG9yaWFsKG4pCgojIERyaXZlciBDb2RlCmlmIF9fbmFtZV9fID09ICdfX21haW5fXyc6CgoJbiA9IDgKCgkjIGZpbmQgY291bnQgb2YgQlNUIGFuZCBiaW5hcnkKCSMgdHJlZXMgd2l0aCBuIG5vZGVzCgljb3VudDEgPSBjb3VudEJTVChuKQoJY291bnQyID0gY291bnRCVChuKQoKCSMgcHJpbnQgY291bnQgb2YgQlNUIGFuZCBiaW5hcnkgdHJlZXMgd2l0aCBuIG5vZGVzCglwcmludCgiQ291bnQgb2YgQlNUIHdpdGgiLCBuLCAibm9kZXMgaXMiLCBjb3VudDEpCglwcmludCgiQ291bnQgb2YgYmluYXJ5IHRyZWVzIHdpdGgiLCBuLAoJCQkJCSJub2RlcyBpcyIsIGNvdW50MikKCiMgVGhpcyBjb2RlIGlzIGNvbnRyaWJ1dGVkIGJ5CiMgU2h1YmhhbSBTaW5naChTSFVCSEFNU0lOR0gxMCkK