MathDB

The following figure shows a walk of length 6: [asy] unitsize(20); for (int x = -5; x <= 5; ++x) for (int y = 0; y <= 5; ++y) dot((x, y)); label("

O

", (0, 0), S); draw((0, 0) -- (1, 0) -- (1, 1) -- (0, 1) -- (-1, 1) -- (-1, 2) -- (-1, 3)); [/asy] This walk has three interesting properties:
[*] It starts at the origin, labelled

O

. [*] Each step is 1 unit north, east, or west. There are no south steps. [*] The walk never comes back to a point it has been to.
Let's call a walk with these three properties a northern walk. There are 3 northern walks of length 1 and 7 northern walks of length 2. How many northern walks of length 6 are there?

Problem Statement