Motzkin Numbers

MATL, 13 14 bytes

i-2/t.5+hH4Zh

Example:

>> matl i-2/t.5+hH4Zh
> 6
51

EDIT (June 16, 2017): you can try it online! Note also that in modern versions of the language (that post-date this challenge) the i could be removed.

Explanation

Pretty straightforward, using the equivalence (see equation (10)) with the hypergeometric function:

From the definition of the hypergeometric function

it's clear that the order of the first two arguments can be interchanged, which saves one byte.

i         % input                                                   
-2/       % divide by -2
t.5+      % duplicate and add 0.5
h         % horizontal concatenation into a vector                               
H         % number 2
4         % number literal                                          
Zh        % hypergeometric function with three inputs (first input is a vector)

Retina, 59 58 bytes

+`(\D*)1(1*)
:$1<$2:$1>$2:$1_$2:
:(_|()<|(?<-2>)>)+:(?!\2)

Takes input in unary. Input 7 (i.e. 1111111) takes quite a while but still completes in less than a minute. I wouldn't go much further than that.

Try it online.

Explanation

A different characterisation of the Motzkin numbers is the number of strings of three different characters, where two of them are correctly balanced (hence the close relation to Catalan numbers, which are the same without the third character which is independent of the balancing).

.NET's balancing groups are pretty good at detecting correctly matched strings, so we simply generate all strings of length N (using _, < and > as the three characters) and then we count how many of those are correctly balanced. E.g. for N = 4 the valid strings are:

____
__<>
_<_>
_<>_
<__>
<_>_
<>__
<<>>
<><>

Compared with the definition in the challenge, _ corresponds to a (1,0) step, < to (1,1) and > to (1,-1).

As for the actual code, the : is used as a separator between the different strings. The second regex is just a golfed form of the standard .NET regex for balanced strings.

Something to note is that there is only a single : inserted between strings in each step, but the second regex matches a leading and a trailing : (and since matches cannot overlap, this means that adjacent strings generated from one template in the last step cannot both match). However, this is not a problem, because at most one of those three can ever match:

• If the string ending in _ matches, the prefix without that _ is already balanced correctly, and < or > would throw off that balance.
• If the string ending in > matches, the string is balanced with that >, so _ or < would throw off that balance.
• Strings ending in < can never be balanced.

Python 2, 51 bytes

M=lambda n:n<1or sum(M(k)*M(n-2-k)for k in range(n))

Uses the formula from Mathworld

Saves chars by putting the M[n-1] term into the summation as k=n-1, which gives M[-1]*M[n-1], with M[-1]=1 as part of the initial condition.

Edit: One char shorter writing the sum recursively:

M=lambda n,k=0:n<1or k<n and M(k)*M(n-2-k)+M(n,k+1)

Other approaches that turned out longer:

M=lambda n,i=0:n and(i>0)*M(n-1,i-1)+M(n-1,i)+M(n-1,i+1)or i==0
M=lambda n:+(n<2)or(3*~-n*M(n-2)+(n-~n)*M(n-1))/(n+2)