A091696 Number of classes of compositions of n equivalent under reflection or cycling.

1, 2, 3, 5, 7, 12, 17, 29, 45, 77, 125, 223, 379, 686, 1223, 2249, 4111, 7684, 14309, 27011, 50963, 96908, 184409, 352697, 675187, 1296857, 2493725, 4806077, 9272779, 17920859, 34669601, 67159049, 130216123, 252745367, 490984487, 954637557, 1857545299

Offset: 1

Author

Neil Fernandez, Jan 29 2004

Keywords

• nonn

Comments

Equivalently, the number of radial cutting patterns of a (maximally symmetric) circular cake such that all resulting pieces are a multiple of 1/n of the whole. - Peter Munn, Oct 27 2020

Examples

			7 has 15 partitions and 64 compositions. Compositions can be mapped to other compositions by reflection, cycling, or both, e.g., {1,2,4} -> {4,2,1} (reflection), {2,4,1} (cycling), or {1,4,2} (both); this defines the equivalence relation used. The number of equivalence classes so defined is 2 greater than the number of partitions because only {3,1,2,1} and {2,1,2,1,1} (and their equivalents) cannot be mapped to the conventionally stated forms of partitions (here, {3,2,1,1} and {2,2,1,1,1} respectively). So a(7) = 15 + 2 = 17.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A000029, A056342.

DIK transform of A057427.

Programs

Maple

with(numtheory):
a:= n-> add(phi(d)*2^(n/d)/(2*n), d=divisors(n))
        +`if`(irem(n, 2)=0, 2^(n/2-1) +2^(n/2-2), 2^((n-1)/2)) -1:
seq(a(n), n=1..40);  # Alois P. Heinz, Oct 20 2012

Mathematica

Needs["Combinatorica`"]
nn=40;Apply[Plus,Table[CoefficientList[Series[CycleIndex[DihedralGroup[n], s]/.Table[s[i]->x^i/(1-x^i),{i,1,nn}],{x,0,nn}],x],{n,1,nn}]]  (* Geoffrey Critzer, Oct 18 2012 *)
mx:=50;CoefficientList[Series[(Sum[(EulerPhi[n] Log[2+1/(-1+x^n)])/n,{n,1,mx}]+(1-1x^2+ x^3)/((x-1) (1-2 x^2)))/(-2),{x,0,mx}],x] (* Herbert Kociemba, Dec 04 2016 *)
a[n_] := (1/4)*(Mod[n, 2] + 3)*2^Quotient[n, 2] + DivisorSum[n, EulerPhi[#]*2^(n/#) & ]/(2*n) - 1; Array[a, 37] (* Jean-François Alcover, Nov 05 2017 *)

Formula

a(n) = A000029(n) - 1.

a(n) = A056342(n) + 1.

G.f.: ( Sum_{n>=1} phi(n)*log(2+1/(-1+x^n))/n + (1-1x^2+x^3)/((x-1)*(1-2*x^2)) )/(-2). - Herbert Kociemba, Dec 04 2016

Extensions

More terms from Sean A. Irvine, Feb 09 2012