[Question]
  [
The nth [Motzkin Number](http://mathworld.wolfram.com/MotzkinNumber.html) is the number of paths from (0, 0) to (n, 0) where each step is of the form (1, -1), (1, 0) or (1, 1), and the path never goes below y = 0.
Here's an illustration of these paths for n = 1, 2, 3, 4, from the above link:
[![Motzkin numbers](https://i.stack.imgur.com/wWeee.gif)](https://i.stack.imgur.com/wWeee.gif)
The desired sequence is [OEIS A001006](https://oeis.org/A001006). OEIS has some other characterizations of the sequence.
---
You will be given a positive integer n as input. You should output the nth Motzkin Number.
Here are Motzkin numbers 1 to 10:
```
1, 2, 4, 9, 21, 51, 127, 323, 835, 2188
```
---
All standard input and output methods are allowed. [Standard loopholes](http://meta.codegolf.stackexchange.com/questions/1061/loopholes-that-are-forbidden-by-default) apply.
This is code golf. Fewest bytes wins.
  
[Answer]
# [MATL](https://esolangs.org/wiki/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!**](https://tio.run/##y00syfn/P1PXSL9Ez1Q7w8MkKuP/fzMA) 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](http://mathworld.wolfram.com/MotzkinNumber.html) (see equation (10)) with the [hypergeometric function](https://en.wikipedia.org/wiki/Hypergeometric_function):
$$M\_n = {}\_2F\_1 \left( \frac {1-n} 2, -\frac n 2 ; 2 ;4 \right)$$
From the definition of the hypergeometric function
$${}\_2F\_1(a,b; c; z) = \sum ^ \infty \_ {n=0} \frac {(a)\_n (b)\_n} {(c)\_n} \frac {z^n} {n!}$$
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)
```
[Answer]
## [Retina](https://github.com/mbuettner/retina), ~~59~~ 58 bytes
```
+`(\D*)1(1*)
:$1<$2:$1>$2:$1_$2:
:(_|()<|(?<-2>)>)+:(?!\2)
```
Takes input in [unary](http://meta.codegolf.stackexchange.com/questions/5343/can-numeric-input-output-be-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.](http://retina.tryitonline.net/#code=K2AoXEQqKTEoMSopCjokMTwkMjokMT4kMjokMV8kMjoKOihffCgpPHwoPzwtMj4pPikrOig_IVwyKQ&input=MTExMTE)
### 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](https://stackoverflow.com/a/17004406/1633117).
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.
[Answer]
## 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
[![enter image description here](https://i.stack.imgur.com/SmW6i.gif)](https://i.stack.imgur.com/SmW6i.gif)
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)
```
[Answer]
# Pyth, 15 bytes
```
Ls*V+KyMb1+t_K1
```
This defines a function `y`. Try it online: [Demonstration](https://pyth.herokuapp.com/?code=Ls%2aV%2BKyMb1%2Bt_K1%0Ay1%0Ay2%0Ay3%0Ay10%0Ay100&debug=0)
### Explanation:
Let `y[n]` be the `n`-th Motzkin Number. I calculate `y[n]` with the formula 
```
y[n] = dot product of (y[0], ..., y[n-1], 1) and (y[n-2], ..., y[0], 1)
```
Notice that the first vector is larger than the second one (except when calculating `y[0]`). When this is the case, than Pyth automatically ignores the 1 at the end of the first vector, so that both vectors are of equal length. 
```
Ls*V+KyMb1+t_K1
L                 define a function y(b), which returns:
      yMb            compute the list [y[0], y[1], ..., y[b-1]]
     K               assign it to K
  *V                 vectorized multiplication of
    +K   1             * K with a 1 at the end
          +t_K1        * reverse(K), remove the first element, and append 1
 s                   return the sum (dot product)
```
This formula is a variation of one of the formulas listed on OEIS. It may be a little bit stupid. Because of the 1 at the end of the first vector (which make the lengths unequal), I don't actually have to give the recursion a base case. And I had hopes, that the two `+...1`s can be golfed somehow. Turns out I can't. 
You can define a similar recursion with a dot product of equal length vectors and define the base case `y[0] = 1` with with the same byte count. 
[Answer]
## CJam (20 bytes)
```
.5X]{__W%.*:++}qi*W=
```
[Online demo](http://cjam.aditsu.net/#code=.5X%5D%7B__W%25.*%3A%2B%2B%7Dqi*W%3D&input=10)
As Mego noted in the comments on the question, this is very closely related to the Catalan numbers: change the `.5` to `1` and offset the index by one (or simply remove the `.5` entirely and leave the index unchanged) to get Catalan numbers.
The recurrence used is
> 
> a(n+2) - a(n+1) = a(0)\*a(n) + a(1)\*a(n-1) + ... + a(n)\*a(0). [Bernhart]
> 
> 
> 
from the OEIS page. The corresponding recurrence for the [Catalan numbers](https://oeis.org/A000108) is listed as
> 
> a(n) = Sum\_{k=0..n-1} a(k)a(n-1-k).
> 
> 
> 
[Answer]
## Seriously, 21 bytes
```
,;╗r`;τ╜█@;u@τ╣║\*`MΣ
```
Borrows some code from [quintopia's Catalan Numbers solution](https://codegolf.stackexchange.com/a/66150/45941), specifically the improvement I made in the comments.
I use the following formula:
[![motzkin formula](https://i.stack.imgur.com/kw3LZ.png)](https://i.stack.imgur.com/kw3LZ.png)
Since `nCk` is 0 for `k > n`, I sum all the way to `n-1`, since those values will all be 0 and thus do not affect the sum.
[Try it online](http://seriouslylang.herokuapp.com/link/code=2c3bbb72603be7bddb403b7540e7b9ba5c2a604de4&input=5)
Explanation:
```
,;╗r`;τ╜█@;u@τ╣║\*`MΣ
,;╗                    push input, dupe, store one copy in register 0
   r                   push range(0, n) ([0,n-1])
    `             `M   map the function:
     ;τ╜█@               dupe k, push C(n, 2*k), swap with k
          ;u@τ╣║\        push the kth Catalan number
                 *       multiply
                    Σ  sum
   
```
[Answer]
# R, 64 bytes
```
f=function(n)ifelse(n<2,1,f(n-1)+sum(rev(s<-sapply(2:n-2,f))*s))
```
Uses also the Mathworld formula of [@xnor's python answer](https://codegolf.stackexchange.com/a/66858/6741).
Thanks to rules of precedence, `2:n-2` is equivalent to `0:(n-2)`.
Test cases:
```
> f(0)
[1] 1
> f(1)
[1] 1
> f(5)
[1] 21
> f(10)
[1] 2188
> sapply(0:20,f)
 [1]        1        1        2        4        9       21       51      127
 [9]      323      835     2188     5798    15511    41835   113634   310572
[17]   853467  2356779  6536382 18199284 50852019
```
[Answer]
# Mathematica, ~~31~~ 30 bytes
```
AppellF1[-#/2,.5,-#/2,2,4,4]&
```
For fun, here's a 37 byte version
```
Hypergeometric2F1[(1-#)/2,-#/2,2,4]&
```
and 52 byte version
```
SeriesCoefficient[1-x-Sqrt[1-2x-3x^2],{x,0,#+2}]/2&
```
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), ~~17~~ ~~14~~ 13 bytes
```
×US;
1;HÇƓ¡1ị
```
This uses the recurrence relation from [@PeterTaylor's answer](https://codegolf.stackexchange.com/a/66853). [Try it online!](http://jelly.tryitonline.net/#code=w5dVUzsKMTtIw4fGk8KhMeG7iw&input=MTA)
### How it works
```
×US;      Define a helper link. Left argument: a (list)
×U        Multiply (×) a by its reverse (U).
  S       Compute the sum of the resulting list.
   ;      Prepend it to a.
          Return the result.
1;HÇƓ¡1ị  Define the main link.
1         Set the left argument to 1.
 ;H       Append the half of 1 to 1. Result: [1, 0.5].
    Ɠ     Read an integer n from STDIN.
   Ç ¡    Call the helper link (Ç) n times.
      1ị  Retrieve the result at index 1.
```
[Answer]
# Mathematica, ~~44~~ ~~42~~ 34 bytes
```
Sum[#!/(i!(i+1)!(#-2i)!),{i,0,#}]&
```
A 35 bytes version:
```
Coefficient[(1+x+1/x)^#,x]/#&[#+1]&
```
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E), ~~13~~ 12 bytes
```
ÝI<ãʒ.øDŸQ}g
```
[Try it online!](https://tio.run/##yy9OTMpM/f//8FxPm8OLT03SO7zD5eiOwNr0///NAA)
While most answers use a formula or recurrence relation, this is a simple counting approach.
Each possible path through the grid is represented by the list of its y coordinates. For n segments, there are a total of (n+1) points, but the first and last one are necessarily 0, so that leaves (n-1) points to specify.
```
Ý           # range [0..n]
 I<         # n - 1
   ã        # cartesian power
```
We now have a list of paths (not yet including the initial and final 0). By construction, none of them ever go below 0. However, some of them have illegal slopes (e.g. jump from 0 to 2), so we need to filter them out.
```
ʒ      }g   # count how many paths satistfy the following condition
 0.ø        # surround with 0
      Q     # is equal to
    DŸ      # its own fluctuating range
```
`Ÿ` is the [fluctuating range](https://codegolf.stackexchange.com/questions/74855/fluctuating-ranges/) built-in. If there's any pair of non-adjacent numbers, it will fill in the missing numbers (e.g. [0, 2] becomes [0, 1, 2]). Only legal paths will be left unchanged.
A perhaps more intuitive way to check for illegal slopes would be `üαà` (assert the maximum of pairwise absolute differences equals 1). However, this misses the flat [0, 0, ... 0] path, which costs one extra byte to fix.
Finally, note that the actual code uses `.ø` where this explanation uses `0.ø`. Instead of surrounding the path with 0s, this surrounds the implicit input with two copies of the path. This turns the coordinate system upside-down and inside-out, but is otherwise equivalent.
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 12 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
îu¬@Y≤ÅÉÑ(πε
```
[Run and debug it](https://staxlang.xyz/#p=8c75aa4059f38f90a528e3ee&i=1%0A2%0A3%0A4%0A5%0A6%0A7%0A8%0A9%0A10&a=1&m=2)
I don't know how to do fancy math typesetting, but this essentially relies on a dynamic programming construction
```
M(0) = 1
M(1) = 1
M(n + 1) = M(n) + sum(M(k) * M(n - k - 1) for k in [0..n-1])
```
[Answer]
# [Pari/GP](http://pari.math.u-bordeaux.fr/), ~~38~~ ~~36~~ 26 bytes
```
n->(1+x+x^2)^n++/n\x^n++%x
```
[Try it online!](https://tio.run/##K0gsytRNL/ifpmD7P0/XTsNQu0K7Is5IMy5PW1s/L6YCRKtW/E/LL9LIU7BVMNRRMDLQUSgoyswrAQooKejaAYk0jTxNTc3/AA "Pari/GP – Try It Online")
Using equation (11) from [MathWorld](http://mathworld.wolfram.com/MotzkinNumber.html):
\$ M\_n = \dfrac{1}{n + 1} \dbinom{n + 1}{1}\_2 \$
where \$ \binom{n}{k}\_2 \$ is a [trinomial coefficient](http://mathworld.wolfram.com/TrinomialCoefficient.html). By definition, \$ \binom{n}{k}\_2 \$ is the coefficient of \$ x^{n + k} \$ in the expansion of \$ (1 + x + x^2)^n \$.
[Answer]
# Ruby, 50
straightforward implementation of the recurrence relation.
```
g=->n{n<2?1:(3*(n-1)*g[n-2]+(2*n+1)*g[n-1])/(n+2)}
```
[Answer]
# [Brain-Flak](https://github.com/DJMcMayhem/Brain-Flak), 90 bytes
```
(([{}]<(())>)<{({}()<{<>([({})]({}[({})]({}<>{}<>)))<>}<>>)}>){({}()<{}>)}{}({}{}[{}{}]<>)
```
[Try it online!](https://tio.run/##PYoxCoBADAS/s1sI2od85LjiLARRLGxD3h7XQoudnWLWe@zXtJ3jqAJaZDeAdFogEjpzNCm78Iv5O5Lmemc6v16ashDai66uapkf "Brain-Flak – Try It Online")
Computes \${\binom{n}{0}}\_2 - {\binom{n}{2}}\_2\$, where \$\binom{n}{k}\_2\$ is a [trinomial coefficient](http://mathworld.wolfram.com/TrinomialCoefficient.html). I couldn't find this formula anywhere, so I can't reference it, but it can be proved in the same way as the analogous formula \$C\_n = \binom{2n}{n} - \binom{2n}{n+1}\$.
[Answer]
# [Haskell](https://www.haskell.org/), ~~55~~ 52 bytes
Straightforward implementation of the recursion. Thanks @Delfad0r for -3 bytes!
```
a n|n>2=div((2*n+1)*a(n-1)+(3*n-3)*a(n-2))$n+2
a n=n
```
[Try it online!](https://tio.run/##Jcq9CoAgFAbQvae4Q4M/KKmzvUg0XChI0g@paOrdLWg8cDY@9zXn1pjwYPRxSbcQXkE7qVjAOKlFUDDhp5eyh/bd1yNa4QSKVI@Ei3oqXIlpcta6YW4v "Haskell – Try It Online")
[Answer]
# [Maxima](http://maxima.sourceforge.net/), 49 bytes
Use the formula
\$
M\_n=\frac{1}{n+1}\cdot[z^{n+2}](1+x+x^2)^n
\$
```
f(n):=coeff(expand((1+x+x^2)^(n+1)),x,n+2)/(n+1);
```
[Try it online!](https://tio.run/##HcxBCoMwEEbhvaf4ERczJNImy5T2KEJQQ104CcHC3D5V3@7bvD3qtsfWEgmH95zXlGjVEmUhckaNTp4nEuOYrVoxnh@3Xi3lCgkOx7f@4J9YMqjDWambHCQWPcYPeovrzR0P7Q8)
[Answer]
## ES6, 44 bytes
```
f=(n,k=0)=>n<1?1:k<n&&f(k)*f(n-2-k)+f(n,k+1)
```
Straightforward port of @xnor's recursive Python solution. Needs `n<1?1:` because `n<1||` would make `f(0)` return `true`.
[Answer]
# [Nekomata](https://github.com/AlephAlpha/Nekomata) + `-n`, 8 bytes
```
3$ŧ←∫Ɔž≥
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m70iLzU7PzexJHFNtJJurpKOgpJunlLsgqWlJWm6FhuNVY4uf9Q24VHH6mNtR_c96ly6pDgpuRgqu2CLIZcRlzGXCZcplxmXOZcFlyWXoQFEDgA)
```
3$ŧ←∫Ɔž≥    Let n be the input
3$ŧ         Find an n-tuple of integers in [0, 3)
   ←        Decrement each element
    ∫       Take the cumulative sum
     Ɔž     Check that the last element is 0
       ≥    And that each element is non-negative
```
`-n` counts the number of solutions.
]