A321982 -id:A321982 - cp's OEIS frontend

A321979 Number of e-positive simple labeled graphs on n vertices.

1, 1, 2, 8, 60, 899

Offset: 0

Gus Wiseman, Nov 23 2018

A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895). A graph is e-positive if, in the expansion of its chromatic symmetric function in terms of elementary symmetric functions, all coefficients are nonnegative.

			The 4 non-e-positive simple labeled graphs on 4 vertices are:
  {{1,2},{1,3},{1,4}}
  {{1,2},{2,3},{2,4}}
  {{1,3},{2,3},{3,4}}
  {{1,4},{2,4},{3,4}}

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
Richard P. Stanley and John R. Stembridge, On immanants of Jacobi-Trudi matrices and permutations with restricted position, Journal of Combinatorial Theory Series A 62-2 (1993), 261-279.
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.
Gus Wiseman, The a(4) = 60 e-positive simple labeled graphs.

Cf. A000569, A006125, A229048, A240936, A277203, A321895, A321911, A321918, A321914, A321931, A321980, A321981, A321982.

A321980 Row n gives the chromatic symmetric function of the n-path, expanded in terms of elementary symmetric functions and ordered by Heinz number.

Original entry on oeis.org

1, 2, 0, 3, 1, 0, 4, 2, 2, 0, 0, 5, 3, 7, 1, 0, 0, 0, 6, 10, 4, 6, 2, 0, 4, 0, 0, 0, 0, 7, 5, 13, 17, 6, 0, 11, 4, 1, 0, 0, 0, 0, 0, 0, 8, 6, 16, 12, 0, 22, 16, 8, 12, 20, 2, 0, 0, 6, 0, 0, 0, 0, 0, 0, 0, 0, 9, 7, 19, 27, 0, 31, 10, 9, 21, 0, 58, 16, 12, 9, 0

Offset: 1

Gus Wiseman, Nov 23 2018

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).
A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895).
All terms are nonnegative [Stanley].

			Triangle begins:
  1
  2  0
  3  1  0
  4  2  2  0  0
  5  3  7  1  0  0  0
  6 10  4  6  2  0  4  0  0  0  0
  7  5 13 17  6  0 11  4  1  0  0  0  0  0  0
  8  6 16 12  0 22 16  8 12 20  2  0  0  6  0  0  0  0  0  0  0  0
For example, row 6 gives: X_P6 = 6e(6) + 10e(42) + 4e(51) + 6e(33) + 2e(222) + 4e(321).

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Row sums are A000079.

Cf. A000569, A001187, A001349, A006125, A056239, A229048, A240936, A245883, A277203, A321911, A321918, A321914, A321979, A321981, A321982.

A207864 Number of n X 2 nonnegative integer arrays with new values 0 upwards introduced in row major order and no element equal to any horizontal or vertical neighbor (colorings ignoring permutations of colors).

Original entry on oeis.org

1, 4, 34, 500, 10900, 322768, 12297768, 580849872, 33093252880, 2227152575552, 174131286983712, 15604440074084672, 1584856558077903168, 180712593036822482176, 22946861101272125055616, 3222156375409363475703040

Offset: 1

R. H. Hardin, Feb 21 2012

nonn

From Gus Wiseman, Mar 01 2019: (Start)
Also the number of stable partitions of the n-ladder graph. A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The n-ladder has 2n vertices and looks like:
  o-o-o-   -o
  | | | ... |
  o-o-o-   -o
(End)

			Some solutions for n=5:
  0 1   0 1   0 1   0 1   0 1   0 1   0 1   0 1   0 1   0 1
  1 0   1 0   1 2   1 2   1 0   1 0   1 2   1 0   1 0   1 0
  0 1   0 1   0 1   0 1   2 1   0 1   0 1   0 2   2 1   0 1
  1 2   1 0   1 0   1 3   3 0   2 0   3 2   2 1   1 0   1 2
  0 1   0 1   2 1   2 4   1 2   0 1   0 1   0 2   0 1   2 0

R. H. Hardin, Table of n, a(n) for n = 1..61

Column 2 of A207868.

Cf. A000110, A000569, A109808, A229048, A240936, A321750, A321979, A321980, A321982, A322064.

Table[Expand[x*(x-1)*(x^2-3*x+3)^(n-1)]/.x^k_.->BellB[k],{n,20}] (* Gus Wiseman, Mar 01 2019 *)

