Caleb Ji - cp's OEIS frontend

A277686 The number of nonisomorphic graphs on n vertices whose chromatic symmetric function in the p basis has a nonzero coefficient for each possible term.

1, 1, 2, 5, 20, 91, 823

Offset: 1

Caleb Ji, Sam Heil, Oct 26 2016

All graphs with a Hamiltonian path are included in this count. The smallest n for which a graph with n vertices satisfies this property and does not have a Hamiltonian path is n=5.

Cf. A277686.

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.

Original entry on oeis.org

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

Offset: 1

Caleb Ji, Sam Heil, Oct 26 2016

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

			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

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

Cf. A277686.

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

A277203 Number of distinct chromatic symmetric functions realizable by a graph on n vertices.

Original entry on oeis.org

1, 2, 4, 11, 33, 146, 939, 10932

Offset: 1

Sam Heil and Caleb Ji, Oct 04 2016

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). - Gus Wiseman, Nov 21 2018

			For n = 3, under the p basis, the CSF's are: p_{1, 1, 1}, p_{1, 1, 1} - p_{2, 1}, p_{1, 1, 1} - 2p_{2, 1} + p_{3}, p_{1, 1, 1} - 3p_{2, 1} + 2p_{3}.
From _Gus Wiseman_, Nov 21 2018: (Start)
The a(4) = 11 chromatic symmetric functions (m is the augmented monomial symmetric function basis):
                                     m(1111)
                            m(211) + m(1111)
                           2m(211) + m(1111)
          m(22) +          2m(211) + m(1111)
                           3m(211) + m(1111)
          m(22) +          3m(211) + m(1111)
                   m(31) + 3m(211) + m(1111)
         2m(22) +          4m(211) + m(1111)
          m(22) +  m(31) + 4m(211) + m(1111)
         2m(22) + 2m(31) + 5m(211) + m(1111)
  m(4) + 3m(22) + 4m(31) + 6m(211) + m(1111)
(End)

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.

Cf. A000088, A000110, A000569, A006125, A229048, A240936, A245883, A277204, A277205, A321750, A321751, A321895, A321911.

