CATALAN NUMBERS IN PYTHON LANGUAGE
AMRUHA AHMED
29th November,2023.
Catalan Numbers are the sequence of numbers that are calculated using the formula:
(2n)!/(n+1)!n!
Where n=0,1,2,3….
Catalan Numbers prove to be extremely useful in calculating the number of binary search trees that can be made using 'n' nodes.
FUNCTIONS REQUIRED:
- fact(): a recursive function to return the factorial of the parameter passed
- main(): invokes fact() at appropriate intervals to calculate the desired number of catalan numbers
VARIABLES REQUIRED IN FACT FUNCTION:
- n : passed as a parameter
VARIABLES REQUIRED IN THE MAIN FUNCTION:
- ctr: stores the count of numbers to be generated
- term1: stores the value of (2n)!
- term2: stores the value of (n+1)!
- term3: stores the value of n!
- finalterm: gives final term=catalan number at i'th position
ALGORITHM FOR MAIN FUNCTION:
- 1.Start
- 2.Accept the count of catalan numbers to be generated and store in ctr
- 3. For i =0 till i is less than ctr, the steps from 4 to 8 need to be repeated otherwise go to step 9
- 4. Invoke fact() and pass 2*i as a parameter.Store the result in term1
- 5.Invoke fact() and pass i+1 as a parameter. Store the result in term2
- 6. Invoke fact() and pass i as a parameter. Store the result in term3
- 7. Calculate term1/(term2+term3) and store the resultant in finalterm
- 8. Display finalterm
- 9.Stop
PROGRAM:
def fact(n):#recursive function to calculate factorial of 'n'
if(n==0):
return 1
else:
return(n*fact(n-1))
ctr=int(input("\n Enter the count of catalan numbers to be generated:"))#stores the count of numbers to be generated
print("\n The first {} Catalan Numbers are...\n".format(ctr))
for i in range(0,ctr):
term1=fact(2*i) #stores the value of (2n)!
term2=fact(i+1)#stores the value of (n+1)!
term3=fact(i)#stores the value of n!
finalterm=int(term1/(term2*term3))#gives final term=catalan number at i'th position
print(finalterm,end=" ")
DRY RUN:
If ctr=5 then the following will be the values of i, term1, term2, term3 and finalterm:
OUTPUT:
Enter the count of catalan numbers to be generated: 5
The first 5 Catalan Numbers are...
1 1 2 5 14