Merge pull request #255 from rahulkumaran/catalan

prateekiiest · web-flow · commit cfba6e163bf5 · 2017-12-31T16:09:42.000+05:30
Added 2 different implementations for Catalan Numbers
diff --git a/Competitive Coding/Math/Catalan_Numbers/README.md b/Competitive Coding/Math/Catalan_Numbers/README.md
@@ -0,0 +1,25 @@
+The two different programs in this folder contain the same implementation!
+The programs basically are a python implementation of the Catalan Numbers.
+They're similar to Fibonacci (very slightly)
+
+The two different implementations vary only in terms of time taken!<br>
+Basically we can implement in 3 different ways!<br>
+
+* Recursively - `Exponential time complexity`<br>
+* Dynamic Programming - `O(n^2)`<br>
+* Binomial Coefficient - `O(n)` <br><br>
+
+Each of the above 3 implementations have a descending order of time complexities from (1) to (3) <br><br>
+
+The Binomial implementation has the best time complexity while the Recursive implementation has the worst time complexity<br>
+In this folder we have the Binomial and Recursive implementations of Catalan Numbers.<br><br>
+
+Catalan Numbers have a lot of applications in Combinatorics. Some of them are listed below:
+* Cn is the number of standard Young tableaux whose diagram is a 2-by-n rectangle. In other words, it is the number of ways the numbers 1, 2, ..., 2n can be arranged in a 2-by-n rectangle so that each row and each column is increasing. As such, the formula can be derived as a special case of the hook-length formula.
+* Cn is the number of ways that the vertices of a convex 2n-gon can be paired so that the line segments joining paired vertices do not intersect. This is precisely the condition that guarantees that the paired edges can be identified (sewn together) to form a closed surface of genus zero (a topological 2-sphere).
+* Cn is the number of semiorders on n unlabeled items.
+* In chemical engineering Cn-1 is the number of possible separation sequences which can separate a mixture of n components.<br><br>
+
+### Sources :
+(1) Click [here](https://www.geeksforgeeks.org/program-nth-catalan-number/) to know more about Catalan number implementations and its theory.<br>
+(2) Click [here](https://en.wikipedia.org/wiki/Catalan_number) to know more about the applicatations of Catalan Numbers in Combinatorics
diff --git a/Competitive Coding/Math/Catalan_Numbers/catalan_binomial.py b/Competitive Coding/Math/Catalan_Numbers/catalan_binomial.py
@@ -0,0 +1,15 @@
+def binCoeff(n, k):	#Finds the binomial coefficient
+    if (k > n - k):	#As binCoeff(n,k)=binCoeff(n,n-k)
+        k = n - k
+    res = 1		#Initialising Result
+    for i in range(k):
+        res = res * (n - i)
+        res = res / (i + 1)
+    return res		#The binomial coefficient is returned
+
+def catalan(n):		#Function that finds catalan numbers
+    c = binCoeff(2*n, n)	#Finding value of c by calling the binCoeff function
+    return c/(n + 1)		#This is the final catalan number
+
+if __name__=='__main__':
+	print "The 10th catalan number is:",catalan(9)
diff --git a/Competitive Coding/Math/Catalan_Numbers/catalan_recursive.py b/Competitive Coding/Math/Catalan_Numbers/catalan_recursive.py
@@ -0,0 +1,10 @@
+def catalan_numbers(n):
+    if n <=1 :		#The result will be 1, if the function takes an argument that's equal to or less than 1
+        return 1
+    res = 0		#Result has been initialised to 0
+    for i in range(n):
+        res += catalan_numbers(i) * catalan_numbers(n-i-1)	#The recursive function call
+    return res
+
+if __name__=='__main__':
+	print "The 10th catalan number is:",catalan(9)
