fork download
copy 
  1. # See https:#www.geeksforgeeks.org/program-nth-catalan-number/
  2. # for reference of below code.
  3.  
  4. # A function to find factorial of a given number
  5. def factorial(n) :
  6. 	res = 1
  7.  
  8. 	# Calculate value of [1*(2)*---*
  9. 	#(n-k+1)] / [k*(k-1)*---*1]
  10. 	for i in range(1, n + 1):
  11. 		res *= i
  12. 	return res
  13.  
  14. def binomialCoeff(n, k):
  15.  
  16. 	res = 1
  17.  
  18. 	# Since C(n, k) = C(n, n-k)
  19. 	if (k > n - k):
  20. 		k = n - k
  21.  
  22. 	# Calculate value of [n*(n-1)*---*(n-k+1)] /
  23. 	# [k*(k-1)*---*1]
  24. 	for i in range(k):
  25.  
  26. 		res *= (n - i)
  27. 		res //= (i + 1)
  28.  
  29. 	return res
  30.  
  31. # A Binomial coefficient based function to
  32. # find nth catalan number in O(n) time
  33. def catalan(n):
  34.  
  35. 	# Calculate value of 2nCn
  36. 	c = binomialCoeff(2 * n, n)
  37.  
  38. 	# return 2nCn/(n+1)
  39. 	return c // (n + 1)
  40.  
  41. # A function to count number of BST
  42. # with n nodes using catalan
  43. def countBST(n):
  44.  
  45. 	# find nth catalan number
  46. 	count = catalan(n)
  47.  
  48. 	# return nth catalan number
  49. 	return count
  50.  
  51. # A function to count number of binary
  52. # trees with n nodes
  53. def countBT(n):
  54.  
  55. 	# find count of BST with n numbers
  56. 	count = catalan(n)
  57.  
  58. 	# return count * n!
  59. 	return count * factorial(n)
  60.  
  61. # Driver Code
  62. if __name__ == '__main__':
  63.  
  64. 	n = 8
  65.  
  66. 	# find count of BST and binary
  67. 	# trees with n nodes
  68. 	count1 = countBST(n)
  69. 	count2 = countBT(n)
  70.  
  71. 	# print count of BST and binary trees with n nodes
  72. 	print("Count of BST with", n, "nodes is", count1)
  73. 	print("Count of binary trees with", n,
  74. 					"nodes is", count2)
  75.  
  76. # This code is contributed by
  77. # Shubham Singh(SHUBHAMSINGH10)
  78.  
Success #stdin #stdout 0.03s 9292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Count of BST with 8 nodes is 1430
Count of binary trees with 8 nodes is 57657600
https://ideone.com/nXGPvs
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!