|
%I #13 Nov 22 2018 18:17:24
%S 1,1,2,6,20,103,759
%N Number of distinct chromatic symmetric functions of simple connected graphs with n vertices.
%C 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).
%H Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/100.pdf">A symmetric function generalization of the chromatic polynomial of a graph</a>, Advances in Math. 111 (1995), 166-194.
%H Richard P. Stanley, <a href="http://www-math.mit.edu/~rstan/papers/taor.pdf">Graph colorings and related symmetric functions: ideas and applications</a>, Discrete Mathematics 193 (1998), 267-286.
%H Gus Wiseman, <a href="http://arxiv.org/abs/math.CO/0505155">A partition of connected graphs</a>, Electronic J. Combinatorics 12, N1 (2005), 8pp. arXiv:math/0505155 [math.CO].
%e The a(4) = 6 connected chromatic symmetric functions (m is the augmented monomial symmetric function basis):
%e m(1111)
%e m(211) + m(1111)
%e 2m(211) + m(1111)
%e m(22) + 2m(211) + m(1111)
%e m(22) + 3m(211) + m(1111)
%e m(31) + 3m(211) + m(1111)
%t spsu[_,{}]:={{}};spsu[foo_,set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@spsu[Select[foo,Complement[#,Complement[set,s]]=={}&],Complement[set,s]]]/@Cases[foo,{i,___}];
%t chromSF[g_]:=Sum[m[Sort[Length/@stn,Greater]],{stn,spsu[Select[Subsets[Union@@g],Select[DeleteCases[g,{_}],Function[ed,Complement[ed,#]=={}]]=={}&],Union@@g]}];
%t 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]}]];
%t 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]]]]]]]]];
%t Table[Length[Union[chromSF/@Select[simpleSpans[n],Length[csm[#]]==1&]]],{n,6}]
%Y First differs from A079457 at a(7) = 759, A079457(7) = 706.
%Y Cf. A000110, A001349, A001187, A125702, A147878, A191970, A229048, A240936, A245883, A277203, A317631, A317632, A320921, A321750, A321751, A321895.
%K nonn,more
%O 1,3
%A _Gus Wiseman_, Nov 21 2018
|
