4
$\begingroup$

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.

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

1 Answer 1

5
$\begingroup$

The sequence you are looking for is A051185. You forgot to count the empty set in each case (which vacuously satisfies the property), so you are off by one.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .