I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
get GPL
COST (GBP)
this unit 0.19
sub units 0.00
+
0

Catalan Numbers List

Computes the Catalan numbers, of order 0 to n.
Controller: CodeCogs

Interface

C++

Catalan Numbers List

 
std::vector<int>catalan_numbers_listintn )
The formula for calculating the Catalan number of order n has several forms:

This function uses the following recurrence relation:

The Catalan number C(n) counts:

1) the number of binary trees with \inline  n vertices;

2) the number of ordered trees with \inline  n+1 vertices;

3) the number of full binary trees with \inline  2n+1 vertices;

4) the number of well formed sequences of \inline  2n parentheses;

5) the number of ways \inline  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 \inline  f : [n] \rightarrow [n] which satisfy \inline  f(i) \leq i, for all \inline  i = \overline{1, n}

8) the number of ways to triangulate a polygon with \inline  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

Returns

the Catalan numbers of order 0 to n

Authors

Lucian Bentea (August 2005)
Source Code

Source code is available when you agree to a GP Licence or buy a Commercial Licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.