Skip to content

Instantly share code, notes, and snippets.

@matarillo
Forked from murasesyuka/CatalanNumber.fs
Created March 22, 2017 15:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save matarillo/1eb6ea577b6726b87786915a4d02ff8d to your computer and use it in GitHub Desktop.
Save matarillo/1eb6ea577b6726b87786915a4d02ff8d to your computer and use it in GitHub Desktop.
Try F# Generics
let rec fact n =
if n = 0I then 1I
else n * fact (n-1I)
let comb n r =
let a = fact n
let b = fact r
let c = fact (n-r)
(a / (b*c))
let catalan_number n =
match n with
| n when n = 0I -> 1I
| _ -> comb (2I*n) n - comb (2I*n) (n-1I)
[<EntryPoint>]
let main argv =
let ans = [|1; 1; 2; 5; 14; 42; 132; 429; 1430; 4862; 16796; 58786; 208012; 742900; 2674440; 9694845|]
for i in 0..(ans.Length-1) do
printfn "catalan %A = %A ; %b" i (catalan_number (bigint i)) (catalan_number (bigint i) = bigint(ans.[i]))
0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment