Let $x_i=\{a_i,a_{i+1}\}\ (1 \leq i \leq n-1)$, $x_n=\{a_n,a_1\}$ and $X=\{x_1, \cdots, x_n\}$. Given $n,m$ and $k$, I'd like to ask how to calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset of $X$? Note that $a_{1}\cdots a_n$ are different from each other.
Let $f(j,l)$ be the number of subset $S$ of $X$ where $|S|=j$ and $|\cup S|=l$. The above can be solved if all values of $f$ are known. I guess $f$ can be calculated recursively, and the inclusion-exclusion principle may help.
$|\cup S|=k+r$, where $r$ is the number of runs in $S$, that is, the number of consecutive stretches $\{a_k,a_{k+1}\}, \{a_{k+1},a_{k+2}\},\ldots$ in $S$ (possibly wrapping around at $n$).
To find the number of subsets $S$ with given $k$ and $r$, let's first count the ones in which a run starts at $\{a_1,a_2\}$. We have $r$ runs with at least one element, separated by $r$ gaps, also with at least one element. Thus we need to distribute $k$ balls into $r$ non-empty bins and $n-k$ balls into $r$ non-empty bins, for a total of $\binom{k-1}{r-1}\binom{n-k-1}{r-1}$ different ways.
In any given set $S$ with $r$ runs, a run starts at $r$ out of $n$ elements. Thus, to make up for the restriction that we assumed that a stretch starts at a specific element, we need to multiply by $\frac nr$. Then your sum comes out as
$$ \sum_{|S|=k}(n-|\cup S|)^m=\sum_{r=1}^k\frac nr\binom{k-1}{r-1}\binom{n-k-1}{r-1}(n-k-r)^m $$
(where if $2k\gt n$ some of the terms are zero because the second binomial coefficient is zero, since in this case there aren't enough elements for $k$ runs and $k$ gaps).