The number of a family of sequences of subsets of $\{1,2,\cdots,n\}$

Question

Given integers $m,n\geq 1$, let $W_{n,m}$ denote the family of all sequences $S_1,S_2,\cdots,S_m$ satisfying

(1) every $S_i$ is a subset of $\{1,2,\cdots,n\}$;

(2) $\mid S_i\cap S_j\mid\geq 3$ for all $1\leq i<j\leq m$.

How to calculate $\mid W_{n,m}\mid$? Is there any known formula for $\mid W_{n,m}\mid$?

Furthermore, if we denote $W_{n,m}^{+}$ to be the subset of $W_{n,m}$ as follow： $$W_{n,m}^{+}=\{(S_1,S_2,\cdots,S_m)\in W_{n,m}:\ \mid S_1\mid+\mid S_2\mid+\cdots\mid S_m\mid\equiv 0 \pmod{2}\}$$ How to calculate $\mid W_{n,m}^{+}\mid$?

Answer 1

One can represent such a sequence as an $m$ by $n$ (binary) Incidence matrix. The problem is then one of counting such matrices, and the exact enumeration is (as far as my ignorance permits) not expressible by a nice formula. However, some bounds can be nicely expressed.

The trivial upper bound $2^{nm}$ comes from counting all matrices of all sequences, and can be slightly refined by looking at those where (say) every row corresponds to a subset of size at least 3. If we restrict sets to size Ceil(n/2)+2 or greater we get a lower bound a little less than $2^{nm-m}$, as any sequence composed of all these sets will work, and they represent almost half of all subsets of $n$. For large $n$, I imagine both your quantities are closer to the lower bound, but I do not have a proof.

If you have time to do a computer enumeration, you can try depth first search. The nice thing is that the set S of possible jth members of a given partial sequence contains the set S' of possible (j+1)th members of that sequence, so you can certain routines to anticipate results from certain subtrees.

Regarding the parity of such sequences, you can almost always add an element to the last sequence member, so I imagine the plus quantity is rather close to half the total quantity. I would be surprised to see otherwise for any n and m greater than 4.

Gerhard "Wonders If Count Is Useful" Paseman, 2018.05.29.