A301871 Number of N- and bowtie-free posets with n elements.

1, 2, 5, 14, 40, 121, 373, 1184, 3823, 12554, 41733, 140301, 475934, 1627440, 5602983, 19406703, 67574371, 236409625, 830582851, 2929246932, 10366380583, 36801225872, 131021870786, 467701875135, 1673584553886, 6002046468815, 21570135722058, 77668429499325, 280167079428684, 1012323004985313

Offset: 1

Author

Stephan Wagner, Mar 28 2018

Keywords

• nonn
• easy

Comments

The number of n-element posets that do not include the two 4-element posets "N" and "bowtie" as induced subposets.

Links

• Stephan Wagner, Table of n, a(n) for n = 1..100
• T. Hasebe and S. Tsujie, Order quasisymmetric functions distinguish rooted trees, arXiv:1610.03908 [math.CO], 2016-2017.
• T. Hasebe and S. Tsujie, Order quasisymmetric functions distinguish rooted trees, Journal of Algebraic Combinatorics 46 (2017), 499-515.
• V. Razanajatovo Misanantenaina and S. Wagner, A Tutte-like polynomial for rooted trees and specific posets, arXiv:1803.09623 [math.CO], 2018.

Crossrefs

Cf. A000112, A003430, A079144, A079146 for related sequences regarding the enumeration of unlabeled posets.

Programs

Mathematica

V=1;Do[V = Normal[Series[(1 - x) Exp[Sum[(2 x^m - x^(2 m)) (V /. x -> x^m)/m, {m, 1, n}]], {x, 0, n}]], {n, 1, 20}]; Table[Coefficient[V,x,n],{n, 1, 20}]

Formula

G.f. V(x) = 1 + x + 2x + 5x^2 + ... satisfies V(x) = (1-x)exp[sum_{m >=1} (2x^m-x^(2m))V(x^m)/m] (see Razanajatovo Misanantenaina/Wagner).