[Equivalence classes (under reflection, cycling) of compositions of n]

[Christian G. Bower]

Neil Fernandez <primeness at borve.demon.co.uk> wrote:

> I've been looking at equivalence classes of compositions of n where the
> equivalence relation is different from the 'order insignificant' one
> that defines partitions.
> 
> Equivalence under reflection, cycling, or a combination of both, gives
> the following nos. of equivalence classes for n = 1, 2, 3, ... :
> 
> 1, 2, 3, 5, 7, 12, 17, 29, 45, ...
> 
a(n) = A000029(n) - 1

ID Number: A000029 (Formerly M0563 and N0202)
URL:       http://www.research.att.com/projects/OEIS?Anum=A000029
Sequence:  1,2,3,4,6,8,13,18,30,46,78,126,224,380,687,1224,2250,4112,
           7685,14310,27012,50964,96909,184410,352698,675188,1296858,
           2493726,4806078,9272780,17920860,34669602,67159050,
           130216124,252745368,490984488
Name:      Necklaces with n beads of 2 colors, allowing turning over.
...
Formula:   Sum_{ d divides n } phi(d)*2^(n/d)/(2*n) + either 2^((n-1)/2)
           if n odd or 2^(n/2-1)+2^(n/2-2) if n even.

Also: reflection without cycling: A005418
cycling without reflection: A008965

Christian