Catalan Numbers

Question

The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics.

The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as [[][]]; formally defined as a string using two characters a and b such that any substring starting from the beginning has number of a characters greater than or equal to number of b characters, and the entire string has the same number of a and b characters) with length 2n. The nth Catalan number (for \$n\ge0\$) is also explicitly defined as: $$C_n=\frac1{n+1}\binom{2n}n$$ Starting from \$n=0\$, the first 20 Catalan numbers are:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190...

Challenge

Write a full program or function that takes a non-negative integer n via STDIN or an acceptable alternative, and outputs the nth Catalan number. Your program must work at minimum for inputs 0-19.

I/O

Input

Your program must take input from STDIN, function arguments or any of the acceptable alternatives per this meta post. You can read the inputted number as its standard decimal represention, unary representation, or bytes.

• If (and only if) your language cannot take input from STDIN or any acceptable alternative, it may take input from a hardcoded variable or suitable equivalent in the program.

Output

Your program must output the nth Catalan number to STDOUT, function result or any of the acceptable alternatives per this meta post. You can output the Catalan number in its standard decimal representation, unary representation or bytes.

The output should consist of the approriate Catalan number, optionally followed by one or more newlines. No other output can be generated, except constant output of your language's interpreter that cannot be suppressed (such as a greeting, ANSI color codes or indentation).

---

This is not about finding the language that is the shortest. This is about finding the shortest program in every language. Therefore, I will not accept an answer.

In this challenge, languages newer than the challenge are acceptable as long as they have an implementation. It is allowed (and even encouraged) to write this interpreter yourself for a previously unimplemented language. Other than that, all the standard rules of code-golf must be obeyed. Submissions in most languages will be scored in bytes in an appropriate preexisting encoding (usually UTF-8). Note also that built-ins for calculating the nth Catalan number are allowed.

Catalog

The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

## Language Name, N bytes

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

## Ruby, <s>104</s> <s>101</s> 96 bytes

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

## Perl, 43 + 2 (-p flag) = 45 bytes

You can also make the language name a link which will then show up in the snippet:

## [><>](http://esolangs.org/wiki/Fish), 121 bytes

<style>body { text-align: left !important} #answer-list { padding: 10px; width: 290px; float: left; } #language-list { padding: 10px; width: 290px; float: left; } table thead { font-weight: bold; } table td { padding: 5px; }</style><script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="language-list"> <h2>Shortest Solution by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr> </thead> <tbody id="languages"> </tbody> </table> </div> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr> </thead> <tbody id="answers"> </tbody> </table> </div> <table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr> </tbody> </table><script>var QUESTION_ID = 66127; var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe"; var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk"; var OVERRIDE_USER = 12012; var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page; function answersUrl(index) { return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER; } function commentUrl(index, answers) { return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER; } function getAnswers() { jQuery.ajax({ url: answersUrl(answer_page++), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { answers.push.apply(answers, data.items); answers_hash = []; answer_ids = []; data.items.forEach(function(a) { a.comments = []; var id = +a.share_link.match(/\d+/); answer_ids.push(id); answers_hash[id] = a; }); if (!data.has_more) more_answers = false; comment_page = 1; getComments(); } }); } function getComments() { jQuery.ajax({ url: commentUrl(comment_page++, answer_ids), method: "get", dataType: "jsonp", crossDomain: true, success: function (data) { data.items.forEach(function(c) { if (c.owner.user_id === OVERRIDE_USER) answers_hash[c.post_id].comments.push(c); }); if (data.has_more) getComments(); else if (more_answers) getAnswers(); else process(); } }); } getAnswers(); var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/; var OVERRIDE_REG = /^Override\s*header:\s*/i; function getAuthorName(a) { return a.owner.display_name; } function process() { var valid = []; answers.forEach(function(a) { var body = a.body; a.comments.forEach(function(c) { if(OVERRIDE_REG.test(c.body)) body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>'; }); var match = body.match(SCORE_REG); if (match) valid.push({ user: getAuthorName(a), size: +match[2], language: match[1], link: a.share_link, }); else console.log(body); }); valid.sort(function (a, b) { var aB = a.size, bB = b.size; return aB - bB }); var languages = {}; var place = 1; var lastSize = null; var lastPlace = 1; valid.forEach(function (a) { if (a.size != lastSize) lastPlace = place; lastSize = a.size; ++place; var answer = jQuery("#answer-template").html(); answer = answer.replace("{{PLACE}}", lastPlace + ".") .replace("{{NAME}}", a.user) .replace("{{LANGUAGE}}", a.language) .replace("{{SIZE}}", a.size) .replace("{{LINK}}", a.link); answer = jQuery(answer); jQuery("#answers").append(answer); var lang = a.language; lang = jQuery('<a>'+lang+'</a>').text(); languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang.toLowerCase(), user: a.user, size: a.size, link: a.link}; }); var langs = []; for (var lang in languages) if (languages.hasOwnProperty(lang)) langs.push(languages[lang]); langs.sort(function (a, b) { if (a.lang_raw > b.lang_raw) return 1; if (a.lang_raw < b.lang_raw) return -1; return 0; }); for (var i = 0; i < langs.length; ++i) { var language = jQuery("#language-template").html(); var lang = langs[i]; language = language.replace("{{LANGUAGE}}", lang.lang) .replace("{{NAME}}", lang.user) .replace("{{SIZE}}", lang.size) .replace("{{LINK}}", lang.link); language = jQuery(language); jQuery("#languages").append(language); } }</script>

