2
$\begingroup$

Does anyone have any thoughts on this? I have been struggling with it and I'm not sure if it's a hard problem, or easy and I'm just not getting it?

For $n=2$ sets (say $A$ and $B$), it's obviously 4:

  1. The one where $A \cap B = \emptyset$
  2. The one in which $A \cap B \neq \emptyset$, but neither set is a subset of the other
  3. The one where $A \subset B$
  4. The one where $B \subset A$

(I'm assuming $A \neq B$ in all cases.)

For $n \ge2 $, though it seems rather difficult. I can't think of a systematic way to count them. Originally I thought I could look at all distinct pairs and allow each pair to take on one of three values (representing disjoint, intersecting, and subset). But I've already found a case where two different diagrams can have the same representation this way.

Any ideas? Thanks.

$\endgroup$
  • 1
    $\begingroup$ One possible idea: looking at the second figure at en.wikipedia.org/wiki/Euler_diagram , maybe try to count the number of ways to shade in regions of the $n$-fold Venn diagram? $\endgroup$ – Greg Martin Jul 11 '14 at 1:47
  • $\begingroup$ Exactly which configurations are disallowed? For $n$ sets there are $2^n$ ways in which an element can be contained/not contained in each of the sets. Ignoring the elements in none of the sets we can assign the $2^n-1$ regions to be empty/not empty in $2^{2^n-1}$ ways, some of which will be disallowed. It will probably be easier to count the disallowed configurations. $\endgroup$ – deinst Jul 11 '14 at 13:04
  • $\begingroup$ Sounds good. Thanks, both of you. Surprisingly, I have a textbook problem in which it asks to sketch all of the "functionally different" configurations for $n=3$. (So for example, the set where $A \cap B \neq \emptyset$ and $C$ is disjoint from the other two would be functionally equivalent to the set where $B \cap C \neq \emptyset$ and $A$ is disjoint). But there will still be too many to sketch I believe and some are difficult to draw. It's just a strange question. $\endgroup$ – user2556975 Jul 11 '14 at 14:19
1
$\begingroup$

In the past month and an half I have spent more hours that I care to admit on this problem.

The original answer is still valid: 2^(2^n - 1) - 1 is an upper boundary on the number of possible Euler diagram. This is sequence A077585 in the OEIS.

A better upper limit is the the number of "covers" of an N set, sequence A003464. This eliminate the cases that reduce to a lower number of "characteristics". For example, the case with two separate regions B and C and no A will be eliminated from the count n=3;

An ever better upper limit is calculated with an iterative "procedure" that tracks how many regions are added when a new characteristic is added. I will upload this sequence to the OEIS, but it is related to A007018.

A lower limit is given by this same procedure, but removing repetitions. This catches most of the "equivalent" arrangements, but has a number of false positives, as the example below

false positive

A different lower limit is given by the number of possible arrangements of circles in a projective plane, sequence A250001 on OEIS. This however misses the possibilities of non-well formed Euler diagrams (e.g. with partially overlapping boundaries) like this

overlapping

Moreover the sequence is not defined after n=4, while the iterative-no repetition could be easily extended to n=6.

In summary, this is the table that i came up with

enter image description here

$\endgroup$
  • 1
    $\begingroup$ "In the past month and an half I have spent more hours that I care to admit on this problem.", welcome to the world of mathematics. $\endgroup$ – Asaf Karagila Feb 27 '15 at 5:58
1
$\begingroup$

I stumbled on the same problem while trying to have an automatic Euler diagram generator and I think the answer of deinst is correct.

Given $n$ “characteristics” there are $$V(n) = 2^n-1$$ different subsets (i.e. the Venn diagram sets, excluding the "rest of universe").

$$V(2)=3$$ $A \setminus B \\ B \setminus A,\\ A\cap B$

$$V(3)=7$$ $A \setminus (B\cup C)\\ B \setminus (A\cup C)\\ C\setminus (A\cup B)\\ (A\cap B) \setminus C\\ (A\cap C) \setminus B\\ (B\cap C) \setminus A\\ A\cap B \cap C$

Then we can assign each of these regions to exist / not exist in our Euler diagram. The number of combinations excluding the empty Universe is $$E(V) = 2^V - 1 \\E(n) = 2^{(2^n -1)}-1$$

I use a short notation, in which a letter indicates that the zone has only that characteristic. So for 3 characteristics $A \triangleq A \setminus (B \cup C) \qquad AB \triangleq (A\cap B)\setminus C$

For n = 2, E= 7
1) A,               B=∅
2) B,               A=∅
3) AB,              A = B ≠ ∅
4) A+B,             A∩B=∅
5) A+AB,            B⊂A
6) B+AB,            A⊂B
7) A+B+AB           A∩B≠∅, but neither set is a subset of the other

Of these, the first 3 reduce to cases with only "1" characteristic 
and the last 4 are the cases you listed in the question.

Note that for three characteristics the number is 127, so sketching all of them would take quite some time.

Much more difficult is to define when two diagrams are “functionally equivalent” as cases 5 and 6 above.

$\endgroup$

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.