A325789 Number of perfect necklace compositions of n.

1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Author

Gus Wiseman, May 22 2019

Keywords

• nonn
• more

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. A circular subsequence is a sequence of consecutive terms where the last and first parts are also considered consecutive. A necklace composition of n is perfect if every positive integer from 1 to n is the sum of exactly one distinct circular subsequence.

Examples

			The a(1) = 1 , a(2) = 1, a(3) = 2, a(7) = 3, a(13) = 5, and a(31) = 11 perfect necklace compositions (A = 10, B = 11, C = 12, D = 13, E = 14):
  1  11  12   124      1264           12546D
         111  142      1327           1274C5
              1111111  1462           13278A
                       1723           13625E
                       1111111111111  15C472
                                      17324E
                                      1A8723
                                      1D6452
                                      1E4237
                                      1E5263
                                      1111111111111111111111111111111
		

Crossrefs

Cf. A002033, A008965, A103300, A108917, A126796, A325676, A325679, A325685, A325780, A325782, A325786, A325787, A325789.

Programs

Mathematica

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
subalt[q_]:=Union[ReplaceList[q,{_,s__,_}:>{s}],DeleteCases[ReplaceList[q,{t___,,u___}:>{u,t}],{}]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&Sort[Total/@subalt[#]]==Range[n]&]],{n,10}]

Formula

For n > 1, a(n) = A325787(n) + 1.