2 added 45 characters in body
source | link

Jelly, 1515 14 bytes

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

Try it online!Try it online!

-1 byte based on Peter Taylor's comment.

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

How it works

Ø.xŒ!QŒɠ€2*HP€SQŒɠ€’§2*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,Decrement and halvesum each
           2*S P€S   Raise Productto power of each2 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.

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.

Jelly, 15 14 bytes

Ø.xŒ!QŒɠ€’§2*S

Try it online!

-1 byte based on Peter Taylor's comment.

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

How it works

Ø.xŒ!QŒɠ€’§2*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
         ’§       Decrement and sum each
           2*S    Raise to power of 2 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.

1
source | link

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.