<s>[INST] 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:

 [/INST] 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.

</s>