# Combinatorics: How many paths?

Original Question: Students sit at their desks in three rows of eight. Felix, the class pet, must be passed to each student exactly once, starting with Alex in one corner and finishing with Bryn in the opposite corner. Each student can pass only to the immediate neighbour left, right, in front or behind. One possible path is shown. How many different paths can Felix take from Alex to Bryn?

So what confuses me about this question is typically this style of "how many paths" gives a more limited direction, e.g. only right and up towards the target. However, in this question, the students can pass left, right, in front, and behind. So the traditional method I usually use for these type of questions of counts on points wouldn't work (finding sum of number of ways to each point)? Or at least I think it doesn't work.

• In the OEIS, the closest I can find is this, which requires that it starts at Alex, but doesn't require that it ends at Bryn, or this where Bryn is in the top left corner instead of top right. It's possible that your sequence is there, but in that case I completely missed it. Commented Apr 12, 2023 at 11:08
• See this post. Commented Apr 12, 2023 at 11:34

The answer is $$2^{c-2}$$ where $$c$$ is the number of columns. The trick is to notice the distribution of unconnected columns on the top and bottom row.
• I don't understand. For $r=3$ rows, $2^{r-2}=2$ but there are obviously more than $2$ paths Commented Apr 12, 2023 at 11:48
• @Taladris If you want to start in the bottom left and end in the top right, and go through all points in the meantime, there are only two paths through a $3\times 3$ grid. Commented Apr 12, 2023 at 12:01
• @Arthur: when I commented, $r$ was the number of rows. Commented Apr 12, 2023 at 13:53