[Previous] [Next] [Contents]

## `combinat::catalan` -- Catalan numbers

#### Introduction

`combinat::catalan`(n) returns the `n`-th Catalan number.

#### Call(s)

`combinat::catalan(n)`

#### Parameters

`n` | - | nonnegative integer

#### Returns

A positive integer.

#### Details

- The Catalan numbers are ubiquitous in combinatorics. For example, `combinat::catalan`(n) counts the Dyck words of size `n`, the ordered trees with `n` nodes, the binary trees with `n+1` nodes, the complete binary trees with `2n+1` nodes, the standard tableaux with two rows of size `n`, the triangulations of a regular `n+2`-gone, or the non-crossing partitions of 1,2,...,n.
- `combinat::catalan`(n) is calculated using the formula

      catalan(n) =
            binomial(2*n,n) / (n+1)

#### Example 1

We compute the 5-th Catalan number:

    >> combinat::catalan(5)

                                        42

Correct answer. But what was the question ?

#### Example 2

We compute the first Catalan numbers:

    >> combinat::catalan(n) $ n = 0..6

                              1, 1, 2, 5, 14, 42, 132

They coincide with the number of Dyck words:

    >> combinat::dyckWords::count(n) $ n = 0..6

                              1, 1, 2, 5, 14, 42, 132

They also coincide with the numbers of tableaux with two rows or two columns of the same size:

    >> 1, nops(combinat::tableaux::list([2 $ n])) $ n = 1..6;
       1, nops(combinat::tableaux::list([n $ 2])) $ n = 1..6;

                              1, 1, 2, 5, 14, 42, 132

                              1, 1, 2, 5, 14, 42, 132

#### Example 3

If one uses a wrong argument, an error message is returned

    >> combinat::catalan(-1)

          Error: Wrong type of 1. argument (type 'Type::NonNegInt' expec\
          ted,
                 got argument '-1');
          during evaluation of 'combinat::catalan'

[Previous] [Next] [Contents]

MuPAD Combinat, an open source algebraic combinatorics package