spsu[,{}]:={{}};spsu[foo,set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,_}];
chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
simpleSpans[n_]:=simpleSpans[n]=If[n==0,{{}},Union@@Table[If[#=={},Union[ine,{{n}}],Union[Complement[ine,List/@#],{#,n}&/@#]]&/@Subsets[Range[n-1]],{ine,simpleSpans[n-1]}]];
Table[Length[Union[chromSF/@simpleSpans[n]]],{n,6}] (* Gus Wiseman, Nov 21 2018 *)

A277204 Number of chromatic symmetric functions realizable from exactly one graph on n vertices.

Original entry on oeis.org

1, 2, 4, 11, 33, 146, 846, 9807, 229972

Offset: 1

Sam Heil and Caleb Ji, Oct 04 2016

Cf. A277203.

A277205 Number of chromatic symmetric functions realizable by exactly 2 graphs on n vertices.

Original entry on oeis.org

0, 0, 0, 0, 1, 10, 81, 907, 16111

Offset: 1

Sam Heil and Caleb Ji, Oct 04 2016

Cf. A277203, A277204.

A276031 Number of edges in the graded poset of the partitions of n taken modulo 3, where a partition into k parts is joined to a partition into k+1 parts if the latter is a refinement of the former.

Original entry on oeis.org

0, 1, 2, 5, 9, 14, 21, 30, 41, 54, 70, 89, 110, 135, 164, 195, 231, 272, 315, 364, 419, 476, 540, 611, 684, 765, 854, 945, 1045, 1154, 1265, 1386, 1517, 1650, 1794, 1949, 2106, 2275, 2456, 2639, 2835, 3044, 3255, 3480, 3719, 3960, 4216, 4487, 4760, 5049, 5354

Offset: 1

Caleb Ji, Aug 17 2016

nonn

			a(6) = 14, the 14 edges are:  (111111) - (21111), (21111) - (1110), (21111) - (2211), (1110) - (111), (1110) - (210), (2211) - (111), (2211) - (210), (2211) - (222), (210) - (00), (210) - (21), (111) - (21), (222) - (21), (00) - (0), (21) - (0).

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A000097, A140144.

G.f.: (x^6-2*x^5+x^4-x^3+2*x^2+1)*x^2/((x^2+x+1)^2*(x-1)^4). - Alois P. Heinz, Aug 27 2016

More terms from Alois P. Heinz, Aug 27 2016

A276033 Number of generalizations of the partition 1^n with all elements taken modulo 2.

Original entry on oeis.org

1, 2, 3, 6, 8, 17, 22, 50, 64, 154, 196, 493, 625, 1626, 2055, 5487, 6917, 18851, 23713, 65703, 82499, 231725, 290511, 825399, 1033411, 2964951, 3707851, 10728256, 13402696, 39065521, 48760366, 143047486, 178405156, 526399066, 656043856, 1945668346, 2423307046

Offset: 1

Caleb Ji, Aug 17 2016

nonn

Consider the ranked poset L(n) of partitions defined in A002846, and take the elements of each node modulo 2, collapsing two equivalent nodes into 1. Then a(n) is the total number of paths of all lengths 0,1,...,n-1 that start at any node in the poset and end at 1^n.
Odd-indexed terms are the partial sums of Catalan numbers: A014138.  Even-indexed terms a_{2n} are C_n (the n-th Catalan number) less than the following odd-indexed term.
Originally this entry had a reference to a paper on the arXiv by Caleb Ji, Enumerative Properties of Posets Corresponding to a Certain Class of No Strategy Games, arXiv:1608.06025 [math.CO], 2016. However, this article has since been removed from the arXiv. - N. J. A. Sloane, Sep 07 2018

Cf. A276032, A014138.

A276032 Number of refinements of the partition n^1 with all numbers taken modulo 2.

Original entry on oeis.org

1, 2, 3, 7, 8, 21, 22, 63, 64, 195, 196, 624, 625, 2054, 2055, 6916, 6917, 23712, 23713, 82498, 82499, 290510, 290511, 1033410, 1033411, 3707850, 3707851, 13402695, 13402696, 48760365, 48760366, 178405155, 178405156, 656043855, 656043856, 2423307045

Offset: 1

Caleb Ji, Aug 17 2016

nonn

Consider the ranked poset L(n) of partitions defined in A002846, and take the elements of each node modulo 2, collapsing two equivalent nodes into 1. Then a(n) is the total number of paths of all lengths 0,1,...,n-1 that start at (n mod 2)^1 and end at any node in the poset.
Odd-indexed terms are the partial sums of Catalan numbers: A014138.
Even-indexed terms are one less than the following odd-indexed term.
Originally this entry had a reference to a paper on the arXiv by Caleb Ji, Enumerative Properties of Posets Corresponding to a Certain Class of No Strategy Games, arXiv:1608.06025 [math.CO], 2016. However, this article has since been removed from the arXiv. - N. J. A. Sloane, Sep 07 2018

Cf. A276033, A014138.

A276029 Number of ways to transform a sequence of n ones and n twos to a single number by continually removing two numbers and replacing them with their sum modulo 3.

Original entry on oeis.org

1, 4, 27, 228, 2226, 23778, 270693, 3229106, 39922172, 507680620, 6604676830, 87549425068, 1178880306174, 16086844260290, 222045139578443, 3095457073064120, 43529719213465854, 616853383573066504, 8801227720060618544, 126344910516550743232

Offset: 1

Caleb Ji, Aug 17 2016

nonn

Originally this entry had a reference to a paper on the arXiv by Caleb Ji, Enumerative Properties of Posets Corresponding to a Certain Class of No Strategy Games, arXiv:1608.06025 [math.CO], 2016. However, this article has since been removed from the arXiv. - N. J. A. Sloane, Sep 07 2018

Alois P. Heinz, Table of n, a(n) for n = 1..800

Cf. A276027, A276028.

b:= proc(x, y, z) option remember;
      `if`(x+y+z=1, 1, `if`(y>0 and z>0, b(x+1, y-1, z-1), 0)+
      `if`(x>1 or x>0 and y>0 or x>0 and z>0, b(x-1, y, z), 0)+
      `if`(y>1, b(x, y-2, z+1), 0)+`if`(z>1, b(x, y+1, z-2), 0))
    end:
a:= n-> b(0, n, n):
seq(a(n), n=1..35);  # Alois P. Heinz, Aug 18 2016

b[x_, y_, z_] := b[x, y, z] = If[x + y + z == 1, 1, If[y > 0 && z > 0, b[x + 1, y - 1, z - 1], 0] + If[x > 1 || x > 0 && y > 0 || x > 0 && z > 0, b[x - 1, y, z], 0] + If[y > 1, b[x, y - 2, z + 1], 0] + If[z > 1, b[x, y + 1, z - 2], 0]];
a[n_] := b[0, n, n];
Table[a[n], {n, 1, 35}] (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)

a(n) = b(0, n, n) where f(a, b, c) is the number of ways to reach one number beginning with a zeros, b ones, and c twos.

Then f(a, b, c) = f_1 + f_2 + f_3 + f_4 where f_1 = f(a-1, b, c) if a>=2 or a, b >=1 or a,c >=1, f_2 = f(a, b-2, c+1) if b >= 2, f_3 = f(a, b+1, c-2) if c >= 2, and f_4 = f(a+1, b-1, c-1) if b, c >= 1, and each are 0 otherwise. Initial terms: f(a, b, c) = 1 for all 1 <= a+b+c <= 2, where a, b, c >= 0.

More terms from Alois P. Heinz, Aug 18 2016

A276028 Number of ways to transform a sequence of n zeros and n ones to a single number by continually removing two numbers and replacing them with their sum modulo 3.

Original entry on oeis.org

1, 3, 10, 50, 259, 1540, 9594, 62649, 422598, 2960716, 21030711, 152470357, 1129502128, 8434189996, 63674017174, 488573782216, 3762932025753, 29178861276815, 229208503750838, 1803350026315019, 14248236439629534, 113825380196996557, 909507867095014380

Offset: 1

Caleb Ji, Aug 17 2016

nonn

Also the number of distinct transformations when the initial state consists of n zeros and n twos.

Originally this entry had a reference to a paper on the arXiv by Caleb Ji, Enumerative Properties of Posets Corresponding to a Certain Class of No Strategy Games, arXiv:1608.06025 [math.CO], 2016. However, this article has since been removed from the arXiv. - N. J. A. Sloane, Sep 07 2018

Alois P. Heinz, Table of n, a(n) for n = 1..650

Cf. A276027, A276029.

b:= proc(x, y, z) option remember;
      `if`(x+y+z=1, 1, `if`(y>0 and z>0, b(x+1, y-1, z-1), 0)+
      `if`(x>1 or x>0 and y>0 or x>0 and z>0, b(x-1, y, z), 0)+
      `if`(y>1, b(x, y-2, z+1), 0)+`if`(z>1, b(x, y+1, z-2), 0))
    end:
a:= n-> b(n, n, 0):
seq(a(n), n=1..35);  # Alois P. Heinz, Aug 18 2016

b[x_, y_, z_] := b[x, y, z] = If[x + y + z == 1, 1, If[y > 0 && z > 0, b[x + 1, y - 1, z - 1], 0] + If[x > 1 || x > 0 && y > 0 || x > 0 && z > 0, b[x - 1, y, z], 0] + If[y > 1, b[x, y - 2, z + 1], 0] + If[z > 1, b[x, y + 1, z - 2], 0]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 1, 35}] (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)

a(n) = f(n, n, 0) where f(a, b, c) is the number of ways to reach one number beginning with a zeros, b ones, and c twos.

Then f(a, b, c) = f_1 + f_2 + f_3 + f_4 where f_1 = f(a-1, b, c) if a>=2 or a, b >=1 or a,c >=1, f_2 = f(a, b-2, c+1) if b >= 2, f_3 = f(a, b+1, c-2) if c >= 2, and f_4 = f(a+1, b-1, c-1) if b, c >= 1, and each are 0 otherwise. Initial terms: f(a, b, c) = 1 for all 1 <= a+b+c <= 2, where a, b, c >= 0.

More terms from Alois P. Heinz, Aug 18 2016

cp's OEIS Frontend

User: Caleb Ji

A277686 The number of nonisomorphic graphs on n vertices whose chromatic symmetric function in the p basis has a nonzero coefficient for each possible term.

Views

Author

Keywords

Comments

Crossrefs

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A277203 Number of distinct chromatic symmetric functions realizable by a graph on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A277204 Number of chromatic symmetric functions realizable from exactly one graph on n vertices.

Views

Author

Keywords

Crossrefs

A277205 Number of chromatic symmetric functions realizable by exactly 2 graphs on n vertices.

Views

Author

Keywords

Crossrefs

A276031 Number of edges in the graded poset of the partitions of n taken modulo 3, where a partition into k parts is joined to a partition into k+1 parts if the latter is a refinement of the former.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A276033 Number of generalizations of the partition 1^n with all elements taken modulo 2.

Views

Author

Keywords

Comments

Crossrefs

A276032 Number of refinements of the partition n^1 with all numbers taken modulo 2.

Views

Author

Keywords

Comments

Crossrefs

A276029 Number of ways to transform a sequence of n ones and n twos to a single number by continually removing two numbers and replacing them with their sum modulo 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A276028 Number of ways to transform a sequence of n zeros and n ones to a single number by continually removing two numbers and replacing them with their sum modulo 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica