login
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).
14

%I #13 Aug 23 2023 08:43:32

%S 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,

%T 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,

%U 20,8,8,1,9,9,9,9,9,9,18,9,9,9,18,18,3,27,27

%N 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).

%C 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.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Newton%27s_identities#Expressing_power_sums_in_terms_of_elementary_symmetric_polynomials">Expressing power sums in terms of elementary symmetric polynomials</a>

%H Gus Wiseman, <a href="http://arxiv.org/abs/0709.0430">Enumeration of paths and cycles and e-coefficients of incomparability graphs</a>, arXiv:0709.0430 [math.CO], 2007.

%e Triangle begins:

%e 1

%e 2 1

%e 3 3 1

%e 4 2 4 4 1

%e 5 5 5 5 5 5 1

%e 6 6 6 3 2 6 12 9 6 6 1

%e The fourth row corresponds to the symmetric function identities:

%e p(4) = -4 e(4) + 2 e(22) + 4 e(31) - 4 e(211) + e(1111)

%e p(4) = 4 h(4) - 2 h(22) - 4 h(31) + 4 h(211) - h(1111).

%t primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

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

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

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

%K nonn,tabf

%O 1,2

%A _Gus Wiseman_, Sep 13 2018