A079145 -id:A079145 - cp's OEIS frontend

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

1, 2, 5, 15, 49, 173, 639, 2469, 9997, 43109, 205092, 1153646, 8523086, 91156133, 1446766659, 32998508358, 1047766596136, 45632564217917, 2711308588849394, 219364550983697100, 24151476334929009951, 3618445112608409433287

Offset: 1

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

nonn

M. Guay-Paquet, A modular relation for the chromatic symmetric functions of (3+1)-free posets, arXiv preprint arXiv:1306.2400 [math.CO], 2013.
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. A079145 (labeled semitransitive orders), A000112.

nmax = 23; co = Coefficient; ex = Exponent;
b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i<1, {}, Flatten[Table[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] co[s, x, i] co[t, x, j], {j, 1, ex[t, x]}], {i, 1, ex[s, x]}]/Product[i^co[s, x, i]*co[s, x, i]!, {i, 1, ex[s, x]}]/Product[i^co[t, x, i] co[t, x, i]!, {i, 1, ex[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[n] x^n, {n, 0, nmax}];
S[, ] = 0; Do[S[c_, t_] = Series[1 + (c/(1 + c)) S[c, t]^2 + t S[c, t]^3, {c, 0, nmax}, {t, 0, nmax}] // Normal, {nmax}];
T[x_] = 1 - S[x/(1 - x), 1 - 2x - 1/B[x]];
Rest[CoefficientList[-T[x] + O[x]^nmax, x]] (* Jean-François Alcover, Aug 11 2018, after Alois P. Heinz *)

G.f.: S(x/(1-x), T(x)), where S(x, y) is the g.f. for A221494 and T(x) is the g.f. for A221492. [Mathieu Guay-Paquet, Jan 18 2013]

More terms from Mathieu Guay-Paquet, Jan 18 2013

A221493 Number of tangled bicolored graphs on n labeled vertices.

Original entry on oeis.org

0, 0, 0, 0, 12, 120, 2460, 64680, 2323692, 111920760, 7272700860, 639739653960, 76764606923532, 12645557866982040, 2878366780307114460, 909775941009828296040, 401039212596034472197932, 247339947733328456032703160, 214013123181627427780427544060

Offset: 0

Mathieu Guay-Paquet, Jan 18 2013

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. Given 4 labels, there are 12 distinct ways of labeling the vertices, so a(4) = 1.

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. A221492, A079145.

nmax = 19;
B[x_] = Sum[Exp[2^n x] x^n/n!, {n, 0, nmax}] + O[x]^nmax;
T[x_] = 2 Exp[-x] - 1 - 1/B[x] + O[x]^nmax;
CoefficientList[T[x], x] Range[0, nmax-1]! (* Jean-François Alcover, Aug 12 2018 *)

E.g.f.: T(x) = 2*e^(-x) - 1 - 1/B(x), where B(x) is the e.g.f. for A047863.

A222863 Strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Original entry on oeis.org

1, 1, 3, 13, 111, 1381, 22383, 461413, 12163791, 420626821, 19880808303, 1337330559973, 130909732781391, 18649561895661061, 3830195104867879023, 1124247654215697637093, 469367653568553278229711, 278046313987470874905216901, 233462156432002170491075384943

Offset: 0

Joel B. Lewis, Mar 07 2013

nonn

Here "strongly graded" means that every maximal chain has the same length. Alternate terminology includes "graded" (e.g., in Stanley 2012) and "tiered" (as in A006860). A poset is said to be (3+1)-free if it does not contain four elements a, b, c, d such that a < b < c and d is incomparable to the other three.

R. P. Stanley, Enumerative Combinatorics, Volume 1. Cambridge University Press. 2nd edition, 2012. http://math.mit.edu/~rstan/ec/ec1/

J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, J. Combin. Theory Ser. A 120 (2013), no. 6, 1305-1327.

For strongly graded (3+1)-free posets by height, see A222864. For weakly graded (3+1)-free posets, see A222865. For all strongly graded posets, see A006860. For all (3+1)-free posets, see A079145.

m = maxExponent = 19;
Psi[x_] = Sum[E^(2^n*x)*x^n/n!, {n, 0, m}] + O[x]^m;
H[x_, y_] = 1+(2x^3 - 3x^2 + (x^3 - 4x^2 + 4x)y)/(2x^2 + x + (x^2-2x-1) y);
CoefficientList[H[E^x, Psi[x]] + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Dec 11 2018 *)

G.f.: H(e^x, Psi(x)) where H(x, y) = 1 + (2x^3 - 3x^2 + (x^3 - 4x^2 + 4x)y)/(2x^2 + x + (x^2 - 2x - 1)y) and Psi(x) is the g.f. for A047863.

A222864 Triangle T(n,k) of strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices with height k.

Original entry on oeis.org

1, 1, 2, 1, 6, 6, 1, 50, 36, 24, 1, 510, 510, 240, 120, 1, 7682, 7380, 4800, 1800, 720, 1, 161406, 141246, 91560, 47040, 15120, 5040, 1, 4747010, 3444756, 2162664, 1134000, 493920, 141120, 40320, 1, 194342910, 110729310, 61286400, 32253480, 14605920, 5594400

Offset: 1

Joel B. Lewis, Mar 07 2013

Here "strongly graded" means that every maximal chain has the same length. Alternate terminology includes "graded" (e.g., in Stanley 2011) and "tiered" (as in A006860). A poset is said to be (3+1)-free if it does not contain four elements a, b, c, d such that a < b < c and d is incomparable to the other three.

			For n = 3, there is 1 strongly graded poset of height 1 (the antichain), 6 strongly graded posets of height 2, and 6 strongly graded posets of height 3 (the chains), and all of these are (3+1)-free. Thus, the third row of the triangle is 1, 6, 6.

Joel B. Lewis, Rows n = 1..20 of triangle, flattened
J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, J. Combin. Theory Ser. A 120 (2013), no. 6, 1305-1327.

For row-sums (strongly graded (3+1)-free posets with n labeled vertices, disregarding height), see A222863. For weakly graded (3+1)-free posets, see A222865. For all strongly graded posets, see A006860. For all (3+1)-free posets, see A079145.

G.f. is given in the Lewis-Zhang paper.

A222865 Weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Original entry on oeis.org

1, 1, 3, 19, 195, 2551, 41343, 826939, 20616795, 658486351, 28264985223, 1725711709459, 155998194920835, 21019550046219271, 4162663551546902223, 1192847436856343300779, 489879387071459457083115, 286844271719979335180726911, 238844671940165660117456403543

Offset: 0

Joel B. Lewis, Mar 07 2013

nonn

Here "weakly graded" means that there is a rank function rk from the vertices to the integers such that whenever x covers y we have rk(x) = rk(y) + 1. Alternate terminology includes "graded" and "ranked." A poset is said to be (3+1)-free if it does not contain four vertices a, b, c, d such that a < b < c and d is incomparable to the other three.

J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, To appear, J. Combinatorial Theory, Series A.

For weakly graded (3+1)-free posets by height, see A222866. For strongly graded (3+1)-free posets, see A222863. For all weakly graded posets, see A001833. For all (3+1)-free posets, see A079145.

m = maxExponent = 19;
Psi[x_] = Sum[E^(2^n x) x^n/n!, {n, 0, m}] + O[x]^m;
W[x_, y_] = (1-x)y/x + (2x^3 + (x^3 - 2x^2)y)/(2x^2 + x + (x^2-2x-1) y);
CoefficientList[W[E^x, Psi[x]] + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Dec 11 2018 *)

G.f. is W(e^x, Psi(x)) where W(x, y) = (1 - x)y/x + (2x^3 + (x^3 - 2x^2)y)/(2x^2 + x + (x^2 - 2x - 1)y) and Psi(x) is the GF for A047863.

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.

A222866 Triangle T(n,k) of weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices with height k.

Original entry on oeis.org

1, 1, 2, 1, 12, 6, 1, 86, 84, 24, 1, 840, 1110, 480, 120, 1, 11642, 16620, 9120, 3240, 720, 1, 227892, 300846, 185640, 82320, 25200, 5040, 1, 6285806, 6810804, 4299624, 2142000, 816480, 221760, 40320, 1, 243593040, 199239270, 117205200, 60890760, 26157600

Offset: 1

Joel B. Lewis, Mar 07 2013

Here "weakly graded" means that there is a rank function rk from the vertices to the integers such that whenever x covers y we have rk(x) = rk(y) + 1. Alternate terminology includes "graded" and "ranked." A poset is said to be (3+1)-free if it does not contain four elements a, b, c, d such that a < b < c and d is incomparable to the other three.

Joel B. Lewis, Rows n = 1..20 of triangle, flattened
J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, J. Combin. Theory Ser. A 120 (2013), no. 6, 1305-1327.

For row-sums (weakly graded (3+1)-free posets with n labeled vertices, disregarding height), see A222865. For strongly graded (3+1)-free posets, see A222863. For all weakly graded posets, see A001833. For all (3+1)-free posets, see A079145.

G.F. is given in the Lewis-Zhang paper.

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A221493 Number of tangled bicolored graphs on n labeled vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A222863 Strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A222864 Triangle T(n,k) of strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices with height k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A222865 Weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Views

Author

Keywords

Comments

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

A222866 Triangle T(n,k) of weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices with height k.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula