# 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? Mar 1, 2019 at 8:36
• For all $0 \leq k \leq n$, the answers are preferred. Mar 1, 2019 at 9:49

$$|\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).