# Sum over subsets of a multiset

I have a sum that looks like the following for some multiset $S$ and some function $f$ of $n$ variables which does not depend on the ordering of its arguments:

$$\sum_{\{k_1,\dots, k_n\}\subset S}f(k_1,\dots k_n)$$

However, this is not a form where a computer (or Mathematica) can easily iterate over the set. Therefore, I would like to use the principle of inclusion-exclusion to write this as a sum of the form (where $P(n)$ denotes integer partitions of $n$):

$$\sum_{p\in P(n)}c_p\sum_{k_1,\dots,k_{|p|}\in S}f(k_1,\dots,k_n),$$

where $c_p$ is some coefficient that I need to calculate in terms of the partition, and the input into the function $f$ now has multiple copies of some of the variables based on the multiplicities of the integer partition $p$. What is $c_p$ in this formula?

As an example consider that when sum is over subsets of size 3 ($n=3$), then the formula is:

$$\sum_{\{k_1,k_2,k_3\}\subset S}f(k_1,k_2,k_3)=\frac{1}{6}\sum_{k_1,k_2,k_3\in S}f(k_1,k_2,k_3)-\frac{1}{2}\sum_{k_1,k_2\in S}f(k_1,k_1,k_2)+\frac{1}{3}\sum_{k_1\in S}f(k_1,k_1,k_1)$$

When $n\geq 4$, however, the formula becomes substantially more complicated. For example, when $n=4$: \begin{align} \sum_{\{k_1,k_2,k_3,k_4\}\subset S}f(k_1,k_2,k_3,k_4) &=\frac{1}{24}\sum_{k_1,k_2,k_3,k_4\in S}f(k_1,k_2,k_3,k_4)-\frac{1}{4}\sum_{k_1,k_2,k_3\in S}f(k_1,k_1,k_2,k_3) \\ & +\frac{1}{8}\sum_{k_1,k_2\in S}f(k_1,k_1,k_2,k_2)+\frac{1}{3}\sum_{k_1,k_2\in S}f(k_1,k_1,k_1,k_2)-\frac{1}{4}\sum_{k_1\in S}f(k_1,k_1,k_1,k_1) \end{align}

When $n=5$: \begin{align} & \sum_{\{k_1,k_2,k_3,k_4,k_5\}\subset S}f(k_1,k_2,k_3,k_4,k_5) \\ & \hspace{5mm} =\frac{1}{120}\sum_{k_1,k_2,k_3,k_4,k_5\in S}f(k_1,k_2,k_3,k_4,k_5)-\frac{1}{12}\sum_{k_1,k_1,k_2,k_3,k_4\in S}f(k_1,k_1,k_2,k_3,k_4) \\ & \hspace{5mm} +\frac{1}{8}\sum_{k_1,k_2,k_3\in S}f(k_1,k_1,k_2,k_2,k_3)+\frac{1}{6}\sum_{k_1,k_2,k_3\in S}f(k_1,k_1,k_1,k_2,k_3) \\ & \hspace{5mm} -\frac{1}{4}\sum_{k_1,k_2\in S}f(k_1,k_1,k_1,k_1,k_2)-\frac{1}{6}\sum_{k_1,k_2\in S}f(k_1,k_1,k_1,k_2,k_2)+\frac{1}{5}\sum_{k_1\in S}f(k_1,k_1,k_1,k_1,k_1) \end{align}

Let me know if anything in this question is unclear.

• (1) In your second display, how many $k$s are there: $p^l$ (?) or $n$? (2) Does $f$ depend only on the multiset $\{k_1,\dots,k_n\}$, or does it depend on their ordering as well? (3) Can you give an example of the type of identity you want, say with the multiset $S=\{1,1,1,1,2,2,3,4\}$? – Greg Martin Jan 2 '15 at 3:20
• (1) There are $|p|$ (not necessarily distinct) choices of $k$'s, which are then placed into the formula the number of times specified by the $i$'th index of $p$, $p_i$. (2) f only depends on the multiset, not the order. – ruadath Jan 2 '15 at 3:38