# Calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset of $X=\{\{a_1,a_2\},\{a_2,a_3\},\cdots,\{a_{n-1},a_n\},\{a_n,a_1\}\}$

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.

• Can you give some context? Do you need the answers as a formula, do you need it for all $k$, etc? – Ingix Mar 1 at 8:36
• For all $0 \leq k \leq n$, the answers are preferred. – Hang Wu Mar 1 at 9:49