5
$\begingroup$

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: enter image description here

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
18
  • 1
    $\begingroup$ Very nice and instructive explanation. (+1) $\endgroup$
    – epi163sqrt
    May 10 '20 at 4:41
  • $\begingroup$ Could you please write more explicit how the values of $g $ (e.g. 8,6,6) were computed? $\endgroup$
    – user
    May 10 '20 at 7:57
  • $\begingroup$ @user: The values $8,6,6$ correspond to the three partitions of the form $\{\{A,B\},\{C,D\}\}$. These are $\{\{A,B\},\{C,D\}\}$, $\{\{A,C\},\{B,D\}\}$ and $\{\{A,D\},\{B,C\}\}$. 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. $\endgroup$
    – joriki
    May 10 '20 at 8:05
  • $\begingroup$ @joriki thanks for detailed explanation! Can you please clarify this part: "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". How you find number of coarser partitions? $\endgroup$ May 10 '20 at 9:36
  • 1
    $\begingroup$ thanks for the links. i will read all that and try to understand how to do it. I'll post my final findings here. $\endgroup$ May 10 '20 at 10:30
1
$\begingroup$

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$$

$\endgroup$
6
  • $\begingroup$ what is $d$ and $c$ ? $\endgroup$ May 10 '20 at 11:02
  • $\begingroup$ @Bojan From your format, $(a,b,c,d)$. The numbers in the products are options for choosing $d$, $c$, $b$ then $a$ $\endgroup$ May 10 '20 at 11:06
  • $\begingroup$ So, if I take 2nd case $d=6, c\neq5$, $1 * 3 * 3 * 2$ - can you please elaborate how to get 1,3,3,2? e.g. is last 2 number of elements in d without 6 ? $\endgroup$ May 10 '20 at 11:11
  • $\begingroup$ @Bojan $1$ option for $d$ with the restriction $d=6$, $3$ options for $c\neq 5$ (selecting from $\{1,2,3\}$), $3$ options for $b$ (the number chosen for $c$ being excluded) and finally, $2$ remaining options for $a$. $\endgroup$ May 10 '20 at 11:20
  • $\begingroup$ Thanks. So in $a,b,c,d$ order it is $2 * 3 * 3 * 1$. I still guess this is easier to calculate by hand only in this case, since many elements are repeating. If number of non-repeating elements increase I wold get much more possible combinations to calculate? $\endgroup$ May 10 '20 at 11:25
1
$\begingroup$

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)$.

                                                            enter image description here

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.

$\endgroup$
2
  • $\begingroup$ Thanks for another approach. I guess this one would not be more optimal for algorithm implementation on a PC? All these valid arrangements also take time... $\endgroup$ May 13 '20 at 8:48
  • $\begingroup$ @BojanVukasovic: You're welcome and I agree. The main intention of this answer was to show another combinatorial approach. $\endgroup$
    – epi163sqrt
    May 13 '20 at 9:22

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.