A321751 -id:A321751

Search: a321751 -id:a321751

Displaying 1-4 of 4 results found.

page 1

A277203

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

+10
17

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

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

LINKS

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

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.

EXAMPLE

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)

MATHEMATICA

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 *)

CROSSREFS

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

KEYWORD

nonn,more

AUTHOR

Sam Heil and Caleb Ji, Oct 04 2016

STATUS

approved

A321911

Number of distinct chromatic symmetric functions of simple connected graphs with n vertices.

+10
11

1, 1, 2, 6, 20, 103, 759

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

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 p 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).

LINKS

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

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, A partition of connected graphs, Electronic J. Combinatorics 12, N1 (2005), 8pp. arXiv:math/0505155 [math.CO].

EXAMPLE

The a(4) = 6 connected 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)

m(22) + 3m(211) + m(1111)

m(31) + 3m(211) + m(1111)

MATHEMATICA

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]}]];

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[Length[Union[chromSF/@Select[simpleSpans[n], Length[csm[#]]==1&]]], {n, 6}]

CROSSREFS

First differs from A079457 at a(7) = 759, A079457(7) = 706.

Cf. A000110, A001349, A001187, A125702, A147878, A191970, A229048, A240936, A245883, A277203, A317631, A317632, A320921, A321750, A321751, A321895.

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Nov 21 2018

STATUS

approved

A321750

Irregular triangle read by rows where T(H(u),H(v)) is the coefficient of m(v) in p(u), where H is Heinz number, m is monomial symmetric functions, and p is power sum symmetric functions.

+10
9

1, 1, 1, 0, 1, 2, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 3, 6, 1, 2, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 2, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 6, 4, 12, 24, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

Row n has length A000041(A056239(n)).

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

LINKS

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

Wikipedia, Symmetric polynomial

EXAMPLE

Triangle begins:

1 0

1 2

1 0 0

1 1 0

1 0 0 0 0

1 3 6

1 2 0 0 0

1 0 1 0 0

1 0 0 0 0 0 0

1 2 2 2 0

1 0 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0

1 0 1 0 0 0 0

1 6 4 12 24

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 2 2 0 0 0

For example, row 18 gives: p(221) = m(5) + 2m(32) + m(41) + 2m(221).

CROSSREFS

Row sums are A321751.

Cf. A005651, A008277, A008480, A048994, A056239, A124794, A124795, A319182, A319191, A321742-A321765.

KEYWORD

nonn,tabf

AUTHOR

Gus Wiseman, Nov 20 2018

STATUS

approved

A321889

Sum of coefficients of forgotten symmetric functions in the power sum symmetric function of the integer partition with Heinz number n.

+10
1

1, 1, -1, 3, 1, -2, -1, 10, 3, 2, 1, -7, -1, -2, -2, 47, 1, 6

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

LINKS

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

Wikipedia, Symmetric polynomial

EXAMPLE

The sum of coefficients of p(211) = -f(4) - 2f(22) - 2f(31) - 2f(211) is a(12) = -7.

CROSSREFS

Row sums of A321888. An unsigned version is A321751.

Cf. A005651, A008277, A008480, A048994, A056239, A124794, A124795, A319182, A319191, A319193, A321742-A321765.

KEYWORD

sign,more

AUTHOR

Gus Wiseman, Nov 20 2018

STATUS

approved

page 1

Search completed in 0.004 seconds