A007363 Maximal self-dual antichains on n points.

0, 1, 3, 5, 20, 168, 11748, 12160647

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• more

Comments

From Gus Wiseman, Jul 02 2019: (Start)

If self-dual means (pairwise) intersecting, then a(n) is the number of maximal intersecting antichains of nonempty subsets of {1..(n - 1)}. A set of sets is an antichain if no part is a subset of any other, and is intersecting if no two parts are disjoint. For example, the a(2) = 1 through a(5) = 20 maximal intersecting antichains are:

{1} {1} {1} {1}

{2} {2} {2}

{12} {3} {3}

{123} {4}

{12}{13}{23} {1234}

{12}{13}{23}

{12}{14}{24}

{13}{14}{34}

{23}{24}{34}

{12}{134}{234}

{13}{124}{234}

{14}{123}{234}

{23}{124}{134}

{24}{123}{134}

{34}{123}{124}

{12}{13}{14}{234}

{12}{23}{24}{134}

{13}{23}{34}{124}

{14}{24}{34}{123}

{123}{124}{134}{234}

(End)

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Daniel E. Loeb, On Games, Voting Schemes and Distributive Lattices. LaBRI Report 625-93, University of Bordeaux I, 1993. [Broken link]

Crossrefs

Intersecting antichains are A326372.

Intersecting antichains of nonempty sets are A001206.

Unlabeled intersecting antichains are A305857.

Maximal antichains of nonempty sets are A326359.

The case with empty edges allowed is A326363.

Cf. A000372, A305844, A306007, A326358, A326361, A326362, A326366.

Programs

Mathematica

stableSets[u_,Q_]:=If[Length[u]==0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r==w||Q[r,w]||Q[w,r]],Q]]]];
fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n],{1,n}],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&]]],{n,0,5}] (* Gus Wiseman, Jul 02 2019 *)
(* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = FindClique[g, Infinity, All];
Length[sets]-1 (* Elijah Beregovsky, May 06 2020 *)

Formula

For n > 0, a(n) = A326363(n - 1) - 1 = A326362(n - 1) + n - 1. - Gus Wiseman, Jul 03 2019

Extensions

a(8) from Elijah Beregovsky, May 06 2020