Python Math: nth Catalan Number
Python Math: Exercise-25 with Solution
Write a Python program for the nth Catalan numbers.
In combinatorial mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects. They are named after the Belgian mathematician Eugène Charles Catalan (1814–1894).
Using zero-based numbering, the nth Catalan number is given directly in terms of binomial coefficients by
The first Catalan numbers for n = 0, 1, 2, 3, … are
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, ....
Pictorial Presentation
The C5 = 42 noncrossing partitions of a 5-element set (below, the other 10 of the 52 partitions)
Image Credits: Watchduck
Sample Solution:
Python Code:
def catalan_number(num):
if num <=1:
return 1
res_num = 0
for i in range(num):
res_num += catalan_number(i) * catalan_number(num-i-1)
return res_num
for n in range(10):
print(catalan_number(n))
Sample Output:
1 1 2 5 14 42 132 429 1430 4862
Flowchart:
Python Code Editor:
Have another way to solve this solution? Contribute your code (and comments) through Disqus.
Previous: Write a Python program to convert a float to ratio.
Next: Write a Python program to print number with commas as thousands separators (from right side)?
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://www.w3resource.com/python-exercises/math/python-math-exercise-25.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics