Enumeration of a certain sequence III

Question

Let’s call a collection $\mathcal{F} \subseteq \mathcal{P}(X)$ satisfying:

• $\emptyset, X \in \mathcal{F}$
• For all $U, V \in \mathcal{F}$ it holds that $U \cap V \in \mathcal{F}$.

special. And let us define $\mathrm{h}(S)=\bigcap_{}^{} \left \{ U : U\supseteq S \wedge U \in \mathcal{F} \right \}$ for all $S \subseteq X$.

We can evaluate the number of special collections on a finite labeled set of n elements via the following code:

    Table[Length[
  Select[Subsets[Subsets[Range[n]]], 
   And[MemberQ[#, {}], MemberQ[#, Range[n]], 
     SubsetQ[#, Intersection @@@ Tuples[#, 2]]] &]], {n, 0, 4}]

Let us introduce the following three conditions that special families may satisfy:

($\mathrm S_2$) For all $x,y \in X, \ x\neq y$ there exists $H \in \mathcal{F}$ such that $X \setminus H \in \mathcal{F}$ and $x \in H$ and $y \in X \setminus H $.

($\mathrm S_3$) For all $x \in X$ and $U \in \mathcal{F}, x \notin U$ there exists $H \in \mathcal{F}$ such that $X \setminus H \in \mathcal{F}$ and $x \in H$ and $U \subseteq X \setminus H $.

($\mathrm I$) For all $S \subseteq X$, the statement $ \forall x,y \in S : \mathrm{h}(\left \{ x,y \right \})\subseteq S$ implies $S \in \mathcal{F}$.

Let us thus by $a_2(n)$, $a_3(n)$ and $a_i(n)$, respectively, denote the denote the number of $\mathrm S_2$, that is, $\mathrm S_3$, that is, $\mathrm I$ special collections on a finite labeled set of n elements.

However, I am not sure how to alter the code such that the condition $\mathrm S_2$, that is, $\mathrm S_3$, that is, $\mathrm I$ is satisfied as well.

Can someone help me to write a code to enumerate the sequences $a_2(n)$, $a_3(n)$ and $a_i(n)$?

I would like to offer my sincere graditude in advance!

NOTE: I still need the code for the condition $(\mathrm I)$.

Answer 1

Solution for $S_2$.

Here is a partial answer (for $S_2$ only), to give you some inspiration.

First, we'll define a function special[n] that generates all special collections (and $a(n)$, of course, is just the length of special[n]):

special[n_] :=
  Select[
   Subsets[Subsets[Range[n]]],
   And[
     MemberQ[#, {}],
     MemberQ[#, Range[n]],
     SubsetQ[#, Intersection @@@ Tuples[#, 2]]] &
   ];
a[n_] := Length@special[n];

Table[a[n], {n, 4}] (* {1, 4, 45, 2271} *)

Let's write your $S_2$ condition on $x$, $y$, and $F$:

s2[x_, y_, F_, n_] :=
 MemberQ[F,
  _?(H |-> With[{H1 = Complement[Range[n], H]},
      MemberQ[F, H1] && MemberQ[H, x] && MemberQ[H1, y]])]

Some comments on what's going on:

1. MemberQ[list, _?f] returns true if at least one member of list satisfies the predicate f - similar to Length@Select[list, f]>0 but faster since it doesn't need to calculate f on every element of list.

2. We use a handy |-> shortcut to define a function with a named argument $H$. With defines a shortcut for the complement of $H$, and the rest is a straightforward translation of your condition.

3. Note that we need $n$ as an explicit argument to $s_2$ in order to calculate the complement.

We can check how $s_2$ works with specific arguments $x=1$ and $y=2$ in special[2]:

Column@special[2]
(*
{{{}, {1, 2}}},
{{{}, {1}, {1, 2}}},
{{{}, {2}, {1, 2}}},
{{{}, {1}, {2}, {1, 2}}}
 *)

Select[special[2], s2[1, 2, #, 2] &] (* {{{}, {1}, {2}, {1, 2}}} *)

Indeed, it's easy to see that only one family - all subsets of $\{1,2\}$ - satisfies $s_2$.

Now, for a given family $F$, we'll check whether it satisfies $s_2$ for all possible pairs $x, y$ (we only need to check for the subsets of length 2 given that the condition is symmetrical on $x, y$). Note that we can re-use the symbol $s_2$ as the function below has arity of 2 and the one defined before has arity of 4:

s2[F_, n_] := AllTrue[
  Subsets[Range[n], {2}],
  s2[#[[1]], #[[2]], F, n] &]

Finally,

a2[n_] := Length@Select[special[n], s2[#, n] &]

Here is a table for the values of $a_2(n)$ for $n=1\dots4$:

Table[a2[n], {n, 4}] (* {1, 1, 4, 167} *)

Answer for $S_3$.

I also wrote the code for $a_3(n)$, and the answer is $1,2,8,121$ for $n=1,\dots,4$.

It was pretty straightforward to do. But in general, I'm not a big fan of answering questions of the type "please write some code for me" :). You would get much bigger mileage from learning some programming basics and showing the places where you got stuck, as opposed to just asking strangers to solve a problem for you.

(Update) Solution for $S_3$.

After some consideration, I decided that's it would be too cruel to not share the solution. So here it is.

The $S_3$ condition is very similar to $S_2$:

s3[x_, U_, F_, n_] :=
 MemberQ[F,
  _?(H |-> With[{H1 = Complement[Range[n], H]},
      MemberQ[F, H1] && MemberQ[H, x] && SubsetQ[H1, U]])]

The somewhat tricky part is to generate all pairs $(x,U)$ for a given $F$. I suggest you to meditate on the following piece of code - most of the ingredients are as described above, FreeQ is the opposite of MemberQ, and Flatten[_, 1] can be looked up in the documentation.

allPairs[F_, n_] := 
 Flatten[(x |-> ({x, #} & /@ Select[F, FreeQ[#, x] &])) /@ Range[n], 
  1]

After this, the s3[F,n] definition is very similar to $s_2$:

s3[F_, n_] := AllTrue[
  allPairs[F, n],
  s3[#[[1]], #[[2]], F, n] &
  ]

And we are ready to calculate $a_3(n)$:

a3[n_] := Length@Select[special[n], s3[#, n] &]
Table[a3[n], {n, 4}] (* {1, 2, 8, 121} *)