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


 
class
	APPLICATION
 
create
	make
 
feature {NONE}
 
	make
		do
			across
				0 |..| 14 as c
			loop
				io.put_double (nth_catalan_number (c.item))
				io.new_line
			end
		end
 
	nth_catalan_number (n: INTEGER): DOUBLE
			--'n'th number in the sequence of Catalan numbers.
		require
			n_not_negative: n >= 0
		local
			s, t: DOUBLE
		do
			if n = 0 then
				Result := 1.0
			else
				t := 4 * n.to_double - 2
				s := n.to_double + 1
				Result := t / s * nth_catalan_number (n - 1)
			end
		end
 
end
 
 
 