A329145 Number of non-necklace compositions of n.

0, 0, 1, 3, 9, 19, 45, 93, 197, 405, 837, 1697, 3465, 7011, 14193, 28653, 57825, 116471, 234549, 471801, 948697, 1906407, 3829581, 7689357, 15435033, 30973005, 62137797, 124630149, 249922665, 501078345, 1004468157, 2013263853, 4034666121, 8084640465

Offset: 1

Author

Gus Wiseman, Nov 10 2019

Keywords

• nonn

Comments

A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.

Examples

			The a(3) = 1 through a(6) = 19 compositions:
  (21)  (31)   (32)    (42)
        (121)  (41)    (51)
        (211)  (131)   (141)
               (212)   (213)
               (221)   (231)
               (311)   (312)
               (1121)  (321)
               (1211)  (411)
               (2111)  (1131)
                       (1221)
                       (1311)
                       (2112)
                       (2121)
                       (2211)
                       (3111)
                       (11121)
                       (11211)
                       (12111)
                       (21111)
		

Crossrefs

Numbers whose prime signature is not a necklace are A329142.

Binary necklaces are A000031.

Necklace compositions are A008965.

Lyndon compositions are A059966.

Numbers whose reversed binary expansion is a necklace are A328595.

Cf. A000740, A001037, A019536, A070211, A178472, A318731, A329138, A329141.

Programs

Mathematica

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!neckQ[#]&]],{n,10}]

Formula

a(n) = 2^(n-1) - A008965(n).