A058855 Number of 6-bead necklaces where each bead is an unlabeled rooted tree, by total number of nodes.
1, 1, 4, 8, 22, 52, 142, 362, 973, 2574, 6935, 18643, 50573, 137401, 375306, 1027898, 2825831, 7790055, 21539352, 59706865, 165921896, 462127857, 1289901083, 3607567539, 10108555623, 28374358327, 79777757405, 224653284863
Offset: 0
Keywords
Examples
a(3) = 8 since the 3 nodes may be arranged around the necklace as 111000, 110100, 101010, 210000, 201000, 200100, 300000 and in the latter arrangement there are two possible trees that can be used because A000081(3)=2.
Programs
-
Mathematica
nn=20;f[x_]:=Sum[a[n]x^n,{n,0,nn}];sol=SolveAlways[0==Series[f[x]-x Product[1/(1-x^i)^a[i],{i,1,nn}],{x,0,nn}],x];t=Prepend[Table[a[n],{n,1,nn}]/.sol//Flatten,1];Drop[CoefficientList[Series[CycleIndex[DihedralGroup[6],s]/.Table[s[i]->Sum[t[[k]]x^((k-1) i),{k,1,nn-1}],{i,1,6}],{x,0,nn}],x],-2] (* Geoffrey Critzer, Feb 22 2013 *)
Formula
Plug g.f. for A000081, 1+x+x^2+2*x^3+4*x^4+ ... into cycle index for dihedral group D_12.
Cycle index for D_12 is 1/12*Z[1]^6+1/6*Z[6]+1/4*Z[1]^2*Z[2]^2+1/6*Z[3]^2+1/3*Z[2]^3.
Comments