# Catalan Numbers

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.

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

• Can we print/return a float rather than an integer? – Alex A. Dec 9 '15 at 18:11
• @AlexA. This is acceptable. – a spaghetto Dec 9 '15 at 18:30
• Shall there be a tag oeis? – Vi. Dec 9 '15 at 21:36
• @Vi. There was a meta discussion about that a while back and we agreed that oeis was unnecessary – a spaghetto Dec 9 '15 at 21:37
• @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. – Martin Ender Dec 10 '15 at 7:57

## C, 78523934 33 bytes

Even more C magic (thanks xsot):

c(n){return!n?:(4+6./~n)*c(n-1);}

This time by expanding the recurrence below (thanks xnor and Thomas Kwa):

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:

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:

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.

• I can't test this now but I think you can shorten it further: c(n){return!n?:(4+6./~n)*c(n-1);} – xsot Dec 10 '15 at 1:19
• Thanks @xsot, I didn't know ?:! Apparently, it's a GNU C extension but I think it still qualifies. – Stefano Sanfilippo Dec 10 '15 at 10:27

# Jelly, 4 bytes

Ḥc÷‘

Try it online!

### How it works

Ḥc÷‘    Left argument: z

Ḥ       Compute 2z.
c      Hook; apply combinations to 2z and z.
÷‘    Divide the result by z+1.
• What does "hook' mean? How does c get 2z and z as its arguments? – xnor Dec 9 '15 at 18:42
• @xnor A hook means functions evaluated like f(x,g(x)). When there's a dyadic function followed by another dyadic function, the parser evaluates the first one as a hook. – lirtosiast Dec 9 '15 at 18:46
• @Dennis Is that really 4 bytes? With those non-ASCII characters, mothereff.in/byte-counter says 9 bytes – Luis Mendo Dec 9 '15 at 20:12
• @LuisMendo it's probably a different encoding – undergroundmonorail Dec 9 '15 at 20:12
• @LuisMendo Jelly uses its own, custom encoding default, where each character is a single byte. With UTF-8, the source code is indeed 9 bytes long. – Dennis Dec 9 '15 at 20:16

## CJam, 12 bytes

ri_2,*e!,\)/

Try it online.

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.
• This is really cool. +1 – a spaghetto Dec 9 '15 at 18:31

## Dyalog APL, 9 bytes

+∘1÷⍨⊢!+⍨

This is a monadic train; it uses the (2x nCr x)/(x+1) formula. Try it online here.

# C, 122121119 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).

• You can remove the space after the comma in the main definition to save a byte. – Alex A. Dec 9 '15 at 19:25
• Nice, I'll edit the post now – cleblanc Dec 9 '15 at 20:24
• You can save 2 more bytes with char**v rather than char *v[]. (The space before * is not needed, and the types are equivalent.) – Mat Dec 9 '15 at 21:02
• Sure enough, that works great. Thanks Mat – cleblanc Dec 9 '15 at 21:10
• This uses some stuff from the tips page to shorten it. Note though that for Ideone I hardcoded a value for n. – FryAmTheEggman Dec 9 '15 at 21:53

# 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);
}
}
• Esolangs entry doesn't matter - as long as you use an interpreter made before the contest, it's all good and valid. – Addison Crump Dec 28 '15 at 14:52
• Ain't gonna win anyway^^ – flawr Dec 28 '15 at 15:09
• It is java, so yeah. – Rɪᴋᴇʀ Dec 28 '15 at 15:23
• @Riker Well, it's worse than Java. – Jakob Aug 20 '17 at 17:21

# Japt, 16 bytes

Even Mathematica is shorter. :-/

U*2ª1 o àU l /°U

Try it online!

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

# 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. How to make it a program that does this, you ask? Concatenate N. c:

Try it online!

# Milky Way 1.5.14, 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, 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>

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

# 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

• Are you redefining the * symbol here? – Paŭlo Ebermann Dec 12 '15 at 17:15
• @PaŭloEbermann not exactly. I'm defining a new dyadic predicate called *. I can still use the regular arithmetic one. In the program above M*Y is my defined predicate while (4-6/(N+1))*Y is regular multiplication. – Emigna Dec 12 '15 at 17:27
• It's slightly shorter than writing it as p(X,Y):- which is nice for code golf. – Emigna Dec 12 '15 at 17:29

# Octave, 22 bytes

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

## Ceylon, 60 bytes

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

This works up to C30, as Ceylon's Integers are signed 64-bit numbers (C31 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

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

# R, 3528 16 bytes

numbers::catalan

Edit: Use numbers package builtin.

# 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
/      % divide

# 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

# R, 28 bytes

Not using a package, so slightly longer than a previous answer

choose(2*(n=scan()),n)/(n+1)