Haskell, 60 55 54 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. Now you have to fill in the non-vertical line. Each triangle must have two non-vertical line. 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!

b 0=1

b 1=2

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

Try it online!

CJam (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. Perhaps I should try to write a patch...

Python 3, 51 bytes

lambda n:-~n*(n<2)or(10-6/n)*f(n-1)-(9-18/n)*f(n-2)

Try it online!

Port of flawr's answer

JavaScript (ES6),  45  44 bytes

Uses the recursive formula found by Peter Taylor and flawr.

f=n=>n<2?n+1:((10-6/n)*f(--n)+9/~n*f(--n)*n)

Try it online!

Haskell, 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!

No formula, just a slow direct calculation.

Charcoal, 44 31 bytes

crossed out 44 is still regular 44

Ｆ⊕θ«≔⟦⟧ηＦ⊕θ⊞ηΣ∨⁺ηＥυ§λκ¹⊞υη»Ｉ⊟⊟υ

Try it online! Explanation: Works by calculating the number of ways to partition a trapezium of opposite side lengths m,n into triangles which all lie on integer offsets. This is simply a general case of the rectangle of size n in the question. The number of partitions is given recursively as the sums of the numbers of partitions for all sides m,0..n-1 and n,0..m-1. This is equivalent to generalised problem of the rooks, OEIS A035002. The code simply calculates the number of partitions working from 0,0 up to n,n using the previously calculated values as it goes.

Ｆ⊕θ«

Loop over the rows 0..n.

≔⟦⟧η

Start with an empty row.

Ｆ⊕θ

Loop over the columns in the row 0..n.

⊞ηΣ∨⁺ηＥυ§λκ¹

Take the row so far and the values in the previous rows at the current column, and add the sum total to the current row. However, if there are no values at all, then substitute 1 in place of the sum.

⊞υη»

Add the finished row to the list of rows so far.

Ｉ⊟⊟υ

Output the final value calculated.

Jelly, 15 bytes

Ø.xŒ!QŒɠ€2*HP€S

Try it online!

Uses flawr's illustration directly, instead of the resulting formula.

How it works

Ø.xŒ!QŒɠ€2*HP€S    Main link (monad). Input: positive integer N.

Ø.x                Make an array containing N zeros and ones

   Œ!Q             All unique permutations

      Œɠ€          Run-length encode on each permutation

         2*H       Raise each value to power of 2, and halve

            P€S    Product of each and sum

Take every possible route on a square grid. The number of ways to move L units in one direction as a rook is 2**(L-1). Apply this to every route and sum the number of ways to traverse each route.