login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A325590 Number of necklace compositions of n with circular differences all equal to 1 or -1. 6
0, 0, 1, 0, 1, 1, 1, 1, 2, 1, 2, 2, 2, 2, 4, 3, 3, 4, 4, 5, 7, 6, 7, 10, 10, 11, 15, 16, 18, 23, 25, 32, 38, 43, 53, 64, 73, 89, 108, 131, 153, 188, 223, 272, 329, 395, 475, 583, 697, 848, 1027, 1247, 1506, 1837, 2223, 2708, 3282, 3993, 4848, 5913, 7175, 8745, 10640 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,9

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.

The circular differences of a sequence c of length k are c_{i + 1} - c_i for i < k and c_1 - c_i for i = k. For example, the circular differences of (1,2,1,3) are (1,-1,2,-2).

Up to rotation, a(n) is the number of ways to arrange positive integers summing to n in a circle such that adjacent parts differ by 1 or -1.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..200

EXAMPLE

The first 16 terms count the following compositions:

   3: (12)

   5: (23)

   6: (1212)

   7: (34)

   8: (1232)

   9: (45)

   9: (121212)

  10: (2323)

  11: (56)

  11: (121232)

  12: (2343)

  12: (12121212)

  13: (67)

  13: (123232)

  14: (3434)

  14: (12121232)

  15: (78)

  15: (123432)

  15: (232323)

  15: (1212121212)

  16: (3454)

  16: (12321232)

  16: (12123232)

The a(21) = 7 necklace compositions:

  (10,11)

  (2,3,4,5,4,3)

  (3,4,3,4,3,4)

  (1,2,1,2,1,2,3,4,3,2)

  (1,2,3,2,1,2,3,2,3,2)

  (1,2,1,2,3,2,3,2,3,2)

  (1,2,1,2,1,2,1,2,1,2,1,2,1,2)

MATHEMATICA

neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], neckQ[#]&&(SameQ[1, ##]&@@Abs[Differences[Append[#, First[#]]]])&]], {n, 15}]

PROG

(PARI)

step(R, n, s)={matrix(n, n, i, j, if(i>j, if(j>s, R[i-j, j-s]) + if(j+s<=n, R[i-j, j+s])) )}

a(n)={sum(k=1, n, my(R=matrix(n, n, i, j, i==j&&abs(i-k)==1), t=0, m=1); while(R, R=step(R, n, 1); m++; t+=sumdiv(n, d, R[d, k]*d*eulerphi(n/d))/m ); t/n)} \\ Andrew Howroyd, Aug 23 2019

CROSSREFS

Cf. A000079, A000740, A008965, A034297, A173258, A325556, A325588, A325589, A325591.

Sequence in context: A140426 A146879 A231577 * A277210 A304777 A058762

Adjacent sequences:  A325587 A325588 A325589 * A325591 A325592 A325593

KEYWORD

nonn

AUTHOR

Gus Wiseman, May 12 2019

EXTENSIONS

a(26)-a(40) from Lars Blomberg, Jun 11 2019

Terms a(41) and beyond from Andrew Howroyd, Aug 23 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 27 21:52 EDT 2020. Contains 334671 sequences. (Running on oeis4.)