# Enumeration of a certain sequence III

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)$$?

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

• Comments are not for extended discussion; this conversation has been moved to chat.
– Kuba
Nov 1, 2022 at 22:30

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} *)

• Thank you so much! I completely understand how such straightforward answers deprive individuals of programming skills. However, I truly needed some values of those sequences for my ongoing research, and I don’t have time to invest in programming. Oct 31, 2022 at 11:14
• Would you mind providing the solution for $\mathrm I$ also since it is an unrelated condition? Oct 31, 2022 at 11:15
• You are welcome! To set your expectation, I’m unlikely to work on the last part - it’s slightly more involved and technical, and I have already satisfied my curiosity by working on the first two parts. Oct 31, 2022 at 23:21
• Re: “I don’t have time to invest in programming” - my friendly advice would be to find some time to invest, esp. given that with WL is extremely useful tool for a mathematician. “An Elementary Introduction” by S. Wolfram is a good start: wolfram.com/language/elementary-introduction/2nd-ed Oct 31, 2022 at 23:25
• Well then, I think this concludes it and that your answer deserves the bounty (@thorimur) :) ! Nov 1, 2022 at 17:35