login
A325591
Number of compositions of n with circular differences all equal to 1, 0, or -1.
5
1, 2, 4, 6, 11, 15, 27, 43, 68, 116, 189, 311, 519, 860, 1433, 2380, 3968, 6613, 11018, 18374, 30633, 51089, 85208, 142113, 237055, 395409, 659576, 1100262, 1835382, 3061711, 5107445, 8520122, 14213135, 23710173, 39553138, 65982316, 110071459, 183620990, 306316328
OFFSET
1,2
COMMENTS
A composition of n is a finite sequence of positive integers summing to n.
The circular differences of a composition 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).
LINKS
FORMULA
a(n) ~ c * d^n, where d = 1.66820206701846111636107... (see A034297), c = 0.65837031047271348106444... - Vaclav Kotesovec, Sep 21 2019
EXAMPLE
The a(1) = 1 through a(6) = 15 compositions:
(1) (2) (3) (4) (5) (6)
(11) (12) (22) (23) (33)
(21) (112) (32) (222)
(111) (121) (122) (1122)
(211) (212) (1212)
(1111) (221) (1221)
(1112) (2112)
(1121) (2121)
(1211) (2211)
(2111) (11112)
(11111) (11121)
(11211)
(12111)
(21111)
(111111)
MATHEMATICA
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], SameQ[1, ##]&@@Abs[DeleteCases[Differences[Append[#, First[#]]], 0]]&]], {n, 15}]
PROG
(PARI)
step(R, n, D)={matrix(n, n, i, j, if(i>j, sum(k=1, #D, my(s=D[k]); if(j>s && 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); while(R, t+=R[n, k]; R=step(R, n, [0, 1, -1])); t)} \\ Andrew Howroyd, Aug 23 2019
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 12 2019
EXTENSIONS
Terms a(21) and beyond from Andrew Howroyd, Aug 23 2019
STATUS
approved