A325591 - OEIS

A325591

Number of compositions of n with circular differences all equal to 1, 0, or -1.

%I #12 Sep 21 2019 02:52:00

%S 1,2,4,6,11,15,27,43,68,116,189,311,519,860,1433,2380,3968,6613,11018,

%T 18374,30633,51089,85208,142113,237055,395409,659576,1100262,1835382,

%U 3061711,5107445,8520122,14213135,23710173,39553138,65982316,110071459,183620990,306316328

%N Number of compositions of n with circular differences all equal to 1, 0, or -1.

%C A composition of n is a finite sequence of positive integers summing to n.

%C 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).

%H Andrew Howroyd, <a href="/A325591/b325591.txt">Table of n, a(n) for n = 1..200</a>

%F a(n) ~ c * d^n, where d = 1.66820206701846111636107... (see A034297), c = 0.65837031047271348106444... - _Vaclav Kotesovec_, Sep 21 2019

%e The a(1) = 1 through a(6) = 15 compositions:

%e (1) (2) (3) (4) (5) (6)

%e (11) (12) (22) (23) (33)

%e (21) (112) (32) (222)

%e (111) (121) (122) (1122)

%e (211) (212) (1212)

%e (1111) (221) (1221)

%e (1112) (2112)

%e (1121) (2121)

%e (1211) (2211)

%e (2111) (11112)

%e (11111) (11121)

%e (11211)

%e (12111)

%e (21111)

%e (111111)

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],SameQ[1,##]&@@Abs[DeleteCases[Differences[Append[#,First[#]]],0]]&]],{n,15}]

%o (PARI)

%o 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]))) )}

%o 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

%Y Row sums of A309931.

%Y Cf. A000079, A008965, A034297, A173258, A325351, A325551, A325553, A325558, A325589, A325590.

%K nonn

%O 1,2

%A _Gus Wiseman_, May 12 2019

%E Terms a(21) and beyond from _Andrew Howroyd_, Aug 23 2019