Counting the number of ordered SDRs using the PIE

Question

Given the sizes of n sets, and the sizes of the intersections between the subsets of the n sets, is it possible to use the principle of inclusion-exclusion to count the number of ordered systems of distinct representatives for the n sets?

Intuitively I think it should be possible. This question seems somewhat similar.

Answer 1

Fimpellizieri's solution is a sum of $2^{\binom{n}2}$ terms, each with a sign determined by the parity of number of conditions included, and carrying a product of sizes of intersections of certain $A_i$. Whenever two sets of condition determine the same partition of $\{1,2,\dots,n\}$, they will contribute the same thing to the sum, so we can group these together. This lets us simplify the sum of $\sim 2^{n(n-1)/2}$ terms to a sum of $B_n$ terms, where $B_n$ is the $n^{th}$ Bell number.

Namely, let $P$ represent an arbitray partition of $\{1,2,\dots,n\}$, with parts $P=\{P_1,P_2,\dots,P_k\}$ for some $k$. Then the number of SDR's is $$ \sum_{P\text{ is a partition}}(-1)^{n-|P|}\prod_{P_i\in P}(|P_i|-1)!\left|\bigcap_{j\in P_i}A_i\right| $$ For example, when $n=2$, there are two possible partitions of $\{1,2\}$: either $\{\{1\},\{2\}\}$ (both in different parts), or $\{\{1,2\}\}$ (both in same part). So it is a sum of two terms, namely, $$ |A_1|\cdot |A_2|-|A_1\cap A_2| $$ When $n=3$, there are $5$ partitions of $\{1,2,3\}$: $$ \{1\},\{2\},\{3\},\quad\{1,2\},\{3\},\quad \{1,3\},\{2\},\quad\{2,3\},\{1\},\quad\{1,2,3\} $$ Resulting in $$ |A_1||A_2||A_3|-|A_1\cap A_2||A_3|-|A_1\cap A_3||A_2|-|A_2\cap A_3||A_1|+2|A_1\cap A_2\cap A_3| $$ Note the $2$ in front of the last term; this is the $(|P_i|-1)!$ in the formula, since the size of the part is $3$.

For a hint of why an alternating sum of ordered pairs of a given partition results in the coefficient of $(n-1)!$, see this question.

Answer 2

A bad system os representatives can be thought of as a tuple $(a_1,a_2,\dots,a_n)$ where $a_i \in A_i$ and for some $i\neq j$ we have $a_i = a_j$.

Then, the set of bad representatives can be written as

$$\bigcup_{B \in \mathcal B}B,$$

where $\mathcal B = \{B_{i,j}\,|\, 1\leqslant i < j \leqslant n\}$ and $B_{i,j}$ is the set of bad representatives with $a_j = a_j$. Therefore, it follows from Inclusion-Exclusion that

$$\left|\bigcup_{B \in \mathcal B}B\right| = \sum_{S\subset \mathcal B}{(-1)}^{1+|S|}\,\left|\bigcap_{B\in S} B\right|.$$

We can break it down by $|S|$.

• When $|S| = 1$, $\bigcap_{B\in S} B = B_{i,j}$ for some $i\neq j$. Now, we can easily compute

$$|B_{i,j}| = \underbrace{|A_i\cap A_j|}_{\text{choosing the value of $a_i = a_j$}} \quad\cdot \underbrace{\prod_{\substack{1\leqslant k \leqslant n\\k\neq i, j}}|A_k|}_{\text{choosing the value of the other $a_k$}}$$

and hence $\left|\bigcap_{B\in S} B\right|$ is known.

• When $|S| = 2$, we are at $B_{i,j}\cap B_{p,q}$ and we have to consider whether the $(i,j)$ and $(p,q)$ have a common index or not.

If they have a common index, say $j=p$ then in the obvious notation we have $B_{i,j}\cap B_{p,q} = B_{i,j,q}$ and

$$|B_{i,j}\cap B_{p,q}| = \underbrace{|A_i\cap A_j\cap A_q|}_{\text{choosing the value of $a_i = a_j = a_q$}} \,\,\,\cdot \underbrace{\prod_{\substack{1\leqslant k \leqslant n\\k\neq i, j, q}}|A_k|}_{\text{choosing the value of the other $a_k$}}.$$

If they do not have a common index, we can compute

$$|B_{i,j}\cap B_{p,q}| = \underbrace{|A_i\cap A_j|}_{\text{choosing the value of $a_i = a_j$}} \cdot \underbrace{|A_p\cap A_q|}_{\text{choosing the value of $a_p = a_q$}} \,\,\,\cdot \underbrace{\prod_{\substack{1\leqslant k \leqslant n\\k\neq i, j, p, q}}|A_k|}_{\text{choosing the value of the other $a_k$}}.$$

In either case, $\left|\bigcap_{B\in S} B\right|$ is known.

---

At this point, I think we got the hang of it.

In general the subfamily $S$ can be partitioned as follows: $B_{i,j}, B_{p,q} \in S$ belong to the same class $C$ if there are $B_{x_1,y_1},B_{x_2,y_2},\dots,B_{x_k,y_k} \in C$ with $\{x_l,y_l\}\cap \{x_{l+1},y_{l+1}\} \neq \emptyset$ for all $1 \leqslant l < k$ and with $\{i,j\}\cap \{x_1,y_1\}, \{x_k,y_k\}\cap\{p,q\} \neq \emptyset$.

It's easy to see that this is an equivalence relation, if the existence of the partition seems unclear.

Perhaps more 'algorithmitically', it can also be seen as the result of a chain of partitions, where the initial partition just makes classes out of pairs $(B_{i,j}, B_{p,q})$ with $\{i,j\}\cap\{p,q\} \neq \emptyset$ and successive partitions aggregates distinct classes when there are representatives from each class with intersecting indices.

Let $P$ be this partition. For each class $C\in P$, let $I(C)$ be the (union of) the set of indices of the $B_{i,j}\in C$. Then it's easy to see that

$$\left|\bigcap_{B\in S} B\right| = \left(\prod_{C \in P}\left|\bigcap_{i \in I(C)}A_i\right|\right)\cdot\left(\prod_{\displaystyle i\not\in\cup_{C\in P} I(C)}\left|A_i\right|\right).$$

This means the answer to your question is a resounding YES, but a 'closed formula' might be a bit too cumbersome to be actually useful. Perhaps a different approach might yield a more tractable formula.