A007363 - OEIS

A007363

Maximal self-dual antichains on n points.
(Formerly M2505)

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

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

Table of n, a(n) for n=1..8.

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

FORMULA

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

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

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.