Combinations of elements from multiple sets with constraints 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:

 A: 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.
A: A selective case-based solution with four cases:
$$d=6, c=5: 1*1*4*3=12\\
d=6, c\neq 5: 1*3*3*2=18\\
d\neq 5, c=5: 2*1*3*2=12\\
d\neq 6, c\neq 5: 2*2*2*1=\;8\\
12+18+12+8=50$$
A: We calculate the wanted number with the help of rook polynomials. We consider a $(6\times4)$-rectangular board, where the columns represent the sets $A,B,C,D$ and the rows the elements of the sets. A valid quadruple $(a,b,c,d)\in A\times B\times C\times D$  can be represented by placing four non-attacking rooks on the board, with forbidden positions marked as red squares. A valid arrangement is given showing $(a,b,c,d)=(2,4,1,6)$.
                                                            
Since the number of forbidden squares is smaller than the number of valid squares, we calculate the rook polynomial for the forbidden squares and subtract the corresponding number of non-attacking rook arrangements from the non-attacking rook arrangements of the complete rectangle.
The rook polynomial $r(x)$ we are looking for is
\begin{align*}
r_0+r_1x+r_2x^2+r_3x^3+r_4x^4\tag{1}
\end{align*}
with  $r_j \ (0\leq j\leq 4)$ denoting the number of placing exactly $j$ non-attacking rooks on the forbidden red squares. 


*

*$r_0$: There is one arrangement placing no rooks at all.

*$r_1$: We have $9$ red squares where we can place a rook, giving $r_1=9$.

*$r_2$: We count all valid arrangements placing two non-attacking rooks on the forbidden squares. We start with placing a rook on $(A,6)$ which admits $5$ arrangements by placing the other rook on $(B,5),(C,4),(D,5),(D,4),(D,3)$. We continue systematically and obtain:
\begin{align*}
&(A,6)\to 5&(A,5)\to 5\\
&(B,6)\to 4&(B,5)\to 4\\
&(C,6)\to 3&(C,4)\to 2\\
\end{align*}
from which $r_2=5+5+4+4+3+2=23$ follows.

*$r_3$: We count all valid arrangements placing two non-attacking rooks on the forbidden squares. We start with placing two rooks on $(A,6),(B,5)$ which admits $3$ arrangements by placing the third rook on $(C,4),(D,4),(D,3)$. We continue systematically and obtain 
\begin{align*}
&(A,6),(B,5)\to 3&(A,5),(B,6)\to 3\\
&(A,6),(C,4)\to 2&(A,5),(C,6)\to 2\\
&(A,5),(C,4)\to 1&(B,6),(C,4)\to 2\\
&(B,5),(C,6)\to 2&(B,5),(C,4)\to 1
\end{align*}
from which $r_3=3+3+2+2+1+2+2+1=16$ follows.

*$r_4$: We have two valid arrangements with four rooks, namely $(A,6),(B,5),(C,4),(D,3)$ and $(A,5),(B,6),(C,4),(D,3)$ giving $r_4=2$.

The rook polynomial of the forbidden squares is
  \begin{align*}
r(x)=1+9x+23x^2+16x^3+2x^4
\end{align*}
Now its time to harvest. The number of all arrangements of four non-attacking rooks on the $(6\times 4)$ board is 
  \begin{align*}
6\cdot5\cdot4\cdot3=\frac{6!}{2}\tag{2}
\end{align*}
  We now use the coefficients of the rook polynomial $r(x)$ and apply the inclusion-exclusion principle. We subtract from (2) the number of arrangements with one rook on the forbidden squares, then adding the number of arrangements with two rooks on the forbidden squares. We continue this way and obtain
  \begin{align*}
&\frac{6!}{2}-9\cdot\frac{5!}{2}+23\cdot\frac{4!}{2}-16\cdot\frac{3}{2}+2\frac{2!}{2}\\
&\qquad=360-540+276-48+2\\
&\qquad\,\,\color{blue}{=50}
\end{align*}
  in accordance  with  the other answers.

