0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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

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