user
|  |
| --- |
| This page uses content from **Wikipedia**. The original article was at Catalan numbers. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |

Catalan numbers are a sequence of numbers which can be defined directly:

:   C

    n
    =


    1

    n
    +
    1

    (


    2
    n
    n

    )
    =

    (
    2
    n
    )
    !

    (
    n
    +
    1
    )
    !

    n
    !

     for 
    n
    ≥
    0.
    {\displaystyle {\displaystyle C\_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ for }}n\geq 0.}}

Or recursively:

:   C

    0
    =
    1

    and


    C

    n
    +
    1
    =

    ∑

    i
    =
    0

    n

    C

    i


    C

    n
    −
    i


    for 
    n
    ≥
    0
    ;
    {\displaystyle {\displaystyle C\_{0}=1\quad {\mbox{and}}\quad C\_{n+1}=\sum \_{i=0}^{n}C\_{i}\,C\_{n-i}\quad {\text{for }}n\geq 0;}}

Or alternatively (also recursive):

:   C

    0
    =
    1

    and


    C

    n
    =

    2
    (
    2
    n
    −
    1
    )

    n
    +
    1

    C

    n
    −
    1
    ,
    {\displaystyle {\displaystyle C\_{0}=1\quad {\mbox{and}}\quad C\_{n}={\frac {2(2n-1)}{n+1}}C\_{n-1},}}

Task

Implement at least one of these algorithms and print out the first 15 Catalan numbers with each.

Memoization   is not required, but may be worth the effort when using the second method above.

Related tasks

* Catalan numbers/Pascal's triangle
* Evaluate binomial coefficients
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2015.12

The recursive formulas are easily written into a constant array, either:

```
constant Catalan = 1, { [+] @_ Z* @_.reverse } ... *;
```

or

```
constant Catalan = 1, |[\*] (2, 6 ... *) Z/ 2 .. *;


# In both cases, the sixteen first values can be seen with:
.say for Catalan[^16];
```

Output:

```
1
1
2
5
14
42
132
429
1430
4862
16796
58786
208012
742900
2674440
```