0

The accepted answer given for What is the number of all possible relations/intersections of n sets? also counts cases when one or more sets are empty. For example, for $n=2$ there are $2^{2^n-1}=8$ relations, but only for $5$ of them both sets are non-empty. (If you draw the Venn diagrams, in two of the $8$ cases one set is empty and in one case both.)

In how many ways can $n$ non-empty sets be related?

Community
  • 1
Eric '3ToedSloth'
  • 199

1 Answers1

0

using the work on the other answer we have $2^{2^n-1}$. If we managed to find a way to substract the relations with no empty sets on $1,2,3...n-1$ elements then we would be done.

let $I(n)$ be the number of intersections with no empty sets. we define recursively.

$I(1)=1$

$I(n)=2^{2^{n-1}}-\sum_{k=0}^{n-1}I(k)$

Asinomás
  • 105,651