Partitioning the grid into triangles

Haskell, 60 55 54 52 bytes

After a drawing and programming a lot of examples, it occured to me that this is the same as the problem of the rooks:

On a \$(n+1) \times (n+1)\$ chessboard, how many ways are there for a rook to go from \$(0,0)\$ to \$(n,n)\$ by just moving right \$+(1,0)\$ or up \$+(0,1)\$?

Basically you have the top and the bottom line of the \$1 \times n\$ grid. Now you have to fill in the non-horizontal line. Each triangle must have two non-horizontal lines. Whether one of its sides is part of the top or the bottom line corresponds to the direction and length you'd go in the rooks problem. This is OEIS A051708. As an illustration of this correspondence consider following examples. Here the top line corresponds to up-moves, while the bottom line corresponds to right-moves.

Thanks @PeterTaylor for -6 bytes and @PostLeftGarfHunter for -2 bytes!

b 0=1
b 1=2
b n=div((10*n-6)*b(n-1)-9*(n-2)*b(n-2))n

Try it online!

Haskell, 42 bytes

0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n

Try it online!

A fairly direct implementation that recurses over 2 variables.

Here's how we can obtain this solution. Start with code implementing a direct recursive formula:

54 bytes

0%0=1
a%b=sum$map(a%)[0..b-1]++map(b%)[0..a-1]
f n=n%n

Try it online!

Using flawr's rook move interpretation ,a%b is the number of paths that get the rook from (a,b) to (0,0), using only moves the decrease a coordinate. The first move either decreases a or decreases b, keeping the other the same, hence the recursive formula.

49 bytes

a?b=sum$map(a%)[0..b-1]
0%0=1
a%b=a?b+b?a
f n=n%n

Try it online!

We can avoid the repetition in map(a%)[0..b-1]++map(b%)[0..a-1] by noting that the two halves are the same with a and b swapped. The auxiliary call a?b counts the paths where the first move decreases a, and so b?a counts those where the first move decreases b. These are in general different, and they add to a%b.

The summation in a?b can also be written as a list comprehension a?b=sum[a%i|i<-[0..b-1]].

42 bytes

0?0=1
a?b=sum[a?i+i?a|i<-[0..b-1]]
f n=n?n

Try it online!

Finally, we get rid of % and just write the recursion in terms of ? by replacing a%i with a?i+i?a in the recursive call.

The new base case causes this ? to give outputs double that of the ? in the 49-byte version, since with 0?0=1, we would have 0%0=0?0+0?0=2. This lets use define f n=n?n without the halving that we'd other need to do.

CJam (24 bytes)

{2,*e!{e`0f=:(1b2\#}%1b}

Online demo

This uses Bubbler's approach of summing over permutations of n 0s and n 1s.

Dissection

{         e# Define a block
  2,*     e#   Given input n, create an array of n 0s and n 1s
  e!      e#   Generate all permutations of that array
  {       e#   Map:
    e`    e#     Run-length encode
    0f=:( e#     Extract just the lengths and decrement them
    1b    e#     Sum
    2\#   e#     Raise 2 to the power of that sum
  }%
  1b      e#  Sum the mapped values
}

---

Alternative approach (28 bytes)

{_1aa{_2$,f{j}@@,f{j}+1b}2j}

Online demo

Dissection

The triangles all have one horizontal edge and two edges which link the horizontal lines. Label the non-horizontal edges by a tuple of their two x-coords and sort lexicographically. Then the first edge is (0,0), the last edge is (n,n), and two consecutive edges differ in precisely one of the two positions. This makes for a simple recursion, which I've implemented using the memoised recursion operator j:

{            e# Define a block
  _          e#   Duplicate the argument to get n n
  1aa        e#   Base case for recursion: 0 0 => 1
  {          e#   Recursive body taking args a b
    _2$,f{j} e#     Recurse on 0 b up to a-1 b
    @@,f{j}  e#     Recurse on a 0 up to a b-1
    +1b      e#     Combine and sum
  }2j        e#   Memoised recursion with 2 args
}

Note

This is not the first time I've wanted fj to be supported in CJam. Here it would bring the score down to 24 bytes also. Perhaps I should try to write a patch...