A367494 Number of (2+2)-free naturally labeled posets on [n].

1, 1, 2, 7, 37, 272, 2637, 32469, 493602, 9062503, 197409097, 5027822588, 147896295785, 4972353491993, 189357434418082, 8104194176872583, 387121098095180237, 20513320778472547576, 1199236185075846230469, 76970026071431034905229, 5399593095642890354948802

Offset: 0

Author

David Bevan, Nov 20 2023

Keywords

• nonn

Comments

A partial order R is naturally labeled if xRy => x

A partial order is (2+2)-free if it does not contain an induced subposet that is isomorphic to the union of two disjoint 2-element chains.

Examples

			a(3) = A006455(3) = 7: {}, {1R2}, {1R3}, {2R3}, {1R2, 1R3}, {1R3, 2R3}, {1R2, 1R3, 2R3}.
a(4) = A006455(4) - 3 = 37: {1R2, 3R4}, {1R3, 2R4} and {1R4, 2R3} (trivially) contain a 2+2 subposet.
		

Links

• David Bevan, Gi-Sang Cheon, and Sergey Kitaev, On naturally labelled posets and permutations avoiding 12-34, arXiv:2311.08023 [math.CO], 2023.

Crossrefs

Cf. A006455 (naturally labeled posets), A113226 ({3,2+2}-free naturally labeled posets).

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.