# 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
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 2, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://math.stackexchange.com/questions/1088074/sum-over-subsets-of-a-multiset", "fetch_time": 1558619597000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2019-22/segments/1558232257244.16/warc/CC-MAIN-20190523123835-20190523145835-00370.warc.gz", "warc_record_offset": 559345123, "warc_record_length": 32164, "token_count": 1206, "char_count": 2741, "score": 3.546875, "int_score": 4, "crawl": "CC-MAIN-2019-22", "snapshot_type": "latest", "language": "en", "language_score": 0.6188194155693054, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00047-of-00064.parquet"}