# How many sets of subsets of an n element set are there such that any two elements are not disjoint?

You are a manager of $$n$$ employees, and want to create projects to assign to one or many employees.

The only constraints are that for any two projects, there must be at least one employee working on both of them.

E.g. If Alice, Bob, and Charlie are your employees, then you could assign Alice and Bob to work on project X, but you could not assign Charlie alone to work on project Y. You would either need to assign Alice, Bob, or both of them to project Y.

Formal problem:

Let $$X$$ be an $$n$$ element set, and

$$S \subset \mathcal P(X)$$ such that $$\forall A,B \in S : A \cap B \neq \emptyset$$.

How many such sets are there?

When $$X=\{a\}$$, there is trivially only one possibility $$\{\{a\}\}$$.

When $$X=\{a,b\}$$, there are five such possibilities $$\{\{a\}\}, \{\{b\}\}, \{\{a,b\}\}, \{\{b\},\{a,b\}\}, \{\{a\},\{a,b\}\}$$.

When $$X=\{a,b,c\}$$, it becomes no longer the case that all elements in the set contain a common intersection e.g. $$\{\{a,b\},\{a,c\}, \{b,c\}\}$$. I found there to be $$39$$ such sets.

When $$X$$ contains $$4$$ elements, I found, with tedious effort, to be $$1345$$? elements.

A few possibilities come to mind: We could consider individual cases based on the number of elements of $$S$$, or consider the maximum/maximum length of any subsets $$A \in S$$.

For example (the first possibility), if we just consider sets $$S$$ with $$1$$ element, only the empty set fails to meet this condition. Every other subset of $$X$$ is valid. There are $$2^n-1$$ possibilities in this case.

When $$S = \{A,B\}$$ contains $$2$$ elements, we need to exclude cases where $$A$$ and $$B$$ are disjoint (there are $$(3^n-1)/2$$ such possibilities). Thus, there are $${{2^n}\choose{2}} - \frac{3^n-1}{2} = \frac{4^n-3^n-2^n+1}{2}$$ such subsets.

The case when $$S$$ contains three elements becomes more difficult. In addition to excluding mutually disjoint subsets, we also need to consider subsets which share a common intersection, but there still exist disjoint subsets.

• Assuming $1, 5, 39$ are correct and $1345$ is approximately correct, this sequence doesn't appear in the OEIS. Commented Aug 3 at 18:46