Take a look at the following article, and see what you can come up with:
https://betterexplained.com/articles/navigate-a-grid-using-combinations-and-permutations/
An ant starts at position (0, 0) and walks north, east, south or west, one unit at a time.
How many di�erent paths of length 8 units finish at (0, 0)?
2 answers
move 1 unit East: 8!/3!3!=1120
move 2 units East: 8!/2!2!2!2!=2520
move 3 units East: 8!/3!3!=1120
move 4 units East: 8!/4!4!=70
move 0 unit East: 8!/4!4!=70
Total paths: 4900
Note: if ant moves 1 unit East, must move back 1 unit West.
move 2 units East: 8!/2!2!2!2!=2520
move 3 units East: 8!/3!3!=1120
move 4 units East: 8!/4!4!=70
move 0 unit East: 8!/4!4!=70
Total paths: 4900
Note: if ant moves 1 unit East, must move back 1 unit West.