OFFSET
0,4
COMMENTS
Number of strict necklace compositions of n. A strict necklace composition of n is a finite sequence of distinct positive integers summing to n that is lexicographically minimal among all of its cyclic rotations. In other words, it is a strict composition of n starting with its least part. - Gus Wiseman, May 31 2019
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..5000 (first 2001 terms from Robert Israel)
C. G. Bower, Transforms (2)
FORMULA
"CGK" (necklace, element, unlabeled) transform of 1, 1, 1, 1, ...
G.f.: Sum_{k >= 1} (k-1)! * x^((k^2+k)/2) / (Product_{j=1..k} 1-x^j). - Vladeta Jovovic, Sep 21 2004
a(n) = Sum_{k=1..floor((sqrt(8*n+1)-1)/2)} (k-1)! * A008289(n,k) for n > 0. - Alois P. Heinz, Aug 07 2020
EXAMPLE
From Gus Wiseman, May 31 2019: (Start)
Inequivalent representatives of the a(1) = 1 through a(9) = 11 ways to slice a pie:
(1) (2) (3) (4) (5) (6) (7) (8) (9)
(12) (13) (14) (15) (16) (17) (18)
(23) (24) (25) (26) (27)
(123) (34) (35) (36)
(132) (124) (125) (45)
(142) (134) (126)
(143) (135)
(152) (153)
(162)
(234)
(243)
(End)
MAPLE
N:= 100: # to get a(0)..a(N)
K:= floor(isqrt(1+8*N)/2):
S:= series(1+add((k-1)!*x^((k^2+k)/2)/mul(1-x^j, j=1..k), k=1..K), x, N+1):
seq(coeff(S, x, j), j=0..N); # Robert Israel, Jul 15 2016
# second Maple program:
b:= proc(n, i, p) option remember; `if`(i*(i+1)/2<n, 0,
`if`(n=0, p!, b(n, i-1, p)+b(n-i, min(n-i, i-1), p+1)))
end:
a:= n-> `if`(n=0, 1, b(n$2, -1)):
seq(a(n), n=1..50); # Alois P. Heinz, Aug 12 2020
MATHEMATICA
max=50; s=Sum[(x^(k(k+1)/2-1)*(k-1)!)/QPochhammer[x, x, k], {k, 1, max}] + O[x]^max; CoefficientList[s, x] (* Jean-François Alcover, Jan 19 2016 *)
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@Select[IntegerPartitions[n], UnsameQ@@#&], neckQ]], {n, 30}] (* Gus Wiseman, May 31 2019 *)
PROG
(PARI)
N=66; q='q+O('q^N);
gf=sum(n=1, N, (n-1)!*q^(n*(n+1)/2) / prod(k=1, n, 1-q^k ) );
Vec(gf)
/* Joerg Arndt, Oct 20 2012 */
(PARI) seq(n)=[subst(serlaplace(p/y), y, 1) | p <- Vec(y-1+prod(k=1, n, 1 + x^k*y + O(x*x^n)))] \\ Andrew Howroyd, Sep 13 2018
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
a(0)=1 prepended by Andrew Howroyd, Sep 13 2018
STATUS
approved