2 added 45 characters in body

# Jelly, 1515 14 bytes

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


-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

# 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.