Can a family of subsets have 5 SDRs? If $X = \{1,2,3\}$, can a family of 3 subsets of X have exactly 5 distinct SDRs?
I'm pretty sure the answer is no as I have tried constructing them, only finding families with 1, 2, 3, 4 or 6 SDRs, but can't quite state explicitly why 5 is not possible.
Is there a specific result that this is the result of?
 A: Let your three subsets be $A,B,C$. Construct a $3\times3$ matrix $M$ where the first row represents $A$ (meaning, if $r$ is an element of $A$, then entry number $r$ of the 1st row is one, else it is zero), similarly 2nd row represents $B$, third row represents $C$. The number of SDRs of the set system is the number of "transversals" of this matrix, that is, the number of ways to choose three nonzero entries, exactly one in row and in each column. It's also the "permanent" of the matrix.
Now if $M$ is the all-ones matrix, then it has six transversals, and clearly no $M$ can have more. If even one entry is a zero, that kills two of the six transversals, leaving four. That proves you can't have exactly five SDRs.
To illustrate: $A=\{1\}$, $B=\{2,3\}$, $C=\{1,2,3\}$ corresponds to $$M=\pmatrix{1&0&0\cr0&1&1\cr1&1&1\cr}$$ which has two transversals, corresponding to the SDRs $1/2/3$ and $1/3/2$.
A: The number of SDRs must decrease monotonically if we remove edges from the graph corresponding to the subset family. $|X|=3$ and we have three subsets, so the bipartite graph has three vertices on either side. Now the largest such graph ($K_{3,3}$) has $6$ matchings (SDRs), but removing any edge leaves only $4$. Since removing an edge is the smallest possible operation that can be done from $K_{3,3}$, there is no subset family with five SDRs.
