%I #99 Sep 17 2022 19:25:27

%S 1,3,7,16,37,86,200,465,1081,2513,5842,13581,31572,73396,170625,

%T 396655,922111,2143648,4983377,11584946,26931732,62608681,145547525,

%U 338356945,786584466,1828587033,4250949112,9882257736,22973462017,53406819691

%N a(n+3) = 3*a(n+2) - 2*a(n+1) + a(n).

%C a(n+1) = number of n-tuples over {0,1,2} without consecutive digits. For the general case see A096261.

%C Diagonal sums of Riordan array (1/(1-x)^3, x/(1-x^3)), A127893. - _Paul Barry_, Jan 07 2008

%C The signed variant (-1)^(n+1)*a(n+1) is the bottom right entry of the n-th power of the matrix [[0,1,0],[0,0,1],[-1,-2,-3]]. - _Roger L. Bagula_, Jul 01 2007

%C a(n) is the number of generalized compositions of n+1 when there are i^2/2-i/2 different types of i, (i=1,2,...). - _Milan Janjic_, Sep 24 2010

%C Dedrickson (Section 4.1) gives a bijection between colored compositions of n, where each part k has one of binomial(k,2) colors, and 0,1,2 strings of length n-2 without sequential digits (i.e., avoiding 01 and 12). Cf. A052529. - _Peter Bala_, Sep 17 2013

%C Except for the initial 0, this is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S^2 - S^3; see A291000. - _Clark Kimberling_, Aug 24 2017

%C For n>1, a(n-1) is the number of ways to split [n] into an unspecified number of intervals and then choose 2 blocks (i.e., subintervals) from each interval. For example, for n=6, a(5)=37 since the number of ways to split [6] into intervals and then select 2 blocks from each interval is C(6,2) + C(4,2)*C(2,2) + C(3,2)*C(3,2) + C(2,2)*C(4,2) + C(2,2)*C(2,2)*C(2,2). - _Enrique Navarrete_, May 20 2022

%H Vincenzo Librandi, <a href="/A095263/b095263.txt">Table of n, a(n) for n = 1..1000</a>

%H C. R. Dedrickson III, <a href="https://digitalcommons.georgiasouthern.edu/etd/17">Compositions, Bijections, and Enumerations</a> Thesis, Jack N. Averitt College of Graduate Studies, Georgia Southern University, 2012.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,1).

%F Let M = the 3 X 3 matrix [0 1 0 / 0 0 1 / 1 -2 3]; then M^n *[1 0 0] = [a(n-2) a(n-1) a(n)].

%F a(n)/a(n-1) tends to 2.3247179572..., an eigenvalue of M and a root of the characteristic polynomial. [Is that constant equal to 1 + A060006? - _Michel Marcus_, Oct 11 2014] [Yes, the limit is the root of the equation -1 + 2*x - 3*x^2 + x^3 = 0, after substitution x = y + 1 we have the equation for y: -1 - y + y^3 = 0, y = A060006. - _Vaclav Kotesovec_, Jan 27 2015]

%F Related to the Padovan sequence A000931 as follows : a(n)=A000931(3n+4). Also the binomial transform of A000931(n+4).

%F From _Paul Barry_, Jul 06 2004: (Start)

%F a(n) = Sum_{k=0..floor((n+1)/2)} binomial(n+k, n-2*k+1).

%F a(n) = Sum_{k=0..floor((n+1)/2)} binomial(n+k, 3*k-1). (End)

%F From _Paul Barry_, Jan 07 2008: (Start)

%F G.f.: x/(1 -3*x +2*x^2 -x^3).

%F a(n) = Sum_{k=0..floor(n/2)} binomial(n+k+2,3*k+2).

%F a(n) = Sum_{k=0..n} binomial(n,k) * Sum_{j=0..floor((k+4)/2)} binomial(j,k-2j+4). (End)

%F If p[i]=i(i-1)/2 and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=2, a(n-1)=det A. - _Milan Janjic_, May 02 2010

%F a(n) = A000931(3*n + 4). - _Michael Somos_, Sep 18 2012

%e a(9) = 1081 = 3*465 - 2*200 + 86.

%e M^9 * [1 0 0] = [a(7) a(8) a(9)] = [200 465 1081].

%e G.f. = x + 3*x^2 + 7*x^3 + 16*x^4 + 37*x^5 + 86*x^6 + 200*x^7 + ...

%p A:= gfun:-rectoproc({a(n+3)=3*a(n+2)-2*a(n+1)+a(n),a(1)=1,a(2)=3,a(3)=7},a(n),remember):

%p seq(A(n),n=1..100); # _Robert Israel_, Sep 15 2014

%t a[1]=1; a[2]=3; a[3]=7; a[n_]:= a[n]= 3a[n-1] -2a[n-2] +a[n-3]; Table[a[n], {n, 22}] (* Or *)

%t a[n_]:= (MatrixPower[{{0,1,2,3}, {1,2,3,0}, {2,3,0,1}, {3,0,1,2}}, n].{{1}, {0}, {0}, {0}})[[2, 1]]; Table[ a[n], {n, 22}] (* _Robert G. Wilson v_, Jun 16 2004 *)

%t RecurrenceTable[{a[1]==1,a[2]==3,a[3]==7,a[n+3]==3a[n+2]-2a[n+1]+a[n]},a,{n,30}] (* _Harvey P. Dale_, Sep 17 2022 *)

%o (Magma) I:=[1,3,7]; [n le 3 select I[n] else 3*Self(n-1) -2*Self(n-2) +Self(n-3): n in [1..30]]; // _G. C. Greubel_, Apr 12 2021

%o (Sage) [sum( binomial(n+k+1,3*k+2) for k in (0..(n-1)//2)) for n in (1..30)] # _G. C. Greubel_, Apr 12 2021

%Y Cf. A000931, A010912, A034943, A052529, A052530, A097550, A137531.

%Y Cf. A052921 (first differences), A137229 (partial sums).

%Y Column k=3 of A277666.

%K nonn,easy

%O 1,2

%A _Gary W. Adamson_, May 31 2004

%E Edited by _Paul Barry_, Jul 06 2004

%E Corrected and extended by _Robert G. Wilson v_, Jun 05 2004