40
\$\begingroup\$

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 >= 0) is also explicitly defined as:

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 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>

\$\endgroup\$
6
  • \$\begingroup\$ Can we print/return a float rather than an integer? \$\endgroup\$
    – Alex A.
    Dec 9, 2015 at 18:11
  • \$\begingroup\$ @AlexA. This is acceptable. \$\endgroup\$ Dec 9, 2015 at 18:30
  • \$\begingroup\$ Shall there be a tag oeis? \$\endgroup\$
    – Vi.
    Dec 9, 2015 at 21:36
  • 1
    \$\begingroup\$ @Vi. There was a meta discussion about that a while back and we agreed that oeis was unnecessary \$\endgroup\$ Dec 9, 2015 at 21:37
  • \$\begingroup\$ @Vi. Here is the meta post: meta.codegolf.stackexchange.com/a/5546/8478. As for some reasoning, you can find OEIS-style challenges quite reliably with sequence and one of number or number-theory. Whether the given sequence actually is in OEIS, is completely irrelevant to the challenge. \$\endgroup\$ Dec 10, 2015 at 7:57

54 Answers 54

1
2
2
\$\begingroup\$

Oasis, 9 bytes

nxx«*n>÷1

Try it online!

Oasis is a language designed by Adnan which is specialized in sequences.

Here, we shall use the following relationship kindly provided by Stefano Sanfilippo:

Currently, this language can do recursion and closed form.

To specify that a(0)=1 is simple: just add the 1 at the end.

For example, if a sequence begins with a(0)=0 and a(1)=1, just put 10 at the end.

Unfortunately, all sequences must be 0-indexed.

nxx«*n>÷1                        stack
        1  a(0)=1

n          push n (input)        n
 x         double                2n
  x        double                4n
   «       minus 2               4n-2
    *      multiply: second      (4n-2)*a(n-1)
           argument is missing,
           so a(n-1) is used.
     n     push n (input)        (4n-2)*a(n-1) n
      >    add 1                 (4n-2)*a(n-1) n+1
       ÷   integer division      (4n-2)*a(n-1)/(n+1)
                               = ((4n-2)/(n+1))*a(n-1)
                               = ((4n+4-6)/(n+1))*a(n-1)
                               = ((4n+4)/(n+1) - 6/(n+1))*a(n-1)
                               = (4-6/(n+1))*a(n-1)

Closed-form:

10 bytes

nx!n!n>!*÷

Try it online!

nx!n!n>!*÷

n           push n (input)
 x          double
  !         factorial: stack is now [(2n)!]
   n        push n (input)
    !       factorial: stack is now [(2n)! n!]
     n      push n (input)
      >     add 1
       !    factorial: stack is now [(2n)! n! (n+1)!]
        *   multiply: stack is now [(2n)! (n!(n+1)!)]
         ÷  divide: stack is now [(2n)!/(n!(n+1)!)]
\$\endgroup\$
2
+100
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ wow r u le french? \$\endgroup\$
    – Adnan
    Dec 9, 2015 at 23:01
  • 2
    \$\begingroup\$ @Adnan XD I'm taking french, but that's about as far as it goes \$\endgroup\$ Dec 9, 2015 at 23:01
1
\$\begingroup\$

Ruby, 30 bytes

c=->n{n<1?1:c[n-1]*(4+6.0/~n)}

Thanks to xsot, saved few bytes by using complement.

Ungolfed:

c = -> n {
  n < 1 ? 1 : c[n-1]*(4+6.0/~n)
}

Usage:

> c=->n{n<1?1:c[n-1]*(4+6.0/~n)}
> c[10]
=> 16796.0
\$\endgroup\$
1
\$\begingroup\$

Maple, 18 bytes

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

Usage:

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

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.

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

TeX, 231 bytes

\newcommand{\f}[1]{\begingroup\count0=1\count1=2\count2=2\count3=0\loop\multiply\count0 by\the\count1\divide\count0 by\the\count2\advance\count1 by4\advance\count2 by1\advance\count3 by1
\ifnum\count3<#1\repeat\the\count0\endgroup}

Usage

\documentclass[12pt,a4paper]{article}
\begin{document}
\newcommand{\f}[1]{\begingroup\count0=1\count1=2\count2=2\count3=0\loop\multiply\count0 by\the\count1\divide\count0 by\the\count2\advance\count1 by4\advance\count2 by1\advance\count3 by1
\ifnum\count3<#1\repeat\the\count0\endgroup}

\newcount \i
\i = 0
\loop
\f{\the\i}
\advance \i by 1
\ifnum \i < 15 \repeat
\end{document}

enter image description here

\$\endgroup\$
1
\$\begingroup\$

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)).

\$\endgroup\$
1
\$\begingroup\$

Pyt, 1 byte

Ć

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

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ what in the world- \$\endgroup\$
    – Razetime
    Oct 5, 2020 at 8:10
1
\$\begingroup\$

Pari/GP, 17 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Factor + math.combinatorics, 28 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

GAP, 28 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
4
  • \$\begingroup\$ 67 bytes \$\endgroup\$
    – Giuseppe
    Feb 18 at 2:56
  • \$\begingroup\$ There's probably a shorter recurrence relation out there, but I'm studying for a spring exam so I'm trying not to procrastinate too much! \$\endgroup\$
    – Giuseppe
    Feb 18 at 3:03
  • 1
    \$\begingroup\$ (n+1)⋅n!⋅n! => n!⋅(n+1)!: 64 bytes (and much faster) \$\endgroup\$
    – DLosc
    Feb 18 at 17:53
  • \$\begingroup\$ Thanks for the help @Giuseppe and @DLosc. I am embarrassed that I missed n!(n+1) = (n+1)! \$\endgroup\$
    – Axuary
    Feb 18 at 18:10
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks @ThomasKwa. Where were you when I got stuck on the Bernoulli numbers question? :D \$\endgroup\$
    – Sherlock9
    Dec 9, 2015 at 18:59
0
\$\begingroup\$

Jellyfish, 16 12 bytes

p
%C+
 &
>+i

Try it online!

\$\endgroup\$
1
0
\$\begingroup\$

><>, 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.

\$\endgroup\$
0
\$\begingroup\$

Clojure, 45 bytes

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

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

\$\endgroup\$
0
\$\begingroup\$

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 )
          
\$\endgroup\$
0
\$\begingroup\$

Excel, 23 bytes

Unimaginative answer:

=COMBIN(2*A1,A1)/(A1+1)
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

Husk, 9 bytes

÷*Π¹Π→¹ΠD

Try it online!

Uses the formula in the description of the OEIS page.

0-indexed.

\$\endgroup\$
0
\$\begingroup\$

Japt, 10 bytes

È*4a6/°Y}g

Try it

Alternative

Ѫ1 àU zUÄ

Try it

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.