Answer 1

Octave, 22 bytes

@(n)prod(4-6./(2:n+1))

Answer 2

Ceylon, 60 bytes

Integer c(Integer n)=>(1:n).fold(1)((p,i)=>p*(n+i)/i)/(n+1);

This works up to C₃₀, as Ceylon's Integers are signed 64-bit numbers (C₃₁ has overflow, will be calculated as -4050872099593203).

I don't know if Ceylon has any built-in higher mathematical functions, but then importing the right package would probably longer than just calculating this by foot.

// Catalan number C_n
//
// Question:  http://codegolf.stackexchange.com/q/66127/2338
// My answer: http://codegolf.stackexchange.com/a/66425/2338

Integer c(Integer n) =>
        // sequence of length n, starting at 1.
        (1:n)
        // starting with 1, for each element i, multiply the result
        // of the previous step by (n+i) and then divide it by i.
    .fold(1)((p, i) => p * (n + i) / i)
        // divide the result by n+1.
        / (n + 1);

Answer 3

MATL, 8 bytes

2*GXnGQ/

Try it online!

Explanation

2*     % take number n as input and multiply by 2
G      % push input again
Xn     % compute "2*n choose n"
G      % push input again
Q      % add 1
/      % divide

Answer 4

Pari/GP, 17 bytes

n->(2*n)!/n!/n++!

Try it online!

Answer 5

Vyxal r, 6 5 bytes

I had to use the r flag. It's only useful once in a blue moon.

‹?dƈ/

Formula: \$\huge{\frac{{2n \choose n-1}}{n}}\$

Explanation:

‹       decrement n
 ?      push n again
  d     double n
   ƈ    push 2n choose n-1 (because reversed)
    /   divide by n

Try it Online!

Answer 6

tinylisp, 63 bytes

