Catalan_Numbers_List — Sequences

Computes the Catalan numbers, of order 0 to n.

You're viewing an older version of this page (#5348). View the current version.

Interface

#include <codecogs/maths/combinatorics/sequences/catalan_numbers_list.h>

using namespace Maths::Combinatorics::Sequences;

std::vector<int> catalan_numbers_list(int n)

The formula for calculating the Catalan number of order n has several forms:

$$C(n) = \frac{(2n)!}{(n + 1)! (n!)} = \frac{1}{n+1} \left( \begin{array}{c} 2n \\ n \end{array} \right) = \frac{1}{2n+1} \left( \begin{array}{c} 2n+1 \\ n+1 \end{array} \right)$$

(1)

This function uses the following recurrence relation:

$$C(n) = \frac{4n-2}{n+1} C(n-1), \qquad C(0) = 1$$

(2)

The Catalan number C(n) counts:

1) the number of binary trees with $n$ vertices;
2) the number of ordered trees with $n+1$ vertices;
3) the number of full binary trees with $2n+1$ vertices;
4) the number of well formed sequences of $2n$ parentheses;
5) the number of ways $2n$ ballots can be counted, in order, with n positive and n negative, so that the running sum is never negative;
6) the number of standard tableaus in a 2 by n rectangular <em> Ferrers </em> diagram;
7) the number of monotone functions $f : [n] \rightarrow [n]$ which satisfy $f(i) \leq i$, for all $i = \overline{1, n}$
8) the number of ways to triangulate a polygon with $n+2$ vertices.

Example 1

#include <codecogs/maths/combinatorics/sequences/catalan_numbers_list.h>
#include <iostream>
int main() {
  std::vector<int> result = Maths::Combinatorics::Sequences::catalan_numbers_list(8);
  std::cout << "Number of values: " << result.size() << std::endl;
    for (int i = 0; i < result.size(); i++)
      std::cout << result[i] << "  ";
  std::cout << std::endl;
  return 0;
}

Output:

Number of values: 9
1  1  2  5  14  42  132  429  1430

References

SUBSET, a C++ library of combinatorial routines, http://www.csit.fsu.edu/~burkardt/cpp_src/subset/subset.html

Parameters

the maximum order of the Catalan numbers to compute

Returns

the Catalan numbers of order 0 to n