2
$\begingroup$

Denote by $a(n)$ the number of families $\mathcal{F} \subseteq \mathcal{P}(X)$ on a finite set $X$ with $n$ elements satisfying:

  • $\emptyset, X \in \mathcal{F}$
  • For all $U, V \in \mathcal{F}$ it holds ture that $U \cap V \in \mathcal{F}$
  • For all $x \in X$ it holds true that $\left \{ x \right \} \in \mathcal{F}$

If we were to drop the last restriction, the sequence is given in OEIS as A102894.

Can someone help me to write a code to enumerate the sequence $a(n)$?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Since $|X|=n$ one has $|\mathcal{P}(X)| = 2^n$ and $|\mathcal{P}(\mathcal{P}(X))| = 2^{2^n}$. This means that with a brute force approach, where one tries all subsets of the power set of $X$ and checks whether they satisfy your condition, there are $2^{2^n}$ candidates, which already for $n=6$ is prohibitive. So what is the largest $n$ you hope to get to? And what algorithm do you propose to get there, better than brute force? $\endgroup$
    – user293787
    Commented Jul 29, 2022 at 3:00
  • $\begingroup$ See also this related question. $\endgroup$
    – user293787
    Commented Jul 29, 2022 at 3:57
  • $\begingroup$ Since I needed only the first few terms, I believe a brute force approach is just fine as of now. $\endgroup$
    – user227351
    Commented Jul 29, 2022 at 10:10
  • $\begingroup$ You are counting Hausdorff topologies on X? $\endgroup$
    – Daniel Lichtblau
    Commented Aug 8, 2022 at 7:26
  • $\begingroup$ No, such families $\mathcal{F}$ are not necessarily closed under union. $\endgroup$
    – user227351
    Commented Aug 8, 2022 at 9:27

1 Answer 1

Reset to default
5
$\begingroup$

Adapting the code given in A102894, a brute force approach would be this.

(* Warning: Only use with n <= 4 *)
allCandidates[n_] := Subsets[Subsets[Range[n]]];
allAdmissibleFamilies[n_] := Select[allCandidates[n],And[
                                MemberQ[#,{}],
                                MemberQ[#,Range[n]],
                                SubsetQ[#,Intersection@@@Tuples[#,2]],
                                SubsetQ[#,Map[{#}&,Range[n]]] 
                             ]&];
a[n_] := Length[allAdmissibleFamilies[n]];

With this I get

Table[a[n],{n,0,4}]
(* {1,1,1,8,545} *)

One can also look at the families, for example

allAdmissibleFamilies[3]
(*
  {{{},{1},{2},{3},{1,2,3}},
   {{},{1},{2},{3},{1,2},{1,2,3}},
   {{},{1},{2},{3},{1,3},{1,2,3}},
   {{},{1},{2},{3},{2,3},{1,2,3}},
   {{},{1},{2},{3},{1,2},{1,3},{1,2,3}},
   {{},{1},{2},{3},{1,2},{2,3},{1,2,3}},
   {{},{1},{2},{3},{1,3},{2,3},{1,2,3}},
   {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}}
*)

Note. This code has the benefit of being very readable. I think that might be its only benefit. Not only does it try all candidates, it even generates all candidates at once, which means that one immediately runs out of memory. Hence the recommendation to only use this for n <= 4. The first improvement would be a more memory-friendly brute force approach.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What if we, instead the third condition, required complements of singletons to not be in the family $\mathcal{F}$? I belive we would only need to alter the part SubsetQ[#,Map[{#}&,Range[n]]] ? $\endgroup$
    – user227351
    Commented Jul 29, 2022 at 10:16
  • $\begingroup$ @TianVlašić So no subsets of length $n-1$ you mean. I think you just have to replace SubsetQ[#,Map[{#}&,Range[n]]] by DisjointQ[#,Subsets[Range[n],{n-1}]]. $\endgroup$
    – user293787
    Commented Jul 29, 2022 at 10:22
  • 1
    $\begingroup$ That works thank you! $\endgroup$
    – user227351
    Commented Jul 29, 2022 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.