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,3

Comments

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

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.

Links

Table of n, a(n) for n=0..20.

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

Example

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.

Crossrefs

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

Sequence in context: A107877 A001028 A116481 * A102743 A195068 A342412

Adjacent sequences: A367491 A367492 A367493 * A367495 A367496 A367497

Keyword

nonn

Author

David Bevan, Nov 20 2023

Status

approved