(This is a spin-off of [Determine the minimal elements of a Dynkin system generated by a finite set of finite sets](https://mathoverflow.net/q/405305))


Let $\Omega$ be a finite set. A [Dynkin system](https://en.wikipedia.org/wiki/Dynkin_system) on $\Omega$ is a subset of the power set of $\Omega$ containing $\Omega$, which is closed under complements in $\Omega$ and which is closed under union of disjoint sets.


Given any subset $\mathcal E$ of the power set of $\Omega$, there is a unique minimal Dynkin system $\delta(\mathcal E)$, the Dynkin system generated by $\mathcal E$.


Any Dynkin system is characterised by its minimal non-empty sets. If $\Omega$ has at most three elements, the Dynkin systems are in bijection with the set partitions. If $\Omega$ has four elements, there are four Dynkin systems whose minimal non-empty sets do not form a set partition:


* $\{\{0, 1\}, \{0, 3\}, \{1, 2\}, \{2, 3\}\}$
* $\{\{0, 1\}, \{0, 2\}, \{1, 3\}, \{2, 3\}\}$
* $\{\{0, 2\}, \{0, 3\}, \{1, 2\}, \{1, 3\}\}$
* $\{\{0, 1\}, \{0, 2\}, \{0, 3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}\}$


**Questions:**


* Can we compute the number of Dynkin systems?
* Can we compute the number of Dynkin systems up to relabelling?



What is the number of finite Dynkin systems?
We can compute the number of Dynkin systems for small $n$ using an almost-brute-force method. For efficient computation we represent a set ${a\_i}$ as a binary number $\sum\_i 2^{a\_i}$; then $\Omega = \{0, 1, 2, \ldots, n-1\}$ is represented by $2^n - 1$ and we can compute the complement with bitwise exclusive or by $2^n - 1$. This numeric representation also gives a straightforward total ordering to the subsets of $\Omega$.


The computational state consists of three sets: a subset of $\Omega$ which is included in the system; a subset which is excluded from the system; and a subset which is as yet undecided. Initially the included set is $\{ \emptyset, \Omega \}$, the excluded set is empty, and the undecided set contains the rest of the powerset of $\Omega$. At each stage we case split on the condition of the least (in the total ordering) undecided subset: either it is in the included set, in which case we apply the closure properties and verify that they don't require an excluded subset; or it isn't, in which case we add it (and its complement) to the excluded set.


I did have some ideas for approaches which should be more efficient asymptotically, but at the sizes which are practical to calculate they slow the computation down.


Python code, considerably optimised over the version I posted earlier in a comment:



```
def extend_closure(omega, included, extension, excluded):
    # We start with a closure which we want to extend
    closure = set(included)

    # Use a queue
    q = set([extension])
    while q:
        x = next(iter(q))
        q.remove(x)
        closure.add(x)

        # Ensure the complement closure too
        if (omega ^ x) not in closure:
            # Shortcut contradictions
            if (omega ^ x) in excluded:
                return None

            q.add(omega ^ x)

        for y in closure:
            if (x & y) == 0 and (x | y) not in closure:
                # Shortcut contradictions
                if (x | y) in excluded:
                    return None

                q.add(x | y)

    return closure


def enumerate_dynkin(n):
    omega = (1 << n) - 1

    def inner(included, lb, excluded):
        yield included

        for min in range(lb, (omega + 1) >> 1):
            if min in included or min in excluded:
                continue

            # Consider the implications of adding min
            ninc = extend_closure(omega, included, min, excluded)
            if ninc:
                for sys in inner(ninc, min + 1, set(excluded)):
                    yield sys

            # Consider systems without min
            excluded.add(min)
            excluded.add(omega ^ min)

    for sys in inner(set([0, omega]), 1, set()): yield sys


for n in range(9):
    print(n, sum(1 for _ in enumerate_dynkin(n)))

```

On my desktop machine, with the pypy3 implementation of Python, this computes up to $n=7$ inclusive in under ten seconds, and $n=8$ in about 36 days.


Results:



```
n systems
0 1
1 1
2 2
3 5
4 19
5 137
6 3708
7 1506404
8 230328505024

```

In principle the same approach could be extended to handle relabelling: in the branch of the case split where we exclude a subset, we could also exclude all subsets which are equivalent to it under relabelling. But actually calculating that gets a bit tricky. It might actually be easier to generate, group by basic statistics like the number of subsets of each cardinality, and then test for relabelling equivalence within each group. I haven't implemented either approach.