It appears that the sequence terms are given by the Dobinski-type formula a(n+1) = (1/e) * Sum_{k>=0} (1+k+k^2)^n/k!. - Peter Bala, Mar 12 2012

Apply x^n -> B(n) to the polynomial chi(n) = x (x - 1) (x^2 - 3 x + 3)^(n - 1), where B = A000110. - Gus Wiseman, Mar 01 2019

A321981 Row n gives the chromatic symmetric function of the n-girder, expanded in terms of elementary symmetric functions and ordered by Heinz number.

Original entry on oeis.org

1, 2, 0, 6, 0, 0, 16, 0, 2, 0, 0, 40, 12, 2, 0, 0, 0, 0, 96, 16, 44, 6, 0, 0, 0, 0, 0, 0, 0, 224, 136, 66, 52, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 0, 512, 384, 208, 96, 30, 178, 0, 18, 30, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1152, 1024, 584, 522, 138, 588, 102

Offset: 1

Gus Wiseman, Nov 23 2018

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).
A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. The chromatic symmetric function is given by X_G = Sum_p m(t(p)) where the sum is over all stable partitions of G, t(p) is the integer partition whose parts are the block-sizes of p, and m is augmented monomial symmetric functions (see A321895).
The n-girder has n vertices and looks like:
  2-4-6-     -n
  |\|\|\ ... \|
  1-3-5-     n-1
Conjecture: All terms are nonnegative (verified up to n = 10). This is a special case of Stanley and Stembridge's poset-chain conjecture.

			Triangle begins:
    1
    2   0
    6   0   0
   16   0   2   0   0
   40  12   2   0   0   0   0
   96  16  44   6   0   0   0   0   0   0   0
  224 136  66  52   2   4   0   2   0   0   0   0   0   0   0
For example, row 6 gives: X_G6 = 96e(6) + 6e(33) + 16e(42) + 44e(51).

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
Richard P. Stanley and John R. Stembridge, On immanants of Jacobi-Trudi matrices and permutations with restricted position, Journal of Combinatorial Theory Series A 62-2 (1993), 261-279.
Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Row sums are A025192.

Cf. A000569, A001187, A006125, A056239, A229048, A240936, A245883, A277203, A321750, A321911, A321918, A321914, A321979, A321980, A321982.

A322066 Number of e-positive antichains of sets spanning n vertices.

Original entry on oeis.org

1, 1, 2, 8, 64, 1299

Offset: 0

Gus Wiseman, Nov 25 2018

A stable partition of a hypergraph or set system is a set partition of the vertices where no non-singleton edge has all its vertices in the same block. The chromatic symmetric function is given by X_G = Sum_pi m(t(pi)) where the sum is over all stable partitions pi of G, t(pi) is the integer partition whose parts are the block-sizes of pi, and m is the basis of augmented monomial symmetric functions (see A321895). A hypergraph or set system is e-positive if, in the expansion of its chromatic symmetric function in terms of elementary functions, all coefficients are nonnegative.

			The a(3) = 8 e-positive antichains:
  {{1},{2,3}}
  {{2},{1,3}}
  {{3},{1,2}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}
  {{1},{2},{3}}
  {{1,2},{1,3},{2,3}}
The antichain {{1,2,3}} is not e-positive, as its chromatic symmetric function is -3e(3) + 3e(21).

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.
Richard P. Stanley, Graph colorings and related symmetric functions: ideas and applications, Discrete Mathematics 193 (1998), 267-286.
Richard P. Stanley and John R. Stembridge, On immanants of Jacobi-Trudi matrices and permutations with restricted position, Journal of Combinatorial Theory Series A 62-2 (1993), 261-279.

Cf. A006125, A229048, A240936, A277203, A321895, A321914, A321918, A321931, A321979, A321980, A321981, A321982, A321994, A322012.

cp's OEIS Frontend

A321979 Number of e-positive simple labeled graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A321980 Row n gives the chromatic symmetric function of the n-path, expanded in terms of elementary symmetric functions and ordered by Heinz number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A207864 Number of n X 2 nonnegative integer arrays with new values 0 upwards introduced in row major order and no element equal to any horizontal or vertical neighbor (colorings ignoring permutations of colors).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A321981 Row n gives the chromatic symmetric function of the n-girder, expanded in terms of elementary symmetric functions and ordered by Heinz number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A322066 Number of e-positive antichains of sets spanning n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs