Catalan numbers

You are encouraged to solve this task according to the task description, using any language you may know.


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 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 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 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


 
report z_catalan_numbers.
 
class catalan_numbers definition.
  public section.
    class-methods:
      get_nth_number
        importing
          i_n                     type int4
        returning
          value(r_catalan_number) type int4.
endclass.
 
class catalan_numbers implementation.
  method get_nth_number.
    r_catalan_number = cond int4(
      when i_n eq 0
      then 1
      else reduce int4(
        init
          result = 1
          index = 1
        for position = 1 while position <= i_n
        next
          result = result * 2 * ( 2 * index - 1 ) div ( index + 1 )
          index = index + 1 ) ).
  endmethod.
endclass.
 
start-of-selection.
  do 15 times.
    write / |C({ sy-index - 1 }) = { catalan_numbers=>get_nth_number( sy-index - 1 ) }|.
  enddo.
 