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.

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

1 Answer 1


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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .