[Question]
  [
The ***[Catalan numbers](https://en.wikipedia.org/wiki/Catalan_number)*** ([OEIS](https://oeis.org/A000108)) 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.](http://meta.codegolf.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods) 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.](http://meta.codegolf.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods) 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](/questions/tagged/code-golf "show questions tagged '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]
## C, ~~78~~ ~~52~~ ~~39~~ ~~34~~ 33 bytes
Even more C magic (thanks xsot):
```
c(n){return!n?:(4+6./~n)*c(n-1);}
```
`?:` [is a GNU extension](https://stackoverflow.com/a/2806311).
---
This time by expanding the recurrence below (thanks xnor and Thomas Kwa):
$$
\begin{equation}
\begin{split}
C\_0 & = 1 \\
C\_n & = \frac{2 (2n - 1)}{n + 1} C\_{n - 1} \\
& = \frac{2 (2n+2-3)}{n+1} C\_{n - 1} \\
& = 2 \left(2\frac{n+1}{n+1} - \frac{3}{n+1}\right) C\_{n - 1} \\
& = \left(4 - \frac{6}{n+1}\right) C\_{n - 1}
\end{split}
\end{equation}
$$
```
c(n){return n?(4+6./~n)*c(n-1):1;}
```
`-(n+1)` is replaced by `~n`, which is equivalent in two's complement and saves 4 bytes.
---
Again as a function, but this time exploiting the following recurrence:
$$
\begin{equation}
\begin{split}
C\_0 & = 1 \\
C\_n & = \frac{2 (2n - 1)}{n + 1} \cdot C\_{n - 1}
\end{split}
\end{equation}
$$
```
c(n){return n?2.*(2*n++-1)/n*c(n-2):1;}
```
`c(n)` enters an infinite recursion for negative `n`, although it's not relevant for this challenge.
---
Since calling a function seems an acceptable alternative to console I/O:
```
c(n){double c=1,k=2;while(k<=n)c*=1+n/k++;return c;}
```
`c(n)` takes an `int` and returns an `int`.
---
Original entry:
```
main(n){scanf("%d",&n);double c=1,k=2;while(k<=n)c*=1+n/k++;printf("%.0f",c);}
```
Instead of directly calculating the definition, the formula is rewritten as:
$$
\begin{equation}
\begin{split}
\frac{1}{n + 1} {2n \choose n} &= \frac{(2n)!}{(n!)^2 \cdot (n + 1)} \\
& = \frac{2n \cdot \ldots \cdot (n + 1)}{n! \cdot (n + 1)} \\
& = \frac{1}{n + 1} \cdot \frac{\prod\_{k = 1}^n (n + k)}{\prod\_{k = 1}^n k} \\
& = \frac{1}{n + 1} \cdot \prod\_{k = 1}^n \frac{n + k}{k} \\
& = \frac{1}{n + 1} \cdot \prod\_{k = 1}^n \left(1 + \frac{n}{k}\right) \\
& = \frac{1}{n + 1} (n + 1) \prod\_{k = 2}^n \left(1 + \frac{n}{k}\right) \\
& = \prod\_{k = 2}^n \left(1 + \frac{n}{k}\right)
\end{split}
\end{equation}
$$
The formula assumes `n >= 2`, but the code accounts for `n = 0` and `n = 1` too.
In the C mess above, `n` and `k` have the same role as in the formula, while `c` accumulates the product. All calculations are performed in floating point using `double`, which is almost always a bad idea, but in this case the results are correct up to `n = 19` at least, so it's ok.
`float` would have saved 1 byte, unfortunately it's not precise enough.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 4 bytes
```
·∏§c√∑‚Äò
```
[Try it online!](http://jelly.tryitonline.net/#code=4bikY8O34oCY&input=&args=NQ)
### How it works
```
·∏§c√∑‚Äò    Left argument: z
·∏§       Compute 2z.
 c      Hook; apply combinations to 2z and z.
  √∑‚Äò    Divide the result by z+1.
```
[Answer]
## TI-BASIC, 11 bytes
```
(2Ans) nCr Ans/(Ans+1
```
Strangely, nCr has higher precedence than multiplication.
[Answer]
## CJam, 12 bytes
```
ri_2,*e!,\)/
```
[Try it online.](http://cjam.tryitonline.net/#code=cmlfMiwqZSEsXCkv&input=OA)
Beyond input 11, you'll need to tell your Java VM to use more memory. And I wouldn't actually recommend going much beyond 11. In theory, it works for any N though, since CJam uses arbitrary-precision integers.
### Explanation
CJam doesn't have a built-in for binomial coefficients, and computing them from three factorials takes a lot of bytes... so we'll have to do something better than that. :)
```
ri  e# Read input and convert it to integer N.
_   e# Duplicate.
2,  e# Push [0 1].
*   e# Repeat this N times, giving [0 1 0 1 ... 0 1] with N zeros and N ones.
e!  e# Compute the _distinct_ permutations of this array.
,   e# Get the number of permutations - the binomial. There happen to be 2n-over-n of
    e# of them. (Since 2n-over-n is the number of ways to choose n elements out of 2n, and
    e# and here we're choosing n positions in a 2n-element array to place the zeros in.)
\   e# Swap with N.
)/  e# Increment and divide the binomial coefficient by N+1.
```
[Answer]
## Python 3, 33 bytes
```
f=lambda n:0**n or(4+6/~n)*f(n-1)
```
Uses the recurrence
```
f(0) = 1
f(n) = (4-6/(n+1)) * f(n-1)
```
The base case of 0 is handled as `0**n or`, which stops as `1` when `n==0` and otherwise evaluates the recursive expression on the right. The bitwise operator `~n==-n-1` shortens the denominator and saves on parens.
Python 3 is used for its float division. Python 2 could do the same with one more byte to write `6.`.
[Answer]
# Mathematica, ~~16~~ 13 bytes
```
CatalanNumber
```
Built-ins, amirite fellas :/
Non-builtin version (21 bytes):
```
Binomial[2#,#]/(#+1)&
```
A binomial-less version (25 bytes):
```
Product[(#+k)/k,{k,2,#}]&
```
[Answer]
## J, 8 bytes
```
>:%~]!+:
```
This is a monadic train; it uses the (2x nCr x)/(x+1) formula. Try it [here](https://a296a8f7c5110b2ece73921ddc2abbaaa3c90d10.googledrive.com/host/0B3cbLoy-_9Dbb0NaSk9MRGE5UEU/index.html#code=(%3E%3A%25%7E%5D!%2B%3A)5).
[Answer]
# pl, 4 bytes
```
‚òº√ß‚ñ≤√∑
```
[Try it online.](http://pl.tryitonline.net/#code=4pi8w6filrLDtw&input=NQ)
## Explanation
In pl, functions take their arguments off the stack and push the result back onto the stack. Normally when there are not enough arguments on the stack, the function simply fails silently. However, something special happens when the amount of arguments on the stack is one off from the arity of the function -- the input variable `_` is added to the argument list:
```
‚òº√ß‚ñ≤√∑
‚òº      double: takes _ as the argument since there is nothing on the stack
 √ß     combinations: since there is only one item on the stack (and arity is 2), it adds _ to the argument list (combinations(2_,_))
  ‚ñ≤    increment last used var (_)
   √∑   divide: adds _ to the argument list again
```
In effect, this is the pseudocode:
```
divide(combinations(double(_),_),_+1);
```
[Answer]
# [Sesos](https://github.com/DennisMitchell/sesos), ~~94~~ ~~86~~ 68 bytes
8 bytes by changing the factorial-er from version 1 to version 2.
18 bytes by computing `n!(n+1)!` in one step. **Largely inspired by [Dennis' primality test algorithm](https://codegolf.stackexchange.com/a/86501/48934).**
Hexdump:
```
0000000: 16f8de a59f17 a0ebba 7f4cd3 e05f3f cf0fd0 a0ebde  ..........L.._?......
0000015: b1c1bb 76fe18 8cc1bb 76fe1c e0fbda 390fda bde3d8  ...v.....v.....9.....
000002a: 000fbe af9d1b b47bc7 cfc11c b47bc7 cff1fa e07bda  .......{.....{.....{.
000003f: 39e83e cf07                                       9.>..
```
[Try it online!](http://sesos.tryitonline.net/#code=c2V0IG51bWluCnNldCBudW1vdXQKZ2V0CmptcCxzdWIgMSxmd2QgMSxhZGQgMSxmd2QgMixhZGQgMixyd2QgMyxqbnoKZndkIDEsYWRkIDEKam1wCiAgam1wLHN1YiAxLHJ3ZCAxLGFkZCAxLHJ3ZCAxLGFkZCAxLHJ3ZCAxLGFkZCAxLGZ3ZCAzLGpuegogIHJ3ZCAxLHN1YiAxLHJ3ZCAxLHN1YiAxLHJ3ZCAxCiAgam1wLHN1YiAxLGZ3ZCAzLGFkZCAxLHJ3ZCAzLGpuegogIGZ3ZCAxCmpuegpmd2QgMwpqbXAKICBqbXAKICAgIHN1YiAxLHJ3ZCAxCiAgICBqbXAsc3ViIDEscndkIDEsYWRkIDEscndkIDEsYWRkIDEsZndkIDIsam56CiAgICByd2QgMgogICAgam1wLHN1YiAxLGZ3ZCAyLGFkZCAxLHJ3ZCAyLGpuegogICAgZndkIDMKICBqbnoKICByd2QgMQogIGptcCxzdWIgMSxqbnoKICByd2QgMQogIGptcCxzdWIgMSxmd2QgMixhZGQgMSxyd2QgMixqbnoKICBmd2QgMwpqbnogCmZ3ZCAxCmptcAogIGptcCxzdWIgMSxmd2QgMSxhZGQgMSxmd2QgMSxhZGQgMSxyd2QgMixqbnoKICBmd2QgMSxzdWIgMSxmd2QgMQogIGptcCxzdWIgMSxyd2QgMixhZGQgMSxmd2QgMixqbnoKICByd2QgMQpqbnoKcndkIDIKam1wCiAgam1wCiAgICBzdWIgMSxmd2QgMQogICAgam1wLHN1YiAxLGZ3ZCAxLGFkZCAxLGZ3ZCAxLGFkZCAxLHJ3ZCAyLGpuegogICAgZndkIDIKICAgIGptcCxzdWIgMSxyd2QgMixhZGQgMSxmd2QgMixqbnoKICAgIHJ3ZCAzCiAgam56CiAgZndkIDEKICBqbXAsc3ViIDEsam56CiAgZndkIDEKICBqbXAsc3ViIDEscndkIDIsYWRkIDEsZndkIDIsam56CiAgcndkIDMKam56IApmd2QgMQpqbXAKICBmd2QgMSxhZGQgMSxyd2QgMwogIGptcCxzdWIgMSxmd2QgMSxhZGQgMSxmd2QgMSxzdWIgMSxyd2QgMixqbnoKICBmd2QgMQogIGptcCxzdWIgMSxyd2QgMSxhZGQgMSxmd2QgMSxqbnoKICBmd2QgMQpqbnoKZndkIDEKcHV0&input=NA&debug=on)
Uses the formula `a(n) = (2n)! / (n!(n+1)!)`.
* The factorial-er: [version 1](http://sesos.tryitonline.net/#code=c2V0IG51bWluCnNldCBudW1vdXQKZ2V0CmptcCxzdWIgMSxmd2QgMSxhZGQgMSxmd2QgMSxhZGQgMSxyd2QgMixqbnoKZndkIDMKYWRkIDEKcndkIDIKam1wCiAgc3ViIDEKICBmd2QgMQogIGptcAogICAgc3ViIDEKICAgIGZ3ZCAxCiAgICBqbXAKICAgICAgc3ViIDEsZndkIDEsYWRkIDEsZndkIDEsYWRkIDEscndkIDIKICAgIGpuegogICAgZndkIDEKICAgIGptcAogICAgICBzdWIgMSxyd2QgMSxhZGQgMSxmd2QgMQogICAgam56CiAgICByd2QgMgogIGpuegogIGZ3ZCAxLGptcCxzdWIgMSxqbnoKICByd2QgMgogIGptcCxzdWIgMSxmd2QgMixhZGQgMSxyd2QgMixqbnoKICBmd2QgMgogIGptcCxzdWIgMSxyd2QgMSxhZGQgMSxyd2QgMSxhZGQgMSxmd2QgMixqbnoKICBmd2QgMgogIGptcCxzdWIgMSxyd2QgMixhZGQgMSxmd2QgMixqbnoKICByd2QgNApqbnoKZndkIDIKcHV0&input=NQ&debug=on) (in-place, constant memory), [version 2](http://sesos.tryitonline.net/#code=c2V0IG51bWluCnNldCBudW1vdXQKZ2V0CmptcAogIGptcCxzdWIgMSxmd2QgMixhZGQgMSxyd2QgMixqbnoKICBmd2QgMgogIGptcCxzdWIgMSxyd2QgMSxhZGQgMSxyd2QgMSxhZGQgMSxmd2QgMixqbnoKICByd2QgMQogIHN1YiAxCmpuegpyd2QgMgpqbXAKICBqbXAKICAgIHN1YiAxLGZ3ZCAxCiAgICBqbXAsc3ViIDEsZndkIDEsYWRkIDEsZndkIDEsYWRkIDEscndkIDIsam56CiAgICBmd2QgMQogICAgam1wLHN1YiAxLHJ3ZCAxLGFkZCAxLGZ3ZCAxLGpuegogICAgcndkIDIKICBqbnoKICBmd2QgMSxqbXAsc3ViIDEsam56LGZ3ZCAyCiAgam1wLHN1YiAxLHJ3ZCAzLGFkZCAxLGZ3ZCAzLGpuegogIHJ3ZCA0Cmpuegpmd2QgMQpwdXQ&input=NQ&debug=on) (in-place, linear memory)
* The multiplier: [here](http://sesos.tryitonline.net/#code=c2V0IG51bWluCnNldCBudW1vdXQKZ2V0CnJ3ZCAxCmdldApqbXAKICBzdWIgMQogIGZ3ZCAxCiAgam1wLHN1YiAxLGZ3ZCAxLGFkZCAxLGZ3ZCAxLGFkZCAxLHJ3ZCAyLGpuegogIGZ3ZCAxCiAgam1wLHN1YiAxLHJ3ZCAxLGFkZCAxLGZ3ZCAxLGpuegogIHJ3ZCAyCmpuegpmd2QgMwpwdXQ&input=MTIKMTM&debug=on) (in place, constant memory)
* The divider: [here](http://sesos.tryitonline.net/#code=c2V0IG51bWluCnNldCBudW1vdXQKZ2V0CmZ3ZCAyCmdldApyd2QgMgpqbXAKICBmd2QgMwogIGFkZCAxCiAgcndkIDEKICBqbXAsc3ViIDEscndkIDEsYWRkIDEscndkIDEsc3ViIDEsZndkIDIsam56CiAgcndkIDEKICBqbXAsc3ViIDEsZndkIDEsYWRkIDEscndkIDEsam56CiAgcndkIDEKam56CmZ3ZCAzCnB1dA&input=MTU2CjEy&debug=on) (does not halt if not divisible)
## Assembler
```
set numin
set numout
get
jmp,sub 1,fwd 1,add 1,fwd 2,add 2,rwd 3,jnz
fwd 1,add 1
jmp
  jmp,sub 1,rwd 1,add 1,rwd 1,add 1,rwd 1,add 1,fwd 3,jnz
  rwd 1,sub 1,rwd 1,sub 1,rwd 1
  jmp,sub 1,fwd 3,add 1,rwd 3,jnz
  fwd 1
jnz
fwd 3
jmp
  jmp
    sub 1,rwd 1
    jmp,sub 1,rwd 1,add 1,rwd 1,add 1,fwd 2,jnz
    rwd 2
    jmp,sub 1,fwd 2,add 1,rwd 2,jnz
    fwd 3
  jnz
  rwd 1
  jmp,sub 1,jnz
  rwd 1
  jmp,sub 1,fwd 2,add 1,rwd 2,jnz
  fwd 3
jnz 
fwd 1
jmp
  jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz
  fwd 1,sub 1,fwd 1
  jmp,sub 1,rwd 2,add 1,fwd 2,jnz
  rwd 1
jnz
rwd 2
jmp
  jmp
    sub 1,fwd 1
    jmp,sub 1,fwd 1,add 1,fwd 1,add 1,rwd 2,jnz
    fwd 2
    jmp,sub 1,rwd 2,add 1,fwd 2,jnz
    rwd 3
  jnz
  fwd 1
  jmp,sub 1,jnz
  fwd 1
  jmp,sub 1,rwd 2,add 1,fwd 2,jnz
  rwd 3
jnz 
fwd 1
jmp
  fwd 1,add 1,rwd 3
  jmp,sub 1,fwd 1,add 1,fwd 1,sub 1,rwd 2,jnz
  fwd 1
  jmp,sub 1,rwd 1,add 1,fwd 1,jnz
  fwd 1
jnz
fwd 1
put
```
## Brainfuck equivalent
[This Retina script](http://retina.tryitonline.net/#code=TSFgKFtmcl13ZHxhZGR8c3ViKSBcZHxqbnp8am1wfGpuZXxub3AKam1wClsKam56Cl0Kc3ViIChcZCkKJDEkKi0KYWRkIChcZCkKJDEkKisKZndkIChcZCkKJDEkKj4KcndkIChcZCkKJDEkKjwKwrYK&input=c2V0IG51bWluCnNldCBudW1vdXQKZ2V0CmptcCxzdWIgMSxmd2QgMSxhZGQgMSxmd2QgMixhZGQgMixyd2QgMyxqbnoKZndkIDEsYWRkIDEKam1wCiAgam1wLHN1YiAxLHJ3ZCAxLGFkZCAxLHJ3ZCAxLGFkZCAxLHJ3ZCAxLGFkZCAxLGZ3ZCAzLGpuegogIHJ3ZCAxLHN1YiAxLHJ3ZCAxLHN1YiAxLHJ3ZCAxCiAgam1wLHN1YiAxLGZ3ZCAzLGFkZCAxLHJ3ZCAzLGpuegogIGZ3ZCAxCmpuegpmd2QgMwpqbXAKICBqbXAKICAgIHN1YiAxLHJ3ZCAxCiAgICBqbXAsc3ViIDEscndkIDEsYWRkIDEscndkIDEsYWRkIDEsZndkIDIsam56CiAgICByd2QgMgogICAgam1wLHN1YiAxLGZ3ZCAyLGFkZCAxLHJ3ZCAyLGpuegogICAgZndkIDMKICBqbnoKICByd2QgMQogIGptcCxzdWIgMSxqbnoKICByd2QgMQogIGptcCxzdWIgMSxmd2QgMixhZGQgMSxyd2QgMixqbnoKICBmd2QgMwpqbnogCmZ3ZCAxCmptcAogIGptcCxzdWIgMSxmd2QgMSxhZGQgMSxmd2QgMSxhZGQgMSxyd2QgMixqbnoKICBmd2QgMSxzdWIgMSxmd2QgMQogIGptcCxzdWIgMSxyd2QgMixhZGQgMSxmd2QgMixqbnoKICByd2QgMQpqbnoKcndkIDIKam1wCiAgam1wCiAgICBzdWIgMSxmd2QgMQogICAgam1wLHN1YiAxLGZ3ZCAxLGFkZCAxLGZ3ZCAxLGFkZCAxLHJ3ZCAyLGpuegogICAgZndkIDIKICAgIGptcCxzdWIgMSxyd2QgMixhZGQgMSxmd2QgMixqbnoKICAgIHJ3ZCAzCiAgam56CiAgZndkIDEKICBqbXAsc3ViIDEsam56CiAgZndkIDEKICBqbXAsc3ViIDEscndkIDIsYWRkIDEsZndkIDIsam56CiAgcndkIDMKam56IApmd2QgMQpqbXAKICBmd2QgMSxhZGQgMSxyd2QgMwogIGptcCxzdWIgMSxmd2QgMSxhZGQgMSxmd2QgMSxzdWIgMSxyd2QgMixqbnoKICBmd2QgMQogIGptcCxzdWIgMSxyd2QgMSxhZGQgMSxmd2QgMSxqbnoKICBmd2QgMQpqbnoKZndkIDEKcHV0) is used to generate the brainfuck equivalent. Note that it only accepts one digit as command argument, and does not check if a command is in the comments.
```
[->+>>++<<<]>+
[[-<+<+<+>>>]<-<-<[->>>+<<<]>]>>>
[[-<[-<+<+>>]<<[->>+<<]>>>]<[-]<[->>+<<]>>>]>
[[->+>+<<]>->[-<<+>>]<]<<
[[->[->+>+<<]>>[-<<+>>]<<<]>[-]>[-<<+>>]<<<]>
[>+<<<[->+>-<<]>[-<+>]>]>
```
[Answer]
# Pyth, 8
```
/.cyQQhQ
```
[Try it online](http://pyth.herokuapp.com/?code=%2F.cyQQhQ&input=5&debug=0) or run the [Test Suite](http://pyth.herokuapp.com/?code=%2F.cyQQhQ&input=50&test_suite=1&test_suite_input=0%0A1%0A2%0A3%0A4%0A5%0A6%0A7%0A8%0A9%0A10%0A11%0A12%0A13%0A14%0A15%0A16%0A17%0A18%0A19&debug=0)
### Explanation
```
/.cyQQhQ   ## implicit: Q = eval(input())
/     hQ   ## integer division by (Q + 1)
 .c        ## nCr
   yQ      ## use Q * 2 as n
     Q     ## use Q as r
```
[Answer]
# Julia, 23 bytes
```
n->binomial(2n,n)/(n+1)
```
This is an anonymous function that accepts an integer and returns a float. It uses the basic binomial formula. To call it, give it a name, e.g. `f=n->...`.
[Answer]
## Seriously, 9 bytes
```
,;;u)œÑ‚ï£E\
```
Hex Dump:
```
2c3b3b7529e7b9455c
```
[Try it online](http://seriouslylang.herokuapp.com/link/code=2c3b3b7529e7b9452f&input=5)
Explanation:
```
,                   Read in evaluated input n
 ;;                 Duplicate it twice
   u)               Increment n and rotate it to bottom of stack
     œÑ‚ï£             Double n, then push 2n-th row of Pascal's triangle
       E            Look-up nth element of the row, and so push 2nCn
        \           Divide it by the n+1 below it.
```
[Answer]
# JavaScript (ES6), 24 bytes
Based on the [Python answer](https://codegolf.stackexchange.com/a/66141/42545).
```
c=x=>x?(4+6/~x)*c(x-1):1
```
### How it works
```
c=x=>x?(4+6/~x)*c(x-1):1
c=x=>                     // Define a function c that takes a parameter x and returns:
     x?               :1  //  If x == 0, 1.
       (4+6/~x)           //  Otherwise, (4 + (6 / (-x - 1)))
               *c(x-1)    //  times the previous item in the sequence.
```
I think this is the shortest it can get, but suggestions are welcome!
[Answer]
## Matlab, ~~35~~ 25 bytes
```
@(n)nchoosek(2*n,n)/(n+1)
```
## Octave, 23 bytes
```
@(n)nchoosek(2*n,n++)/n
```
[Answer]
# ùîºùïäùïÑùïöùïü, 3 chars / 6 bytes
```
–ú∆Ö√Ø
```
`[Try it here (Firefox only).](http://molarmanful.github.io/ESMin/interpreter.html?eval=true&input=4&code=%D0%9C%C6%85%C3%AF)`
Builtins ftw! So glad I implemented math.js early on.
# Bonus solution, 12 chars / 19 bytes
```
–ú∆° 2*√Ø,√Ø)/‚ß∫√Ø
```
`[Try it here (Firefox only).](http://molarmanful.github.io/ESMin/interpreter2.html?eval=true&input=19&code=%D0%9C%C6%A1%202*%C3%AF%2C%C3%AF%29%2F%E2%A7%BA%C3%AF)`
Ay! 19th byte!
Evaluates to pseudo-ES6 as:
```
nchoosek(2*input,input)/(input+1)
```
[Answer]
## Haskell, 27 bytes
```
g 0=1
g n=(4-6/(n+1))*g(n-1)
```
A recursive formula. There's got to be a way to save on parens...
Directly taking the product was 2 bytes longer:
```
g n=product[4-6/i|i<-[2..n+1]]
```
[Answer]
## Dyalog APL, 9 bytes
```
+‚àò1√∑‚ç®‚ä¢!+‚ç®
```
This is a monadic train; it uses the (2x nCr x)/(x+1) formula. Try it online [here](http://tryapl.org/?a=%28+%u22181%F7%u2368%u22A2%21+%u2368%29%20%u237315&run).
[Answer]
# C, ~~122~~ ~~121~~ ~~119~~ 108 bytes
```
main(j,v)char**v;{long long p=1,i,n=atoi(v[1]);for(j=0,i=n+1;i<2*n;p=(p*++i)/++j);p=n?p/n:p;printf("%d",p);}
```
I used gcc (GCC) 3.4.4 (cygming special, gdc 0.12, using dmd 0.125) to compile in a windows cygwin environment. Input comes in on the command line. It's similar to Sherlock9's Python solution but the loops are combined into one to avoid overflow and get output up to the 20th Catalan number (n=19).
[Answer]
# [Javagony](http://esolangs.org/wiki/Javagony), 223 bytes
```
public class C{public static int f(int a,int b){try{int z=1/(b-a);}catch(Exception e){return 1;}return a*f(a+1,b);}public static void main(String[]s){int m=Integer.parseInt(s[0])+1;System.out.println(f(m,2*m-1)/f(1,m)/m);}}
```
Fully expanded:
```
public class C {
    public static int f(int a,int b){
        try {
            int z=1/(b-a);
        } catch (Exception e){
            return 1;
        }
        return a*f(a+1,b);
    }
    public static void main(String[] s){
        int m=Integer.parseInt(s[0])+1;
        System.out.println(f(m,2*m-1)/f(1,m)/m);
    }
}
```
[Answer]
# R, ~~35~~ ~~28~~ 16 bytes
```
numbers::catalan
```
Edit: Use numbers package builtin.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), 6 bytes
```
Dxcr>/
```
**Explanation:**
```
Code:     Stack:               Explanation:
Dxcr>/
D         [n, n]               # Duplicate of the stack. Since it's empty, input is used.
 x        [n, n, 2n]           # Pops a, pushes a, a * 2
  c       [n, n nCr 2n]        # Pops a,b pushes a nCr b
   r      [n nCr 2n, n]        # Reverses the stack
    >     [n nCr 2n, n + 1]    # Increment on the last item
     /    [(n nCr 2n)/(n + 1)] # Divides the last two items
                               # Implicit, nothing has printed, so we print the last item
```
[Answer]
# R, 28 bytes
Not using a package, so slightly longer than a previous answer
```
choose(2*(n=scan()),n)/(n+1)
```
[Answer]
# [Oasis](http://github.com/Adriandmen/Oasis), 9 bytes
```
nxx¬´*n>√∑1
```
[Try it online!](http://oasis.tryitonline.net/#code=bnh4wqsqbj7DtzE&input=&args=MTk)
Oasis is a language designed by [Adnan](https://codegolf.stackexchange.com/users/34388/adnan) which is specialized in sequences.
Here, we shall use the following relationship kindly provided by [Stefano Sanfilippo](https://codegolf.stackexchange.com/a/66168/48934):
![](https://i.stack.imgur.com/CW9Zo.png)
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!](http://oasis.tryitonline.net/#code=bnghbiFuPiEqw7c&input=&args=MTk)
```
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)!)]
```
[Answer]
# 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](https://i.stack.imgur.com/Wckg8.png)](https://i.stack.imgur.com/Wckg8.png)
[Answer]
# Japt, 16 bytes
Even Mathematica is shorter. `:-/`
```
U*2¬™1 o √†U l /¬∞U
```
[Try it online!](http://ethproductions.github.io/japt?v=master&code=VSoyqjEgbyDgVSBsIC+wVQ==&input=Ng==)
### Ungolfed and explanation
```
U*2¬™ 1 o √†U l /¬∞ U
U*2||1 o √†U l /++U
         // Implicit: U = input number
U*2||1   // Take U*2. If it is zero, take 1.
o √†U     // Generate a range of this length, and calculate all combinations of length U.
l /++U   // Take the length of the result and divide by (U+1).
         // Implicit: output result
```
Alternate version, based on the recursive formula:
```
C=_?(4+6/~Z *C$(Z-1):1};$C(U
```
[Answer]
# [Vitsy](https://github.com/VTCAKAVSMoACE/Vitsy), 13 Bytes
```
VV2*FVF/V1+F/
V              Capture the input as a final global variable.
 V             Push it back.
  2*           Multiply it by 2
    F          Factorial.
     VF        Factorial of the input.
       /       Divide the second to top by the first.
        V1+    1+input
           F   Factorial.
            /  Divide.
```
This is a function in [Vitsy](https://github.com/VTCAKAVSMoACE/Vitsy). How to make it a program that does this, you ask? Concatenate `N`. c:
[Try it online!](http://vitsy.tryitonline.net/#code=VlYyKkZWRi9WMStGL04&input=&args=MQ)
[Answer]
# [Milky Way 1.5.14](https://github.com/zachgates7/Milky-Way), 14 bytes
```
':2K;*Ny;1+/A!
```
---
### Explanation
```
'               # read input from the command line
 :              # duplicate the TOS
  2      1      # push integer to the stack
   K            # push a Pythonic range(0, TOS) as a list
    ;   ;       # swap the TOS and the STOS
     *          # multiply the TOS and STOS
      N         # push a list of the permutations of the TOS (for lists)
       y        # push the length of the TOS
          +     # add the STOS to the TOS
           /    # divide the TOS by the STOS
            A   # push the integer representation of the TOS
             !  # output the TOS
```
or, alternatively, the *much* more efficient version:
---
# [Milky Way 1.5.14](https://github.com/zachgates7/Milky-Way), 22 bytes
```
'1%{;K¬£1+k1-6;/4+*}A!
```
---
### Explanation
```
'                      # read input from the command line
 1     1  1 6  4       # push integer to the stack
  %{  ¬£           }    # for loop
    ;        ;         # swap the TOS and the STOS
     K                 # push a Pythonic range(0, TOS) as a list
        +       +      # add the TOS and STOS
         k             # push the negative absolute value of the TOS
           -           # subtract the STOS from the TOS
              /        # divide the TOS by the STOS
                 *     # multiply the TOS and the STOS
                   A   # push the integer representation of the TOS
                    !  # output the TOS
```
---
## Usage
```
python3 milkyway.py <path-to-code> -i <input-integer>
```
[Answer]
# Clojure/ClojureScript, 53 bytes
```
(defn c[x](if(= 0 x)1(*(c(dec x))(- 4(/ 6(inc x))))))
```
Clojure can be pretty frustrating to golf in. It's very pithy while still being very readable, but some of the niftier features are really verbose. `(inc x)` is more idiomatic than `(+ x 1)` and "feels" more concise, but doesn't actually save characters. And writing chains of operations is nicer as `(->> x inc (/ 6) (- 4))`, but it's actually longer than just doing it the ugly way.
[Answer]
# 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
```
[Answer]
# Prolog, 42 bytes
Using recursion is almost always the way to go with Prolog.
**Code:**
```
0*1.
N*X:-M is N-1,M*Y,X is(4-6/(N+1))*Y.
```
**Example:**
```
19*X.
X = 1767263190.0
```
Try it online [here](http://swish.swi-prolog.org/p/qICyHIzl.pl)
]