A079146 -id:A079146 - cp's OEIS frontend

A079145 Number of labeled semitransitive orders on n elements: (1+3)-free posets.

1, 3, 19, 195, 2791, 51423, 1167979, 32067675, 1064281951, 43806954183, 2376985075939, 186194963282595, 22598045194449271, 4259417828951807343, 1200382884654622348699, 490727012583769876310955, 286998078380075662131967951, 238889878466868543045084230103

Offset: 1

Detlef Pauly (dettodet(AT)yahoo.de), Dec 27 2002

M. Guay-Paquet, A. H. Morales, E. Rowland, Structure and enumeration of (3+1)-free posets (extended abstract), arXiv:1212.5356 [math.CO], 2012.

Cf. A079146 (unlabeled semitransitive orders).

E.g.f.: S(e^x-1, T(x)), where S(x, y) is the g.f. for A221494 and T(x) is the e.g.f. for A221493. [Mathieu Guay-Paquet, Jan 18 2013]

More terms from Mathieu Guay-Paquet, Jan 18 2013

A221492 Number of tangled bicolored graphs on n unlabeled vertices.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 10, 34, 158, 804, 4876, 35516, 319719, 3636064, 53349918, 1025758444, 26132964903, 888605372756, 40526634099476, 2487361532245964, 205991405080129554, 23065538883807036798, 3498567662956243132910

Offset: 0

Mathieu Guay-Paquet, Jan 18 2013

nonn

A bicolored graph on n labeled vertices, k of which are black, and (n-k) of which are white, can be represented as a k X (n-k) matrix, where the (i,j) entry is 1 if the i-th black vertex is adjacent to the j-th white vertex, and 0 otherwise. Then, the graph is tangled if (1) the matrix does not have any rows or columns of all 0's or all 1's; and (2) it is not possible to permute the rows of the matrix and the columns of the matrix to obtain a matrix of the form
[ A | J ]
[---+---]
[ 0 | B ]
where the top right block J consists of all 1's, and the bottom left block 0 consists of all 0's.

			The only tangled bicolored graph on 4 vertices (up to isomorphism) consists of 2 black vertices, 2 white vertices, and 2 edges, with each black vertex joined to a different white vertex.

M. Guay-Paquet, A. H. Morales, E. Rowland, Structure and enumeration of (3+1)-free posets (extended abstract), arXiv:1212.5356 [math.CO], 2012.

Cf. A221493, A079146.

terms = 23;
b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten @ Table[Map[ Function[{p}, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]];
g[n_, k_] := g[n, k] = Sum[Sum[2^Sum[Sum[GCD[i, j]*Coefficient[s, x, i]* Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/ Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n + k, n + k]}], {s, b[n, n]}];
A[n_, k_] := g[Min[n, k], Abs[n - k]];
A[d_] := Sum[A[n, d - n], {n, 0, d}];
B[x_] = Sum[A[d] x^d, {d, 0, terms}];
T[x_] = 1 - 2x - 1/B[x];
CoefficientList[T[x] + O[x]^terms, x] (* Jean-François Alcover, Jan 30 2019, after Alois P. Heinz in A049312 *)

G.f.: T(x) = 1 - 2*x - 1/(1+B(x)), where B(x) is the g.f. for A049312.

A221494 Table read by downward diagonals: T(n,k) = number of skeleta of (3+1)-free posets with n clone sets and k tangles.

Original entry on oeis.org

1, 1, 1, 3, 5, 1, 12, 28, 16, 2, 55, 165, 152, 47, 4, 273, 1001, 1265, 658, 136, 9, 1428, 6188, 9919, 7315, 2547, 392, 21, 7752, 38760, 75208, 71981, 35975, 9252, 1130, 51, 43263, 245157, 558144, 657356, 431599, 159701, 32286, 3262, 127, 246675, 1562275

Offset: 0

Mathieu Guay-Paquet, Jan 18 2013

			There are 28 skeleta of (3+1)-free posets with 1 clone set and 2 tangles.
Table begins
  1   1    3     12      55      273 ...
  1   5   28    165    1001     6188 ...
  1  16  152   1265    9919    75208 ...
  2  47  658   7315   71981   657356 ...
  4 136 2547  35975  431599  4660516 ...
  9 392 9252 159701 2277821 28589750 ...
  ......................................

M. Guay-Paquet, A. H. Morales, and E. Rowland, Structure and enumeration of (3+1)-free posets (extended abstract), arXiv:1212.5356 [math.CO], 2012.

Cf. A079145, A079146, A221492, A221493

G.f.: S(x, y) is the unique power series solution of the equation S(x, y) = 1 + S(x, y)^2 * x / (1 + x) + S(x, y)^3 * y.

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

Original entry on oeis.org

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

Stephan Wagner, Mar 28 2018

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

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.

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

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}]

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

A230090 A certain restricted class of posets on n points.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 5, 11, 35635

Offset: 1

N. J. A. Sloane, Oct 09 2013

See Guay-Paquet for precise definition.

M. Guay-Paquet, A modular relation for the chromatic symmetric functions of (3+1)-free posets, arXiv preprint arXiv:1306.2400 [math.CO], 2013.

Cf. A000112, A079146.

cp's OEIS Frontend

A079145 Number of labeled semitransitive orders on n elements: (1+3)-free posets.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A221492 Number of tangled bicolored graphs on n unlabeled vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A221494 Table read by downward diagonals: T(n,k) = number of skeleta of (3+1)-free posets with n clone sets and k tangles.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A230090 A certain restricted class of posets on n points.

Views

Author

Keywords

Comments

Links

Crossrefs