A091696 - OEIS

%I #45 Nov 07 2020 11:36:27

%S 1,2,3,5,7,12,17,29,45,77,125,223,379,686,1223,2249,4111,7684,14309,

%T 27011,50963,96908,184409,352697,675187,1296857,2493725,4806077,

%U 9272779,17920859,34669601,67159049,130216123,252745367,490984487,954637557,1857545299

%N Number of classes of compositions of n equivalent under reflection or cycling.

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

%H Alois P. Heinz, <a href="/A091696/b091696.txt">Table of n, a(n) for n = 1..1000</a>

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

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

%F 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

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

%p with(numtheory):

%p a:= n-> add(phi(d)*2^(n/d)/(2*n), d=divisors(n))

%p         +`if`(irem(n, 2)=0, 2^(n/2-1) +2^(n/2-2), 2^((n-1)/2)) -1:

%p seq(a(n), n=1..40);  # _Alois P. Heinz_, Oct 20 2012

%t Needs["Combinatorica`"]

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

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

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

%Y Cf. A000029, A056342.

%K nonn

%O 1,2

%A _Neil Fernandez_, Jan 29 2004

%E More terms from _Sean A. Irvine_, Feb 09 2012