I am interested in a formula which relating two functions over a multiset. 


I have a multiset $X$ of sets where each element in $X$ is a set $x \subseteq \{1,2,\ldots,m\}$. Now I have two ``count'' functions 


$p\_s = |\{x \in X : s = x\}|$


$\eta\_s = |\{x \in X : s \subseteq x\}|$


One can expand the formula for the marginal count $\eta\_s$ as


$\eta\_s = \sum\_{s \subseteq t,|t|\leq m} p\_t$


I have confirmed for up to $m = 4$ that the following results holds


$p\_s = \sum\_{s \subseteq t,|t|\leq m} (-1)^{|s|-|t|}\eta\_t$


Does the above result hold for arbitrary $m$? This seems like it must be related to the inclusion/exclusion principle (<http://en.wikipedia.org/wiki/Inclusion-exclusion_principle>) but there is a subtle difference, in that the summation is over set which include $s$ as subsets. Perhaps this difference is immaterial, but I don't see the argument just yet. Also, in the general problem that I wish to solve I will have $x \subseteq \{(i,a\_i)\}\_{i \in I}$ where $I$ is all combinations of $\{1,\ldots,m\}$ and $a\_i$ is drawn from a finite set $A:|A|=n$.



Inverse formula for counting marginals
The answer is yes, and this is known as Moebius inversion. See Section E.1, p.286 in [Graphical models, exponential families, and variational inference.](http://www.eecs.berkeley.edu/~wainwrig/Papers/WaiJor08_FTML.pdf)


