Catalan numbers for triangulations gambler’s ruin binary…

July 27, 2015

(This article was first published on isomorphismes, and kindly contributed to R-bloggers)

Catalan numbers for

  • triangulations
  • gambler’s ruin
  • binary trees
  • trees

…from the Flajolet/Sedgewick coursera analysis of algorithms

Noncrossing partitions 5.svg

in R:

catalan <- function(n) {
    if(n<=1) 1
    else lapply(1:n,
        FUN=function(k) catalan(k-1) * catalan(n-k) ) %>% unlist %>% sum

(This is slow above catalan(10) though, so here’s a memoised version. Then if you want to run above catalan(250) you’ll need to adjust options(expressions=5e3) to something higher; otherwise the nesting of calls goes too deep.)

To leave a comment for the author, please follow the link and comment on their blog: isomorphismes. offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...

If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers


Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)