A380571 Number of Dynkin systems on [n].

1, 1, 2, 5, 19, 137, 3708, 1506404, 230328505024

Offset: 0

Author

Peter J. Taylor, Feb 24 2025

Keywords

• nonn
• hard
• more

Comments

A Dynkin system on a set S is a subset of the power set of S which contains the empty set, is closed under complements in S, and is closed under union of disjoint sets.

Examples

			The a(3) = 5 systems are:
  {{}, {1,2,3}}
  {{}, {1}, {2,3}, {1,2,3}}
  {{}, {2}, {1,3}, {1,2,3}}
  {{}, {3}, {1,2}, {1,2,3}}
  {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}
The a(4) = 19 systems are 15 sigma-algebras counted by A000110(4) and 4 other systems:
  {{}, {1,2,3,4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}
  {{}, {1,2,3,4}, {1,2}, {1,3}, {2,4}, {3,4}}
  {{}, {1,2,3,4}, {1,2}, {1,4}, {2,3}, {3,4}}
  {{}, {1,2,3,4}, {1,3}, {1,4}, {2,3}, {2,4}}
		

Links

• Martin Rubey and Peter Taylor, What is the number of finite Dynkin systems?, MathOverflow.
• Wikipedia, Dynkin system

Crossrefs

Cf. A000110, A102894, A381471 (unlabeled case).

Formula

a(n) >= A000110(n).