Catalan numbers are named after the Belgian mathematician Eugène Charles Catalan, who discovered these in 1855. They represent the ratio of the central binomial coefficient to its consecutive number plus one. The central binomial coefficient for n=1 is divided by two, that for n=2 by three, and so on to obtain the corresponding Catalan number. Catalan numbers appear in many calculations in combinatorics, for example, in counting problems in graph theory. The counting of Catalan numbers begins at zero, so the first Catalan number is C0 with the value 1. C1 = 1, C2 = 2, and the sequence then continues with 5, 14, 42, 132, 429, 1430, ...
| Cn = | 1 | ( | 2n | ) |
| n + 1 | n |
For n enter a positive integer smaller as 86 and press Calculate to determine the Catalan number.
An example of a problem that can be solved by calculating Catalan numbers: You have x different variables. Here, let x=4 with the variables a, b, c, and d. How many ways are there to calculate with these using a specific combination and parentheses? So, it's all about finding the correct combinations of parentheses. This number is the fourth Catalan number C3, the one for n=3. So there are five possibilities, which are:
• ((a ∘ b) ∘ c) ∘ d
• (a ∘ (b ∘ c)) ∘ d
• (a ∘ b) ∘ (c ∘ d)
• a ∘ ((b ∘ c) ∘ d)
• a ∘ (b ∘ (c ∘ d))
Whether these five different calculations produce the same or different results depends on the associativity of the connection. For plus and multiplication, the results are the same; for minus and division, they are different, as is the case for multiplication.
Other examples where the solutions are always Cn would be:
Binary trees: how many different structures can a binary decision tree with n nodes have?
Path planning: How many paths in a grid lead diagonally from (0,0) to (n,n) without ever crossing the diagonal?
Triangulation of a polygon: How many ways are there to divide an n+2 vertex into triangles without any diagonals intersecting?
Combinatorics and Statistics Functions and Formulas © Jumk.de Webprojects | Imprint & Privacy | German: Kombinatorik- und Statistik-Funktionen
See also Statistics Calculator
big.js Script Copyright (c) 2022 Michael Mclaughlin, MIT Expat Licence.