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,2

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

Links

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

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

Example

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.

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

Crossrefs

Cf. A000029, A056342.

Sequence in context: A206788 A002965 A206290 * A334683 A280303 A048808

Adjacent sequences: A091693 A091694 A091695 * A091697 A091698 A091699

Keyword

nonn

Author

Neil Fernandez, Jan 29 2004

Extensions

More terms from Sean A. Irvine, Feb 09 2012

Status

approved