(load library
(d C(q((N)(i N(/(*(C(dec N))(s(* 4 N)2))(inc N))1

Try it online!

Explanation

Uses one of the recurrence relations from Stefano Sanfilippo's C answer:

$$ \begin{align} C_0 & = 1 \\ C_n & = C_{n-1} \cdot \frac{4n-2}{n+1} \end{align} $$

(d C(q((N)(i N(/(*(C(dec N))(s(* 4 N)2))(inc N))1
(d C                                               Define C
    (q((N)                                         as a function of N:
          (i N                                      If N is nonzero:
              (/                               )     Divide
                (*                     )              the product of
                  (C(dec N))                          a recursive call with N-1
                            (s(* 4 N)2)               and (4*N)-2
                                        (inc N)      by N-1
                                                1   Else, return 1

Answer 7

Brachylog, 15 bytes

×₂{g{b|~b}ⁱ⁾Ė}ᶜ

Try it online!

Effectively brute forces all Dyck words of length \$2n\$. I don't know that an adaptation of one of the formulas can't be shorter, but my handful of (failed) attempts have all been roughly this length.

  {          }ᶜ    Count the number of possible ways to:
          ⁱ        iterate
   g       ⁾       starting with the empty list
×₂         ⁾       2n times,
     b             removing the first element
    { |~b}         or adding an element
            Ė      such that the end result is the empty list.

Answer 8

Python 3, 83 63 62 55 bytes

With thanks to Thomas Kwa.

f=lambda x:x<1or x*f(x-1)
c=lambda n:f(2*n)/f(n)/f(n+1)

f is the factorial function. c returns what is equivalent to 2*n C n divided by n+1.

Answer 9

Jolf, 15 13 bytes

Try it here: ze link. You know what? I almost implemented a built-in. I just didn't have time. Le sigh. Also, there's a bug with my combination code, so I have to implement it with permutations. >_< I'm now also pretty glad I didn't add comments.

//mk*2jjm!jhj

With permutation (9 bytes; invalid, as I fixed this after the challenge was posted):

/mK*2jjhj

With built-in (3 bytes; implemented after challenge :P. I take off my hat to @FlagAsSpam.):

m$j

Answer 10

Maple, 18 bytes

(2*n)!/((n+1)!*n!)

Usage:

> f := n->(2*n)!/((n+1)!*n!);
> f(19);
  1767263190
  

Answer 11

Python 2, 92 bytes

(lambda f:lambda n:f(2*n)/f(n)/f(n+1))((lambda r:r(r))(lambda r:lambda x:x<1or x*r(r)(x-1)))

Ideone it!

This answer purely serves to demonstrate the power of lambdas.

Answer 12

Alice, 16 bytes

/o
\i@/..2*~C~h:

Try it online!

Explanation

This is a basic framework for arithmetic programs to read and write integer I/O and process them in Cardinal mode:

/o
\i@/...

As for the actual computation, I'm using the usual formula given in the challenge:

..   Make two copies of the input.
2*   Double one copy.
~    Swap it with another copy.
C    Compute the binomial coefficient (2n,n).
~    Swap with the third copy.
h    Increment.
:    Divide to compute C_n = (2n,n)/(n+1)

Answer 13

Brain-Flak, 78 bytes

(([{}])<(({}){}){({}()<(())<>{({}({})<>)<>}>)}><>){({}()<{}>)}{}({}[{}]<>{}{})

Try it online!

Computes the first 2n rows of Pascal's triangle, then returns ((2n-1) C n) - ((2n-1) C (n+1)).

Answer 14

Pyt, 1 byte

Ć

Gets the input n implicity, then uses a builtin to get the nth Catalan number

Try it online!

Answer 15

Factor + math.combinatorics, 28 bytes

[| n | n 2 * n 1 - nCk n / ]

Try it online!

Answer 16

GAP, 28 bytes

c:=n->Binomial(2*n,n)/(n+1);

Try it online!

Answer 17

tinylisp, 72 67 64 bytes

-5 bytes thanks to @Giuseppe -3 bytes thanks to @DLosc

(load library
(d F factorial
(d g(q((n)(/(F(+ n n))(F n)(F(+ n 1

Try it online!

Answer 18

Nekomata, 6 bytes

+$Ç$→/

Attempt This Online!

+$Ç$→/
+       Add the input with itself
 $      Swap
  Ç     Binomial coefficient
   $    Swap
    →   Increment
     /  Divide

---

Nekomata + -n, 12 bytes

+Ø$ᵑ{ᵉçt?}Ø=

Attempt This Online!

A port of @Unrelated String's Brachylog answer.

+Ø$ᵑ{ᵉçt?}Ø=
 Ø$             Starting from the empty list
+  ᵑ{    }      Apply the following function 2*input times
     ᵉç             Prepend zero
       t?           Or drop the first element
          Ø=    Check if the result is empty

The -n flag counts the number of possible results.

Answer 19

Jellyfish, 16 12 bytes

p
%C+
 &
>+i

Try it online!

Answer 20

><>, 29+2 = 31 bytes

:1+$?!\:2-
$/?=1l<*-$4,$6
;\n

Requires the input to be present on the stack at program start, so +2 bytes for the -v flag. Try it online!

Uses the algorithm presented in Stefano Sanfilippo's answer (linky).

The first line compiles n+1, n, n-1, ... , 2, 1 on the stack. The second line, running backwards, computes C(n) = (4 - (6 / (n+1)) * C(n-1). Each iteration reduces the size of the stack by 1, so the remaining number is output when the length of the stack is 1.

Answer 21

Clojure, 45 bytes

#(apply *(for[k(range 2(inc %))](/(+ % k)k)))

Uses the direct formula instead of recursion. Luckily * with zero arguments returns one :)

Answer 22

cQuents, 13 bytes

f2$)/(f$+1)f$

1-indexed. Try it online!

Explanation

:                 Implicit; sets mode to sequence
                  Given input n, output nth term in sequence; otherwise, output sequence
                  Each term in the sequence is equal to:
 f2$)             Factorial (2 * current)
     /            Divided by
      (        )  Group (implicit )
       f$+1)      Factorial (current + 1)
                  Implicit multiplication
            f$)   Factorial (current, implicit )
          

Answer 23

Excel, 23 bytes

Unimaginative answer:

=COMBIN(2*A1,A1)/(A1+1)

Answer 24

Lua, 86 bytes

c=setmetatable({[0]=1},{__index=function(c,n)c[n]=c[n-1]*(4-(6/(n+1)))print(c[n])end})

Try it online!

Answer 25

Husk, 9 bytes

÷*Π¹Π→¹ΠD

Try it online!

Uses the formula in the description of the OEIS page.

0-indexed.

Answer 26

Japt, 10 bytes

È*4a6/°Y}g

Try it

Alternative

Ѫ1 àU zUÄ

Try it

Answer 27

Thunno 2, 6 bytes

Ḍscs⁺÷

Attempt This Online!

Explanation

Ḍscs⁺÷  # Implicit input   ->  n
Ḍ       # Double           ->  2n
 sc     # nCr with input   ->  (2n)C(n)
   s⁺   # Increment input  ->  (2n)C(n), n+1
     ÷  # Divide           ->  ((2n)C(n)) / (n+1)
        # Implicit output