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

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

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.

Sequence in context: A171864 A256093 A066902 * A103991 A224994 A321768

Adjacent sequences: A007360 A007361 A007362 * A007364 A007365 A007366

Keyword

nonn,more

Author

N. J. A. Sloane

Extensions

a(8) from Elijah Beregovsky, May 06 2020

Status

approved