A319226 Irregular triangle where T(n,k) is the number of acyclic spanning subgraphs of a cycle graph, where the sizes of the connected components are given by the integer partition with Heinz number A215366(n,k).

1, 2, 1, 3, 3, 1, 4, 2, 4, 4, 1, 5, 5, 5, 5, 5, 5, 1, 6, 6, 6, 3, 2, 6, 12, 9, 6, 6, 1, 7, 7, 7, 7, 14, 7, 7, 7, 7, 7, 21, 14, 7, 7, 1, 8, 8, 8, 4, 8, 8, 8, 16, 16, 8, 2, 24, 8, 24, 12, 16, 8, 32, 20, 8, 8, 1, 9, 9, 9, 9, 9, 9, 18, 9, 9, 9, 18, 18, 3, 27, 27

Offset

1,2

Comments

A refinement of A135278, up the sign these are the coefficients appearing in the expansion of power-sum symmetric functions in terms of elementary or homogeneous symmetric functions.

Links

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

Wikipedia, Expressing power sums in terms of elementary symmetric polynomials

Gus Wiseman, Enumeration of paths and cycles and e-coefficients of incomparability graphs, arXiv:0709.0430 [math.CO], 2007.

Example

Triangle begins:
  1
  2  1
  3  3  1
  4  2  4  4  1
  5  5  5  5  5  5  1
  6  6  6  3  2  6 12  9  6  6  1
The fourth row corresponds to the symmetric function identities:
  p(4) = -4 e(4) + 2 e(22) + 4 e(31) - 4 e(211) + e(1111)
  p(4) =  4 h(4) - 2 h(22) - 4 h(31) + 4 h(211) - h(1111).

Mathematica

primeMS[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
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[Select[Subsets[Partition[Range[n], 2, 1, 1], {n-PrimeOmega[m]}], Sort[Length/@csm[Union[#, List/@Range[n]]]]==primeMS[m]&]], {n, 6}, {m, Sort[Times@@Prime/@#&/@IntegerPartitions[n]]}]

Crossrefs

Signed versions with different row-orderings are A115131, A210258, A263916.

Cf. A005651, A008480, A048994, A056239, A124794, A124795, A135278, A215366, A318762, A319191, A319193, A319225.

Sequence in context: A277227 A054531 A324602 * A307449 A368748 A207645

Adjacent sequences: A319223 A319224 A319225 * A319227 A319228 A319229

Keyword

nonn,tabf

Author

Gus Wiseman, Sep 13 2018

Status

approved