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 at 8:36
  • $\begingroup$ For all $0 \leq k \leq n$, the answers are preferred. $\endgroup$ – Hang Wu Mar 1 at 9:49

Your Answer


Browse other questions tagged or ask your own question.