login
A318729
Number of cyclic compositions (necklaces of positive integers) summing to n that have only one part or whose consecutive parts (including the last with first) are indivisible.
13
1, 1, 1, 1, 2, 1, 3, 2, 4, 6, 6, 8, 11, 19, 21, 30, 41, 59, 79, 112, 157, 219, 305, 430, 605, 860, 1210, 1727, 2424, 3463, 4905, 7001, 9954, 14211, 20271, 28980, 41392, 59254, 84800, 121540, 174163, 249932, 358578, 515091, 739933, 1063827, 1529767, 2201383
OFFSET
1,5
LINKS
FORMULA
a(n) = A328600(n) + 1. - Andrew Howroyd, Oct 27 2019
EXAMPLE
The a(13) = 11 cyclic compositions with successive parts indivisible:
(13)
(2,11) (3,10) (4,9) (5,8) (6,7)
(2,4,7) (2,6,5) (2,8,3) (3,6,4)
(2,3,5,3)
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Or[Length[#]==1, neckQ[#]&&And@@Not/@Divisible@@@Partition[#, 2, 1, 1]]&]], {n, 20}]
PROG
(PARI)
b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q, ]}
seq(n)={my(v=sum(k=1, n, k*b(n, k, (i, j)->i%j<>0))); vector(n, n, 1 + sumdiv(n, d, eulerphi(d)*v[n/d])/n)} \\ Andrew Howroyd, Oct 27 2019
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 02 2018
EXTENSIONS
Terms a(21) and beyond from Andrew Howroyd, Sep 08 2018
Name corrected by Gus Wiseman, Nov 04 2019
STATUS
approved