A277687 a(n) is the number of nonisomorphic trees on n vertices whose chromatic symmetric function in the p basis has a nonzero coefficient for each possible term.

1, 1, 1, 1, 2, 1, 4, 2, 4, 2, 18, 2, 29, 5, 8, 9, 97, 7, 148, 9, 25, 20

Offset

1,5

Comments

The path graph is always included in this count.

The chromatic symmetric function is defined in Stanley (1995). By theorem 2.5 of that reference we can give an equivalent definition of this sequence. Say that a forest corresponds to the partition whose parts are the sizes of the trees in the forest. Then a(n) counts the trees on n vertices for which a forest corresponding to any partition of n can be produced by deleting edges from the tree. - Peter J. Taylor, Sep 03 2021

Links

Table of n, a(n) for n=1..22.

Richard P. Stanley, A symmetric function generalization of the chromatic polynomial of a graph, Advances in Math. 111 (1995), 166-194.

Example

For n = 5 there are three trees, but a(5) = 2 because the star tree cannot be split into a tree of size 2 and a tree of size 3. - Peter J. Taylor, Sep 03 2021

Crossrefs

Cf. A277686.

Sequence in context: A086449 A321088 A070556 * A065295 A296604 A261211

Adjacent sequences: A277684 A277685 A277686 * A277688 A277689 A277690

Keyword

nonn,more

Author

Caleb Ji, Sam Heil, Oct 26 2016

Extensions

a(16)-a(22) from Peter J. Taylor, Sep 03 2021

Status

approved