3
$\begingroup$

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP).

Let's consider the following two aspects:

1.) IEP transforms at least information to exact information

Applying the Inclusion-Exclusion Principle to $n$ sets $A_1,\dots,A_n$ gives:

\begin{align*} \left|\bigcup_{j=1}^{n}A_j\right|=\sum_{j=1}^{n}\left|A_j\right| -\sum_{1\leq i \leq j \leq n}\left|A_i\cap A_j\right|\pm\cdots+(-1)^{n-1}\left|\bigcap_{j=1}^{n}A_j\right|\tag{1} \end{align*}

We observe that the LHS representing an exact information can be represented by the RHS providing an at least information.

2.) Generating functions and corresponding binomial inverse relation pairs

Let

  • $e_m$ ... number of elements, which are in exactly $m$ sets

  • $l_m$ ... number of elements, which are in at least $m$ sets

Using this notation, the IEP (1) can now be written as: \begin{align*} e_1+e_2+\cdots+e_n=l_1-l_2\pm\cdots+(-1)^{n-1}l_n \end{align*} We now introduce the generating functions $L(z)$ and $E(z)$ having $l_k$ and $e_k$ as coefficients: \begin{align*} L(z) = \sum_{k=0}^{n}l_kz^k\qquad\qquad E(z)=\sum_{k=0}^{n}e_kz^k \end{align*} We observe following relations (see e.g. the answer section of the question above) \begin{align*} L(z)=E(z+1)&\qquad\qquad\qquad l_k=\sum_{m=k}^{n}\binom{m}{k}e_m\\ E(z)=L(z-1)&\qquad\qquad\qquad e_k=\sum_{m=k}^{n}(-1)^{m-k}\binom{m}{k}l_m\\ \end{align*}

This gives rise to the following question:

Question: Are there further inverse relation pairs which can be interpreted in the context of boolean algebras and which provide an interesting transformation of information similar to the IEPs at least to exact transformation.

$\endgroup$
  • $\begingroup$ Are you familiar with general Mobius inversion on posets? It is a very useful generalization of property 1. $\endgroup$ – Jair Taylor May 28 '14 at 3:35
  • $\begingroup$ @JairTaylor: My knowledge on (general) Möbius inversions is far too little. Thanks for the hint! Very interesting! Good point for further studies. Best Regards. $\endgroup$ – Markus Scheuer May 28 '14 at 7:56
3
$\begingroup$

Since no one has answered this yet, I'll elaborate a little on my comment.

One way of phrasing the inclusion-exclusion principle is as follows. Here I will borrow the notation from Richard Stanley's Enumerative Combinatorics Vol. 1, which is freely available on Stanley's web site. Let's say we have a set $X$ and a set of $\mathcal{C}$ of subsets of $X$, which we think of as conditions that we do not want to hold. For any $S \subseteq \mathcal{C}$ let $f_{\geq}(S)$ be the number of elements $x \in X$ that satisfy all the conditions of $S$, and let $f_=(S)$ be the number of $x \in X$ for which exactly the conditions in $S$ hold - that is, the conditions of $S$ hold but the conditions of $\mathcal{C} \backslash S$ do not hold. From this definition, we get the relation

$$f_\geq(S) = \sum_{T \supseteq S} f_=(T).$$

The inclusion-exclusion principle then says that we can invert this relation. We have

$$f_=(S) = \sum_{T \supseteq S} (-1)^{|T| - |S|}f_\geq(T). $$ In particular, $$f_=(\emptyset) = \sum_{T} (-1)^{|T|}f_\geq(T)$$ is the number of $x \in X$ that do not satisfy any of the conditions in $\mathcal{C}$.

Möbius inversion is a broad generalization of this idea. If $P$ is any finite poset then there is a unique function $\mu: P \times P \rightarrow \mathbb{Z}$, called the Möbius function of $P$, so that if any two functions $f,g$ from $P$ into $\mathbb{Z}$ (or your preferred commutative ring) obey the relation

$$f(v) = \sum_{u \geq v} g(v)$$

then we can invert, getting

$$g(v) = \sum_{u \geq v} \mu(v,u) f(v).$$

Thus in the case where the poset $P$ is the boolean algebra consisting of subsets of a fixed set $X$ with the subset relation, we have $\mu(S,T) = (-1)^{|T|-|S|}$ when $S \subseteq T$. In the case of the integers with the divisibility relation we get the classical Möbius function from number theory, hence the name.

$\endgroup$
  • $\begingroup$ Thanks for the elaboration and upvote for this nice summary. In fact I regard it as useful hint only.As you mentioned above: "If $P$ is any finite poset, we can apply a Möbius inversion on it." The challenge is to find $\endgroup$ – Markus Scheuer May 30 '14 at 18:28
  • $\begingroup$ (continuing)... The challenge is to find a proper poset or a proper inverse relation pair which enables us to derive a combinatorially interesting property like at least/exactly from it. But anyway, posets with Möbius inversions are at least as interesting as starting point as binomial inversion pairs. Best regards, Markus $\endgroup$ – Markus Scheuer May 30 '14 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.