A240936 -id:A240936 - cp's OEIS frontend

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

2, 0, 12, 2, 0, 0, 0, 54, 26, 16, 0, 2, 0, 0, 0, 0, 0, 0, 216, 120, 168, 84, 0, 24, 40, 32, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 810, 648, 822, 56, 240, 870, 280, 282, 120, 24, 0, 266, 232, 0, 48, 0, 54, 0, 48, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 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).
The n-ladder has 2*n vertices and looks like:
  o-o-o-   -o
  | | | ... |
  o-o-o-   -o
Conjecture: All terms are nonnegative (verified up to the 5-ladder).

			Triangle begins:
    2   0
   12   2   0   0   0
   54  26  16   0   2   0   0   0   0   0   0
  216 120 168  84   0  24  40  32   0   0   2   0   0   [+9 more zeros]
For example, row 3 gives: X_L3 = 54e(6) + 26e(42) + 16e(51) + 2e(222).

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

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

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.

A321994 Number of different chromatic symmetric functions of hypertrees on n vertices.

Original entry on oeis.org

1, 1, 2, 4, 9, 22, 59, 165

Offset: 1

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

Stanley conjectured that the number of distinct chromatic symmetric functions of trees with n vertices is equal to A000055, i.e., the chromatic symmetric function distinguishes between trees. It has been proven for trees with up to 25 vertices. If it is true in general, does the chromatic symmetric function also distinguish between hypertrees, meaning this sequence would be equal to A035053?

