1,2

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

Diagonal sums of Riordan array (1/(1-x)^3, x/(1-x^3)), A127893. - Paul Barry, Jan 07 2008

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

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

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

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

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

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Charles R. Dedrickson III, Compositions, Bijections, and Enumerations Thesis, Jack N. Averitt College of Graduate Studies, Georgia Southern University, 2012.

Andrew Li and Hua Wang, Combinatorics of positional colored compositions, arXiv:2511.08529 [math.CO], 2025. See pp. 3, 6-7.

Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

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)].

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]

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

From Paul Barry, Jul 06 2004: (Start)

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

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

From Paul Barry, Jan 07 2008: (Start)

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

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

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

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

a(n) = A000931(3*n + 4). - Michael Somos, Sep 18 2012

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

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

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

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):

seq(A(n), n=1..100); # Robert Israel, Sep 15 2014

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 *)

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 *)

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 *)

(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

(SageMath) [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

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

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

Column k=3 of A277666.

Sequence in context: A124671 A188626 A123392 * A010912 A192665 A052967

Adjacent sequences: A095260 A095261 A095262 * A095264 A095265 A095266

nonn,easy

Gary W. Adamson, May 31 2004

Edited by Paul Barry, Jul 06 2004

Corrected and extended by Robert G. Wilson v, Jun 05 2004

approved