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

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.

Links

Table of n, a(n) for n=1..34.

Formula

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

Example

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)

Mathematica

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

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.

Sequence in context: A051894 A146393 A147431 * A348377 A147334 A147463

Adjacent sequences: A329142 A329143 A329144 * A329146 A329147 A329148

Keyword

nonn

Author

Gus Wiseman, Nov 10 2019

Status

approved