stumbled upon a homework question which I wasn't able to solve. I have the following graph:
The question is how many paths with the length of $n$ there are on the given graph so you can go through the top vertex once at most?
I was trying to solve it with recursion, but I wasn't able to split the scenarios with the top vertex and without it correctly.
Is recursion the right way to solve it? I couldn't figure anything else that might work with it..
The number of paths of length $n$ which do no go through the apex is $6\cdot 2^{n}$; $6$ choices for the start, $2$ choices for whether each step is clockwise or counterclockwise. If the $k^{th}$ point visited by the path is the apex (indexing from $0$), then there are $6\cdot 2^{k-1}$ ways to choose the path that comes before, and $6\cdot 2^{n-k-1}$ ways to choose what comes after. The exception is when $k=0$, in which case the number of ways to choose what comes before is $1$, and when $k=n$, where the number of ways to choose what comes after is $1$. Conclude by summing over $k$.
You can also solve this with a recursion. Let $a_n$ be the number of paths, and let $b_n$ be the number of paths which do not pass through the apex. $$ a_n = 2a_{n-1}+b_{n-2}+b_{n-1},\\ b_n=2b_{n-1}. $$