A321750 -id:A321750 - cp's OEIS frontend

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

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

A011968 Apply (1+Shift) to Bell numbers.

Original entry on oeis.org

1, 2, 3, 7, 20, 67, 255, 1080, 5017, 25287, 137122, 794545, 4892167, 31858034, 218543759, 1573857867, 11863100692, 93345011951, 764941675963, 6514819011216, 57556900440429, 526593974392123, 4981585554604074, 48658721593531669, 490110875149889635

Offset: 0

N. J. A. Sloane

nonn

Number of set partitions of n+2 with at least one singleton and the smallest element in any singleton is exactly n. The maximum number of singletons is therefore 3. Alternatively, number of set partitions of n+2 with at least one singleton and the largest element in any singleton is exactly 3 (or n+2 if n+2 < 3). For example, a(3)=7 counts the following set partitions of [5]: {1245, 3}, {12, 3, 45}, {124, 3, 5}, {15, 24, 3}, {125, 3, 4}, {14, 25, 3}, {12, 3, 4, 5}. - Olivier Gérard, Oct 29 2007

Let V(N)={v(1),v(2),...,v(N)} denote an ordered set of increasing positive integers containing a pair of adjacent elements that differ by at least 2, that is, v(i),v(i+1) with v(i+1)-v(i) > 1. Then for n > 0, a(n) is the number of partitions of V(n+1) into blocks of nonconsecutive integers. - Augustine O. Munagi, Jul 17 2008

			a(3)=7 because the set {1,3,4,5} has 7 different partitions into blocks of nonconsecutive integers: 14/35, 135/4, 1/35/4, 13/4/5, 14/3/5, 15/3/4, 1/3/4/5.

Olivier Gérard and Karol Penson, A budget of set partitions statistics, in preparation, unpublished as of Sep 22 2011

Chai Wah Wu, Table of n, a(n) for n = 0..500 n = 0..200 from Vincenzo Librandi.
Cohn, Martin; Even, Shimon; Menger, Karl, Jr.; Hooper, Philip K.; On the Number of Partitionings of a Set of n Distinct Objects, Amer. Math. Monthly 69 (1962), no. 8, 782--785. MR1531841.
Cohn, Martin; Even, Shimon; Menger, Karl, Jr.; Hooper, Philip K.; On the Number of Partitionings of a Set of n Distinct Objects, Amer. Math. Monthly 69 (1962), no. 8, 782--785. MR1531841. [Annotated scanned copy]
Augustine O. Munagi, Extended set partitions with successions, European J. Combin. 29(5) (2008), 1298--1308.
Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.

Cf. A000110, A000296, A011969, A011970.
A diagonal of A011971 and A106436. - N. J. A. Sloane, Jul 31 2012
Cf. A000569, A240936, A321750.

with(combinat): seq(`if`(n>0,bell(n)+bell(n-1),1),n=0..21); # Augustine O. Munagi, Jul 17 2008

# requires python 3.2 or higher. Otherwise use def'n of accumulate in python docs.
from itertools import accumulate
A011968_list, blist, b = [1,2], [1], 1
for _ in range(10**2):
    blist = list(accumulate([b]+blist))
    A011968_list.append(b+blist[-1])
    b = blist[-1] # Chai Wah Wu, Sep 02 2014, updated Chai Wah Wu, Sep 20 2014

For n >= 1, a(n+1) = exp(-1)*Sum_{k>=0} ((k+1)/k!)*k^n. - Benoit Cloitre, Mar 09 2008
For n >= 1, a(n) = Bell(n) + Bell(n-1). - Augustine O. Munagi, Jul 17 2008
G.f.: G(0) where G(k) = 1 - 2*x*(k+1)/((2*k+1)*(2*x*k-1) - x*(2*k+1)*(2*k+3)*(2*x*k-1)/(x*(2*k+3) - 2*(k+1)*(2*x*k+x-1)/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 19 2012
G.f.: 1 + x*E(0) where E(k) = 1 + 1/(1-x*k-x)/(1-x/(x+1/E(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Jan 20 2013
G.f.: 1 + Sum_{k>=0} ( 1+1/(1-x-x*k) )*x^(k+1)/Product_{i=0..k} (1-x*i). - Sergei N. Gladkovskii, Jan 20 2013
a(n) ~ Bell(n) * (1 + LambertW(n)/n). - Vaclav Kotesovec, Jul 28 2021

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

Original entry on oeis.org

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

Offset: 1

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

			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)

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

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.

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

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

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

Original entry on oeis.org

1, 1, 1, 3, 1, 2, 1, 10, 3, 2, 1, 7, 1, 2, 2, 47, 1, 6, 1, 6, 2, 2, 1, 26, 3, 2, 10, 6, 1, 6, 1, 246, 2, 2, 2, 26, 1, 2, 2, 24, 1, 5, 1, 6, 6, 2, 1, 138, 3, 6, 2, 6, 1, 23, 2, 23, 2, 2, 1, 20, 1, 2, 7, 1602, 2, 5, 1, 6, 2, 6, 1, 105, 1, 2, 6, 6, 2, 5, 1, 114

Offset: 1

Gus Wiseman, Nov 20 2018

nonn

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

Also the number of ordered set partitions of {1, 2, ..., A001222(n)} whose blocks, when i is replaced by the i-th prime index of n, have weakly decreasing sums.

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

Wikipedia, Symmetric polynomial

Row sums of A321750.

Cf. A005651, A008277, A008480, A056239, A124794, A124795, A296150, A319182, A319225, A319226, A321742-A321765.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Sum[Times@@Factorial/@Length/@Split[Sort[Total/@s]],{s,sps[Range[PrimeOmega[n]]]/.Table[i->If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]][[i]],{i,PrimeOmega[n]}]}],{n,50}]

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

A321917 Tetrangle where T(n,H(u),H(v)) is the coefficient of m(v) in p(u), where u and v are integer partitions of n, H is Heinz number, m is monomial symmetric functions, and p is power sum symmetric functions.

Original entry on oeis.org

1, 1, 0, 1, 2, 1, 0, 0, 1, 1, 0, 1, 3, 6, 1, 0, 0, 0, 0, 1, 2, 0, 0, 0, 1, 0, 1, 0, 0, 1, 2, 2, 2, 0, 1, 6, 4, 12, 24, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 2, 2, 0, 0, 0, 1, 2, 1, 0, 2, 0, 0, 1, 3, 4, 6, 6, 6, 0, 1, 5, 10, 30

Offset: 1

Gus Wiseman, Nov 22 2018

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

			Tetrangle begins (zeroes not shown):
  (1):  1
.
  (2):   1
  (11):  1  2
.
  (3):    1
  (21):   1  1
  (111):  1  3  6
.
  (4):     1
  (22):    1  2
  (31):    1     1
  (211):   1  2  2  2
  (1111):  1  6  4 12 24
.
  (5):      1
  (41):     1  1
  (32):     1     1
  (221):    1  1  2  2
  (311):    1  2  1     2
  (2111):   1  3  4  6  6  6
  (11111):  1  5 10 30 20 60 20
For example, row 14 gives: p(32) = m(5) + m(32).

Wikipedia, Symmetric polynomial

This is a regrouping of the triangle A321750.

Cf. A005651, A008480, A056239, A124794, A124795, A215366, A318284, A319191, A319193, A321912-A321935.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A011968 Apply (1+Shift) to Bell numbers.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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