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


 
  [Calculation of Catalan numbers.
   EDSAC program, Initial Orders 2.]
 
  [Define where to store the list of Catalan numbers.]
            T   54 K  [store address in location 54, so that values
                       are accessed by code letter C (for Catalan)]
            P  200 F  [<------ address here]
 
  [Modification of library subroutine P7.
   Prints signed integer up to 10 digits, right-justified.
   54 storage locations; working position 4D.
   Must be loaded at an even address.
   Input: Number is at 0D.]
            T   56 K
  GKA3FT42@A47@T31@ADE10@T31@A48@T31@SDTDH44#@NDYFLDT4DS43@TF
  H17@S17@A43@G23@UFS43@T1FV4DAFG50@SFLDUFXFOFFFSFL4FT4DA49@T31@
  A1FA43@G20@XFP1024FP610D@524D!FO46@O26@XFO46@SFL8FT4DE39@
 
     [Main routine]
            T  120 K  [load at 120]
            G      K  [set @ (theta) to load address]
     [Variables]
      [0]   P      F  [index of Catalan number]
     [Constants]
      [1]   P    7 D  [maximum index required]
      [2]   P      D  [single-word 1]
      [3]   P    2 F  [to change addresses by 2]
      [4]   H     #C  [these 3 are used to manufacture EDSAC orders]
      [5]   T     #C
      [6]   V     #C
      [7]   K 4096 F  [(1) add to change T order into H order
                       (2) teleprinter null]
      [8]   #      F  [figures shift]
      [9]   !      F  [space]
     [10]   @      F  [carriage return]
     [11]   &      F  [line feed]
 
           [Enter with acc = 0]
     [12]   O    8 @  [set teleprinter to figures]
            T    4 D  [clear 5F and sandwich bit]
            A    2 @  [load single-word 1]
            T    4 F  [store as double word at 4D; clear acc]
           [Here with index in acc, Catalan number in 4D]
     [16]   U      @  [store index]
            L    1 F  [times 4 by shifting]
            A    5 @  [make T order to store Catalan number]
            U   27 @  [plant in code]
            A    7 @  [make H order with same address]
            U   45 @  [plant in code]
            S   47 @  [make A order with same address]
            T   34 @  [plant in code]
            A    6 @  [load V order for start of list]
            T   46 @  [plant in code]
            A    4 D  [Catalan number from temp store]
     [27]   T     #C  [store in list (manufactured order)]
            T      D  [clear 1F and sandwich bit]
            A      @  [load single-word index]
            T      F  [store as double word at 0D]
     [31]   A   31 @  [for return from print subroutine]
            G   56 F  [print index]
            O    9 @  [followed by space]
     [34]   A     #C  [load Catalan number (manufactured order)]
            T      D  [to 0D for printing]
     [36]   A   36 @  [for return from print subroutine]
            G   56 F  [print Catalan number]
            O   10 @  [followed by new line]
            O   11 @
            T    4 D  [clear partial sum]
            A      @  [load index]
            S    1 @  [reached the maximum?]
            E   64 @  [if so, jump to exit]
            [Inner loop to compute sum of products C{i}*C(n-1}]
     [44]   T      F  [clear acc]
     [45]   H     #C  [C{n-i} to mult reg (manufactured order)]
     [46]   V     #C  [acc := C{i}*C{n-i} (manufactiured order)]
           [Multiply product by 2^34 (see preamble). The 'L F' order is
            also exploited above to convert an H order into an A order.]
     [47]   L      F  [shift acc left by 13 (the maximum available)]
            L      F  [shift 13 more]
            L   64 F  [shift 8 more, total 34]
            A    4 D  [add partial sum]
            T    4 D  [update partial sum]
            A   46 @  [inc i in V order]
            A    3 @
            T   46 @
            A   45 @  [dec (n - i) in H order]
            S    3 @
            U   45 @
            S    4 @  [is (n - i) now negative?]
            E   44 @  [if not, loop back]
           [Here with latest Catalan number in temp store 4D]
            T      F  [clear acc]
            A      @  [load index]
            A    2 @  [add 1]
            E   16 @  [back to start of outer loop]
     [64]   O    7 @  [exit; print null to flush teleprinter buffer]
            Z      F  [stop]
            E   12 Z  [define entry point]
            P      F  [acc = 0 on entry]
 