Count of All Possible Paths back to same origin

Question

I want to count the total number of ways we can travel between multiple cities and come back to the same origin in given maximum steps $\mathtt{N}$.

For example, if I have 5 cities (A, B, C, D, E) and every city is connected to next one bidirectionally. So City A is connected to B and E. B is connected to city A and city C...

So for $\mathtt{N = }$ odd number, we will have zero paths as we can't come back to $\mathtt{A}$ after traveling to any city.

For $\mathtt{N =2}$ we have

$ A\rightarrow B \rightarrow A\\$
$ A\rightarrow E \rightarrow A$

i.e. 2 ways.

For $\mathtt{N =3}$ we have zero ways

For $\mathtt{N =4}$ we have:

$ A\rightarrow B \rightarrow A \rightarrow B \rightarrow A\\$
$ A\rightarrow B \rightarrow C \rightarrow B \rightarrow A\\$
$ A\rightarrow B \rightarrow A \rightarrow E \rightarrow A\\$
$ A\rightarrow E \rightarrow D \rightarrow E \rightarrow A\\$
$ A\rightarrow E \rightarrow A \rightarrow E \rightarrow A\\$
$ A\rightarrow E \rightarrow A \rightarrow B \rightarrow A\\$

i.e. a total of 6 ways.

I was thinking if we can represent this relationship using some equation for

1. A fixed number of cities (5 cities).

2. $\mathtt{K}$ number of cities.

Thanks

Answer 1

In general, we write the graph (which cities are connected to each other) as an adjacency matrix $M$. If we choose city $A$ to be represented by row/column $1$ in $M$, then $M^d[1,1]$ is the number of length-$d$ walks from $A$ to $A$.

In the case of $C_5$, the numbers satisfy a linear recurrence: $$a(n) = 5a(n-2) - 5a(n-4) + 2a(n-5)$$ as given by OEIS A054877 and the sequence begins $$0, 2, 0, 6, 2, 20, 14, 70, 72, 254, 330, 948, 1430, \ldots$$ when $n \in \{1,2,\ldots\}$.

A comment there describes a general formula for length-$n$ closed walks on the $m$-cycle $C_m$ (but no reference is given):

In general a(n,m)=2^n/m*Sum(k,0,m-1,Cos(2Pi*k/m)^n) counts closed walks of length n at a vertex of the cyclic graph on m nodes C_m. Here we have the case m=5. - Herbert Kociemba, May 31 2004