Jeremy L. Martin, The uniqueness problem for chromatic symmetric functions of trees (2015)
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. A000055, A000569, A001187, A001349, A006125, A035053, A229048, A240936, A245883, A277203, A030019, A321750, 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,_}];
stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
density[c_]:=Total[(Length[#]-1&)/@c]-Length[Union@@c];
hyall[n_]:=Select[stableSets[Select[Subsets[Range[n]],Length[#]>1&],Or[SubsetQ[#1,#2],Length[Intersection[#1,#2]]>1]&],And[Union@@#==Range[n],Length[csm[#]]==1,density[#]==-1]&];
chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
Table[Length[Union[chromSF/@If[n==1,{{{1}}},hyall[n]]]],{n,5}]

A322011 Number of distinct chromatic symmetric functions of spanning hypergraphs (or antichain covers) on n vertices.

Original entry on oeis.org

1, 2, 5, 19, 121

Offset: 1

Gus Wiseman, Nov 24 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 the augmented monomial symmetric function basis (see A321895).

			The a(3) = 5 chromatic symmetric functions:
                  m(111)
          m(21) + m(111)
         2m(21) + m(111)
         3m(21) + m(111)
  m(3) + 3m(21) + m(111)

Cf. A000569, A006125, A229048, A240936, A245883, A277203, A030019, A321750, A321895, A321911, A321994.

chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
hyps[n_]:=Select[stableSets[Rest[Subsets[Range[n]]],SubsetQ],Union@@#==Range[n]&];
Table[Length[Union[chromSF/@hyps[n]]],{n,5}]

A322063 Number of ways to choose a stable partition of an antichain of sets spanning n vertices.

Original entry on oeis.org

1, 1, 3, 25, 773, 160105

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 a(3) = 25 stable partitions of antichains on 3 vertices. The antichain is on top, and below is a list of all its stable partitions.
  {1}{2}{3}      {1,2,3}        {1}{2,3}       {1,3}{2}       {1,2}{3}
  --------       --------       --------       --------       --------
  {{1,2,3}}      {{1},{2,3}}    {{1,2},{3}}    {{1},{2,3}}    {{1},{2,3}}
  {{1},{2,3}}    {{1,2},{3}}    {{1,3},{2}}    {{1,2},{3}}    {{1,3},{2}}
  {{1,2},{3}}    {{1,3},{2}}    {{1},{2},{3}}  {{1},{2},{3}}  {{1},{2},{3}}
  {{1,3},{2}}    {{1},{2},{3}}
  {{1},{2},{3}}
.
  {1,3}{2,3}     {1,2}{2,3}     {1,2}{1,3}     {1,2}{1,3}{2,3}
  --------       --------       --------       --------
  {{1,2},{3}}    {{1,3},{2}}    {{1},{2,3}}    {{1},{2},{3}}
  {{1},{2},{3}}  {{1},{2},{3}}  {{1},{2},{3}}

Cf. A000110, A000569, A006125, A006126, A229048, A240936, A277203, A321979, A322064, A322065.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
Table[Sum[Length[stableSets[Complement[Subsets[Range[n]],Union@@Subsets/@stn],SubsetQ]],{stn,sps[Range[n]]}],{n,5}]

A322065 Number of ways to choose a stable partition of a connected antichain of sets spanning n vertices.

Original entry on oeis.org

1, 1, 1, 11, 525, 146513

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 a(3) = 11 stable partitions. The connected antichain is on top, and below is a list of all its stable partitions.
{1,2,3}        {1,3}{2,3}     {1,2}{2,3}     {1,2}{1,3}     {1,2}{1,3}{2,3}
--------       --------       --------       --------       --------
{{1},{2,3}}    {{1,2},{3}}    {{1,3},{2}}    {{1},{2,3}}    {{1},{2},{3}}
{{1,2},{3}}    {{1},{2},{3}}  {{1},{2},{3}}  {{1},{2},{3}}
{{1,3},{2}}
{{1},{2},{3}}

Cf. A000110, A001187, A006125, A048143, A229048, A240936, A245883, A277203, A321911, A321979, A322063, A322064.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Sum[Length[Select[stableSets[Complement[Subsets[Range[n]],Union@@Subsets/@stn],SubsetQ],And[Union@@#==Range[n],Length[csm[#]]==1]&]],{stn,sps[Range[n]]}],{n,5}]

A355073 G.f.: Sum_{n>=0} a(n)x^n/(n!3^(n(n-1)/2)) = exp( Sum_{n>=1} x^n/(n!3^(n*(n-1)/2)) ).

Original entry on oeis.org

1, 1, 4, 55, 2539, 383860, 187659181, 293630900689, 1459799672901004, 22924423319469919651, 1131844225175191511724871, 175015470856131731421651730600, 84480805958219938739735661779357401, 126948830401157131161305967764668449231937

Offset: 0

Seiichi Manyama, Jun 18 2022

nonn

Cf. A000110, A240936, A355074.

Cf. A355070, A355081.

a(n) = n!*3^(n*(n-1)/2)*polcoef(exp(sum(k=1, n, x^k/(k!*3^(k*(k-1)/2)))+x*O(x^n)), n);

T(n, k) = if(k==1, 1, sum(j=1, n-1, 3^(j*(n-j))*binomial(n-1, j)*T(j, k-1)));
a(n) = if(n==0, 1, sum(k=1, n, T(n, k)));

A355074 G.f.: Sum_{n>=0} a(n)x^n/(n!4^(n(n-1)/2)) = exp( Sum_{n>=1} x^n/(n!4^(n*(n-1)/2)) ).

Original entry on oeis.org

1, 1, 5, 113, 11265, 4859137, 8966576129, 70171067707393, 2313986342570295297, 319893682564775147012097, 184627527352223449064321581057, 443344010564094761887045848673550337, 4416539344305075410912848824562640662560769

Offset: 0

Seiichi Manyama, Jun 18 2022

nonn

Cf. A000110, A240936, A355073.

Cf. A355071, A355082.

a(n) = n!*4^(n*(n-1)/2)*polcoef(exp(sum(k=1, n, x^k/(k!*4^(k*(k-1)/2)))+x*O(x^n)), n);

T(n, k) = if(k==1, 1, sum(j=1, n-1, 4^(j*(n-j))*binomial(n-1, j)*T(j, k-1)));
a(n) = if(n==0, 1, sum(k=1, n, T(n, k)));

A322012 Number of s-positive simple labeled graphs with n vertices.

Original entry on oeis.org

1, 2, 8, 60, 1009

Offset: 1

Gus Wiseman, Nov 24 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 the augmented monomial symmetric function basis (see A321895). A graph is s-positive if, in the expansion of its chromatic symmetric function in terms of Schur functions, all coefficients are nonnegative.

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.

a(n) >= A321979(n).

Cf. A000569, A006125, A229048, A240936, A277203, A321895, A321924, A321925, A321931, A321994.

cp's OEIS Frontend

A321982 Row n gives the chromatic symmetric function of the n-ladder, 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

A321994 Number of different chromatic symmetric functions of hypertrees on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A322011 Number of distinct chromatic symmetric functions of spanning hypergraphs (or antichain covers) on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A322063 Number of ways to choose a stable partition of an antichain of sets spanning n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A322065 Number of ways to choose a stable partition of a connected antichain of sets spanning n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A355073 G.f.: Sum_{n>=0} a(n)*x^n/(n!*3^(n*(n-1)/2)) = exp( Sum_{n>=1} x^n/(n!*3^(n*(n-1)/2)) ).

Views

Author

Keywords

Crossrefs

Programs

PARI

PARI

A355074 G.f.: Sum_{n>=0} a(n)*x^n/(n!*4^(n*(n-1)/2)) = exp( Sum_{n>=1} x^n/(n!*4^(n*(n-1)/2)) ).

Views

Author

Keywords

Crossrefs

Programs

PARI

PARI

A355073 G.f.: Sum_{n>=0} a(n)x^n/(n!3^(n(n-1)/2)) = exp( Sum_{n>=1} x^n/(n!3^(n*(n-1)/2)) ).

A355074 G.f.: Sum_{n>=0} a(n)x^n/(n!4^(n(n-1)/2)) = exp( Sum_{n>=1} x^n/(n!4^(n*(n-1)/2)) ).