Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Suppose that we have a universe $U= \{1,\dots,n\}$ for some integer $n$. How many subsets $S_1,S_2,\dots\subseteq U $ are there such that $S_i \nsubseteq S_j$ but $S_i \cap S_j \neq \emptyset$ for all $i,j$? That means all $S_i$ and $S_j$ pairwise intersect but none are subsets of each other.
I tried starting with one $S_1$ and then counting the number of possible $S_2$ sets using the binomial coefficient but this didn't get me anywhere.
This is OEIS sequence A037952, given by
$$ \binom n{\left\lfloor\frac{n-1}2\right\rfloor}\;. $$
The entry states (without proof) that this is "the maximum size of an intersecting (or proper) antichain on an $n$-set", which is what you're looking for. An example of such an antichain is given by all subsets with $\left\lfloor\frac{n-1}2\right\rfloor$ elements.
(Here's the code I used to find the terms up $n=5$ to search for the sequence in OEIS.)
