2
$\begingroup$

Let $\mathbb A := \{A_1,\dots,A_n\}$ be a collection of finite sets, and for $J\subseteq[n]$ let $A_J:=\bigcap_{j\in J} A_j$. Inclusion-exclusion principle gives the number of elements belonging to at least one set from $\mathbb A$ as $$\bigg|\bigcup_{j\in[n]} A_j\bigg| = \sum_{\emptyset\ne J\subseteq [n]} (-1)^{|J|-1} |A_J|.$$ It can further be shown that the number of elements belonging to exactly one set from $\mathbb A$ can be expressed as $$\sum_{J\subseteq [n]} (-1)^{|J|-1} |A_J|\cdot |J|.$$ More generally, the number of elements belonging to exactly $k$ sets from $\mathbb A$ is given by $$\sum_{J\subseteq [n]} (-1)^{|J|-k} |A_J|\cdot \binom{|J|}k.$$

So, for functions $f(x)=(-1)^k\binom{x}{k}$ we have nice interpretations for the expression: $$\sum_{J\subseteq [n]} (-1)^{|J|} |A_J|\cdot f(|J|).$$

Q: Are there any other functions $f$, for which the expression above has a nice combinatorial interpretation?

$\endgroup$
4
  • $\begingroup$ Nice! It also works for the case $k=0$, that gives the usual I-E formula in equivalent form, where the intersection of the empty family $A_\emptyset$ is of course the (finite) universe containing the $A_i$ as subsets $\endgroup$ Commented Jul 24 at 17:22
  • $\begingroup$ @PietroMajer: Yes, the first formula is essentially (the complement of) the one with $\binom{|J|}k$ for $k=0$. $\endgroup$ Commented Jul 24 at 17:31
  • 1
    $\begingroup$ Not sure, but this answer might be related. $\endgroup$ Commented Jul 24 at 17:47
  • $\begingroup$ @FabiusWiesner: Yes, the linked answer gives a generalization in another (multivariate) direction. The last formula (with all variables being the same) there essentially represents a generating function identity for the formulas in my question, since $(-1)^k\binom{x}k$ equals the coefficient of $t^k$ in $(1-t)^x$. $\endgroup$ Commented Jul 24 at 18:38

0

You must log in to answer this question.

Browse other questions tagged .