Given four sets of numbers:
$$A=\{1,2,3,4\}$$
$$B=\{1,2,3,4\}$$
$$C=\{1,2,3,5\}$$
$$D=\{1,2,6\}$$
I need to find number of all possible combinations of numbers from these sets in following format:
$$(a,b,c,d)$$
where $a\in A, b \in B, c \in C, d \in D$ and where each number can be present only once per combination (e.g. combination $(1,2,3,4)$ is valid, but combination $(1,1,2,3)$ is not (number 1 repeats) and neither is combination $(2,3,5,2)$ (number 2 repeats)).
My idea is to use inclusion-exclusion principle. First I calculate number of all possible combinations:
$$\vert{A}\vert \cdot \vert{B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert = 192$$
And then I need to remove all combinations where elements are repeating 2 or more times. These sets are:
$$\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert = 48 $$
$$\vert{A\cap C}\vert \cdot \vert{B}\vert \cdot \vert{D}\vert = 36 $$
$$\vert{A\cap D}\vert \cdot \vert{B}\vert \cdot \vert{C}\vert = 32 $$
$$\vert{B\cap C}\vert \cdot \vert{A}\vert \cdot \vert{D}\vert = 36 $$
$$\vert{B\cap D}\vert \cdot \vert{A}\vert \cdot \vert{C}\vert = 32 $$
$$\vert{C\cap D}\vert \cdot \vert{A}\vert \cdot \vert{B}\vert = 32 $$
The problem here is that I have duplicates during removal, since sum of all combinations above is $216$ (some combinations that I remove – I remove multiple times).
My questions is – how to find intersections between all these sets, in order to get correct number for removal (in this case it should be $142$ and not $216$) – so correct answer in the end should be $192-142=50$.
I guess I need to find following intersections but not sure how to calculate all of these:
$$\vert(\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert) \cap (\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert)\vert = 9 \tag{1}\label{1}$$
$$\vert(\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert) \cap (\vert{A\cap C}\vert \cdot \vert{B}\vert \cdot \vert{D}\vert)\vert = 8$$
$$\vert(\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert) \cap (\vert{A\cap D}\vert \cdot \vert{B}\vert \cdot \vert{C}\vert)\vert = 9$$
$$\vert(\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert) \cap (\vert{B\cap C}\vert \cdot \vert{A}\vert \cdot \vert{D}\vert)\vert = 8$$
$$\vert(\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert) \cap (\vert{B\cap D}\vert \cdot \vert{A}\vert \cdot \vert{C}\vert)\vert = 8$$
$$\vert(\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert) \cap (\vert{C\cap D}\vert \cdot \vert{A}\vert \cdot \vert{B}\vert)\vert = 8$$
$$…$$
$$\vert(\vert{A\cap D}\vert \cdot \vert{B}\vert \cdot \vert{C}\vert) \cap (\vert{B\cap C}\vert \cdot \vert{A}\vert \cdot \vert{D}\vert)\vert = 6 \tag{2}\label{2}$$
$$…$$
$\eqref{1}$ duplicates are $(1,1,1,1),(1,1,1,2),(1,1,1,6),(2,2,2,1),(2,2,2,2),(2,2,2,6),(3,3,3,1),(3,3,3,2),(3,3,3,6)$
$\eqref{2}$ duplicates are $(1,1,1,1),(1,2,2,1),(1,3,3,1),(2,1,1,2),(2,2,2,2),(2,3,3,2)$ -> what is the rule here if I have more than 4 sets like here?
and then I need all 3 intersections:
$$\vert((\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert) \cap (\vert{A\cap C}\vert \cdot \vert{B}\vert \cdot \vert{D}\vert) \cap (\vert{A\cap D}\vert \cdot \vert{B}\vert \cdot \vert{C}\vert))\vert = 2$$
$$…$$
and then 4,5 intersections (not shown here) and finally I need remaining (6) intersection of all:
$$\vert((\vert{A\cap B}\vert \cdot \vert{C}\vert \cdot \vert{D}\vert) \cap (\vert{A\cap C}\vert \cdot \vert{B}\vert \cdot \vert{D}\vert) \cap (\vert{A\cap D}\vert \cdot \vert{B}\vert \cdot \vert{C}\vert) \cap (\vert{B\cap C}\vert \cdot \vert{A}\vert \cdot \vert{D}\vert) \cap (\vert{B\cap D}\vert \cdot \vert{A}\vert \cdot \vert{C}\vert) \cap (\vert{C\cap D}\vert \cdot \vert{A}\vert \cdot \vert{B}\vert))\vert = 2$$
In the end I get result: $192-(216-119+65-30+12-2)=50$
I tried to generalize this to more than 4 sets, but cannot find strict rule to calculate these intersections that I wrote above. Any help would be appreciated.
UPDATE
Based on answer below, I found a formula that makes computation much easier per partition:
$$ Part(p) = \prod_{n=1}^{g} (-1)^{l_n} \cdot l_n! \cdot s_n $$
Here, $p$ is one of partitions – e.g. $\{\{A,B\},\{C\},\{D\}\}$; $g$ is number of groups in that partition (in this case 3 – $\{A,B\}$ ,$\{C\}$ and $\{D\}$); $l_n$ is number of elements in a group minus 1 – in this case it would be $2-1=1$, $1-1=0$ and $1-1=0$ per group; $s_n$ is number of elements in that group – in this case $\vert\{A,B\}\vert=4$, $\vert\{C\}\vert=4$ and finally $\vert\{D\}\vert=3$.
You can see all the formula for this example in the uploaded picture below:
Best Answer
This could theoretically be done with standard inclusion–exclusion on the $\binom n2$ conditions that the elements be pairwise different (where $n$ is the number of sets being chosen from, in your case $n=4$), but that would be quite cumbersome. It’s easier to apply general Möbius inversion on posets. Here the partially ordered set is the set of partitions of your set of sets, partially ordered by refinement.
That is: Let $\mathcal S=\{A,B,C,D\}$ denote the set of sets, and let $\mathcal P$ denote the set of its partitions. For each partition $p\in\mathcal P$ of $\mathcal S$, we can count the tuples that are constant on each part of the partition. For instance, for $p=\{\{A,C\},\{B,D\}\}$, the identical elements from $A$ and $C$ can be $1$, $2$ or $3$, and the identical elements from $B$ and $D$ can be $1$ or $2$, so there are a total of $3\cdot2=6$ tuples that are constant on the parts of $p$.
Partially order $\mathcal P$ by refinement, where $p\preceq q$ means that $q$ is finer than $p$, that is, each part of $q$ is a subset of a part of $p$; for instance, $\{\{A,C\},\{B,D\}\}\preceq\{\{A\},\{C\},\{B,D\}\}$. Let $g(p)$ count the tuples that are constant on the parts of $p$, and let $f(p)$ count the tuples that are constant on the parts of $p$ but not of any coarser partition. Then we have
$$ g(q)=\sum_{p\preceq q}f(p)\;. $$
We can readily count $g$, and we want to invert the sum by Möbius inversion to get $f(s)$, where $s=\{\{A\},\{B\},\{C\},\{D\}\}$ is the finest partition, the maximal element of $\mathcal P$:
$$ f(s)=\sum_{p\preceq s}g(p)\mu(p,s)\;. $$
The values of the Möbius function $\mu$ that we need are determined by the initial value $\mu(s,s)=1$ and the recurrence
$$ \mu(s,p)=-\sum_{s\preceq q\preceq p}\mu(s,q)\;. $$
The next-coarsest partitions after $s$ are the ones with three parts, of the form $\{\{A,B\},\{C\},\{D\}\}$. There are $6$ of these, one for every pair of sets. You’ve already counted the corresponding values of $g$. As the only finer partition is $s$, we have $\mu(s,p)=-1$ for each of these, so we subtract each of their counts once, as expected.
Then there are two types of partitions with two parts, of the form $\{\{A,B\},\{C,D\}\}$ and of the form $\{\{A,B,C\},\{D\}\}$. There are $3$ of the first type (one for each way to divide the sets into pairs) and $4$ of the second type (one for each set). A partition of the first type is coarser than $2$ of the partitions with three parts, and a partition of the second type is coarser than $3$ of the partitions with three parts, so the Möbius function values $\mu(s,p)$ are $-(1+2\cdot(-1))=1$ and $-(1+3\cdot(-1))=2$, respectively.
Finally, there is one partition with a single part, $\{\{A,B,C,D\}\}$, the minimal element of $\mathcal P$, which is coarser than all other partitions, so the corresponding Möbius function value is $\mu(s,p)=-(1+6\cdot(-1)+3\cdot1+4\cdot2)=-6$.
Counting the values of $g$ as described above yields counts of $8,6,6$ and $9,8,8,8$ for the partitions with two parts of the first and second type, respectively, and a count of $2$ for the partition with a single part.
For example, the values $8$, $6$, $6$ correspond to the partitions $\{\{A,B\},\{C,D\}\}$, $\{\{A,C\},\{B,D\}\}$ and $\{\{A,D\},\{B,C\}\}$, respectively. In the first case, $A$ and $B$ share $4$ elements (all $4$) and $C$ and $D$ share $2$ elements ($1$ and $2$). We can combine these in $4\cdot2=8$ ways to form tuples that are constant on both parts. One example of such a tuple is $(1,1,2,2)$. Analogously, $A$ and $C$ share $3$ elements ($1$, $2$ and $3$) and $B$ and $D$ share $2$ elements ($1$ and $2$), so for the second partition there are $3\cdot2=6$ tuples.
Now by Möbius inversion the desired count of tuples that are not constant on any partition coarser than the finest partition $s$ is
$$ f(s)=192-48-36-32-36-32-32+8+6+6+2(9+8+8+8)-6\cdot2=50\;, $$
in agreement with your result.