A097550 -id:A097550 - cp's OEIS frontend

A095263 a(n+3) = 3a(n+2) - 2a(n+1) + a(n).

1, 3, 7, 16, 37, 86, 200, 465, 1081, 2513, 5842, 13581, 31572, 73396, 170625, 396655, 922111, 2143648, 4983377, 11584946, 26931732, 62608681, 145547525, 338356945, 786584466, 1828587033, 4250949112, 9882257736, 22973462017, 53406819691

Offset: 1

Gary W. Adamson, May 31 2004

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

			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 + ...

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
C. R. Dedrickson III, Compositions, Bijections, and Enumerations Thesis, Jack N. Averitt College of Graduate Studies, Georgia Southern University, 2012.
Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Cf. A000931, A010912, A034943, A052529, A052530, A097550, A137531.
Cf. A052921 (first differences), A137229 (partial sums).
Column k=3 of A277666.

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

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

[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

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

Edited by Paul Barry, Jul 06 2004

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

A034943 Binomial transform of Padovan sequence A000931.

Original entry on oeis.org

1, 1, 1, 2, 5, 12, 28, 65, 151, 351, 816, 1897, 4410, 10252, 23833, 55405, 128801, 299426, 696081, 1618192, 3761840, 8745217, 20330163, 47261895, 109870576, 255418101, 593775046, 1380359512, 3208946545

Offset: 0

N. J. A. Sloane

Trisection of the Padovan sequence: a(n) = A000931(3n). - Paul Barry, Jul 06 2004
a(n+1) gives diagonal sums of Riordan array (1/(1-x),x/(1-x)^3). - Paul Barry, Oct 11 2005
a(n+2) is the sum, over all Boolean n-strings, of the product of the lengths of the runs of 1. For example, the Boolean 7-string (0,1,1,0,1,1,1) has two runs of 1s. Their lengths, 2 and 3, contribute a product of 6 to a(9). The 8 Boolean 3-strings contribute to a(5) as follows: 000 (empty product), 001, 010, 100, 101 all contribute 1, 011 and 110 contribute 2, 111 contributes 3. - David Callan, Nov 29 2007
[a(n), a(n+1), a(n+2)], n > 0, = [0,1,0; 0,0,1; 1,-2,3]^n * [1,1,1]. - Gary W. Adamson, Mar 27 2008
Without the initial 1 and 1: 1, 2, 5, 12, 28, this is also the transform of 1 by the T_{1,0} transformation; see Choulet link. - Richard Choulet, Apr 11 2009
Without the first 1: transform of 1 by T_{0,0} transformation (see Choulet link). - Richard Choulet, Apr 11 2009
Starting (1, 2, 5, 12, ...) = INVERT transform of (1, 1, 2, 3, 4, 5, ...) and row sums of triangle A159974. - Gary W. Adamson, Apr 28 2009
a(n+1) is also the number of 321-avoiding separable permutations. (A permutation is separable if it avoids both 2413 and 3142.) - Vince Vatter, Sep 21 2009
a(n+1) is an eigensequence of the sequence array for (1,1,2,3,4,5,...). - Paul Barry, Nov 03 2010
Equals the INVERTi transform of A055588: (1, 2, 4, 9, 22, 56, ...) - Gary W. Adamson, Apr 01 2011
The Ca3 sums, see A180662, of triangle A194005 equal the terms of this sequence without a(0) and a(1). - Johannes W. Meijer, Aug 16 2011
Without the initial 1, a(n) = row sums of A182097(n)*A007318(n,k); i.e., a Triangular array T(n,k) multiplying the binomial (Pascal's) triangle by the Padovan sequence where a(0) = 1, a(1) = 0 and a(2) = 1. - Bob Selcoe, Jun 28 2013
a(n+1) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 1; 0, 1, 1; 1, 0, 1] or [1, 1, 0; 1, 1, 1; 1, 0, 1] or [1, 1, 1; 1, 1, 0; 0, 1, 1] or [1, 0, 1; 1, 1, 0; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 0, 1; 1, 1, 1; 0, 1, 1] or of the 3 X 3 matrix [1, 1, 0; 0, 1, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
Number of sequences (e(1), ..., e(n-1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) < e(k) and e(i) <= e(k). [Martinez and Savage, 2.8] - Eric M. Schmidt, Jul 17 2017
a(n+1) is the number of words of length n over the alphabet {0,1,2} that do not contain the substrings 01 or 12 and do not start with a 2 and do not end with a 0. - Yiseth K. Rodríguez C., Sep 11 2020

			G.f. = 1 + x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 28*x^6 + 65*x^7 + 151*x^8 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Miklos Bona and Rebecca Smith, Pattern avoidance in permutations and their squares, arXiv:1901.00026 [math.CO], 2018. See H(z), Ex. 4.1.
Richard Choulet, Curtz like Transformation
Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, Non-contiguous pattern avoidance in binary trees, Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227. - From _N. J. A. Sloane_, Feb 01 2013
Stoyan Dimitrov, Sorting by shuffling methods and a queue, arXiv:2103.04332 [math.CO], 2021.
Phan Thuan Do, Thi Thu Huong Tran, and Vincent Vajnovszki, Exhaustive generation for permutations avoiding a (colored) regular sets of patterns, arXiv:1809.00742 [cs.DM], 2018.
Brian Hopkins and Hua Wang, Restricted Color n-color Compositions, arXiv:2003.05291 [math.CO], 2020.
Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 18.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 904
H. Magnusson and H. Ulfarsson, Algorithms for discovering and proving theorems about permutation patterns, arXiv preprint arXiv:1211.7110 [math.CO], 2012.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016
Vincent Vatter, Finding regular insertion encodings for permutation classes, arXiv:0911.2683 [math.CO], 2009.
Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.
Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

First differences of A052921.
Cf. A000931, A007318, A055588, A095263, A097550.
Cf. A137531, A159974, A182097, A185963, A194005.

[n le 3 select 1 else 3*Self(n-1)-2*Self(n-2)+Self(n-3): n in [1..40]]; // Vincenzo Librandi, Feb 14 2012

A034943 := proc(n): add(binomial(n+k-1, 3*k), k=0..floor(n/2)) end: seq(A034943(n), n=0..28); # Johannes W. Meijer, Aug 16 2011

LinearRecurrence[{3,-2,1},{1,1,1},30] (* Harvey P. Dale, Aug 11 2017 *)

{a(n) = if( n<1, n = 0-n; polcoeff( (1 - x + x^2) / (1 - 2*x + 3*x^2 - x^3) + x * O(x^n), n), n = n-1; polcoeff( (1 - x + x^2) / (1 - 3*x + 2*x^2 - x^3) + x * O(x^n), n))} /* Michael Somos, Mar 31 2012 */

@CachedFunction
def a(n): # a = A034943
    if (n<3): return 1
    else: return 3*a(n-1) - 2*a(n-2) + a(n-3)
[a(n) for n in range(51)] # G. C. Greubel, Apr 22 2023

a(n) = 3*a(n-1) - 2*a(n-2) + a(n-3).
a(n) = Sum_{k=0..floor(n/2)} binomial(n+k-1, 3*k). - Paul Barry, Jul 06 2004
G.f.: (1 - 2*x)/(1 - 3*x + 2*x^2 - x^3). - Paul Barry, Jul 06 2005
G.f.: 1 + x / (1 - x / (1 - x / (1 - x / (1 + x / (1 - x))))). - Michael Somos, Mar 31 2012
a(-1 - n) = A185963(n). - Michael Somos, Mar 31 2012
a(n) = A095263(n) - 2*A095263(n-1). - G. C. Greubel, Apr 22 2023

Edited by Charles R Greathouse IV, Apr 20 2010

A052921 Expansion of (1 - x)/(1 - 3x + 2x^2 - x^3).

Original entry on oeis.org

1, 2, 4, 9, 21, 49, 114, 265, 616, 1432, 3329, 7739, 17991, 41824, 97229, 226030, 525456, 1221537, 2839729, 6601569, 15346786, 35676949, 82938844, 192809420, 448227521, 1042002567, 2422362079, 5631308624, 13091204281, 30433357674, 70748973084, 164471408185

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

First differences of A095263. - R. J. Mathar, Nov 23 2011
Partial sums of A034943 starting (1, 1, 2, 5, 12, 28, 65, ...). - Gary W. Adamson, Feb 15 2012
a(n) is the number of n (decimal) digit integers x such that all digits of x are odd and all digits of 6x are even. - Robert Israel, Apr 17 2014
a(n) is the number of words of length n over the alphabet {0,1,2} that do not contain the substrings 01 or 12 and do not end in 0. - Yiseth K. Rodríguez C., Sep 11 2020

			G.f. = 1 + 2*x + 4*x^2 + 9*x^3 + 21*x^4 + 49*x^5 + 114*x^6 + 265*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Sergio Falcón, Binomial Transform of the Generalized k-Fibonacci Numbers, Communications in Mathematics and Applications (2019) Vol. 10, No. 3, 643-651.
I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 905
Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Cf. A000931, A034943.

Cf. A097550, A137531.

a:=[1,2,4];; for n in [4..40] do a[n]:=3*a[n-1]-2*a[n-2]+a[n-3]; od; a; # G. C. Greubel, Oct 16 2019

I:=[1,2,4]; [n le 3 select I[n] else 3*Self(n-1)-2*Self(n-2) +Self(n-3): n in [1..40]]; // Vincenzo Librandi, Feb 14 2012

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-x)/(1-3*x+2*x^2-x^3) )); // Marius A. Burtea, Oct 16 2019

spec := [S,{S=Sequence(Union(Z,Z,Prod(Sequence(Z),Z,Z,Z)))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..29);
A052921 := proc(n): add(binomial(n+k+1, n-2*k),k=0..n+1) end: seq(A052921(n), n=0..29); # Johannes W. Meijer, Aug 16 2011

LinearRecurrence[{3,-2,1},{1,2,4},40] (* Vincenzo Librandi, Feb 14 2012 *)
CoefficientList[Series[(1-x)/(1-3*x+2*x^2-x^3),{x,0,30}],x] (* Harvey P. Dale, Nov 09 2019 *)

my(x='x+O('x^40)); Vec((1-x)/(1 -3*x +2*x^2 -x^3)) \\ G. C. Greubel, Oct 16 2019

def A077952_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-x)/(1 -3*x +2*x^2 -x^3)).list()
A077952_list(40) # G. C. Greubel, Oct 16 2019

G.f.: (1 - x)/(1 - 3*x + 2*x^2 - x^3).
a(n) = 3*a(n-1) - 2*a(n-2) + a(n-3), with a(0)=1, a(1)=2, a(2)=4.
a(n) = Sum_{alpha=RootOf(-1 + 3*z - 2*z^2 + z^3)} (1/23)*(8 - 5*alpha + 7*alpha^2)*alpha^(-1-n).
From Paul Barry, Jun 21 2004: (Start)
Binomial transform of the Padovan sequence A000931(n+5).
a(n) = Sum_{k=0..n+1} C(n+k+1, n-2*k). (End)
a(n) = A000931(3*n + 5). - Michael Somos, Sep 18 2012
a(n) = Sum_{i=1..n+1} A000931(3*i). - David Nacin, Nov 03 2019

A135364 First column of a triangle - see Comments lines.

Original entry on oeis.org

1, 2, 3, 7, 17, 40, 93, 216, 502, 1167, 2713, 6307, 14662, 34085, 79238, 184206, 428227, 995507, 2314273, 5380032, 12507057, 29075380, 67592058, 157132471, 365288677, 849193147, 1974134558, 4589306057, 10668842202

Offset: 0

Paul Curtz, Dec 09 2007

nonn

...1;
...2,...1;
...3,...3,...1;
...7,...5,...4,...1;
..17,..10,...7,...5,...1;
..40,..24,..13,...9,...6,...1;
..93,..57,..31,..16,..11,...7,...1;
From the second, the sum of a row gives the first term of the following one. Diagonal differences are the first term upon. First column is a(n).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Richard Choulet, Transformation à la Curtz. Curtz like Transformation, March 2008.
Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Cf. A034943, A097550, A136302, A136303, A136304, A136305, A137229, A137234, A137249.

I:=[3,7,17]; [1,2] cat [n le 3 select I[n] else 3*Self(n-1) -2*Self(n-2) +Self(n-3): n in [1..51]]; // G. C. Greubel, Apr 19 2021

a:= n-> `if`(n=0, 1, (<<7|3|2>> .<<3|1|0>, <-2|0|1>, <1|0|0>>^(n-1))[1, 3]):
seq(a(n), n=0..50);  # Alois P. Heinz, Jul 24 2008

LinearRecurrence[{3,-2,1}, {1,2,3,7,17}, 51] (* G. C. Greubel, Oct 11 2016; Apr 19 2021 *)

@CachedFunction
def A095263(n): return sum( binomial(n+j+2, 3*j+2) for j in (0..n//2) )
def A135364(n): return 1 if n==0 else 2*A095263(n-1) -3*A095263(n-2) +2*A095263(n-3)
[A135364(n) for n in (0..50)] # G. C. Greubel, Apr 19 2021

From Richard Choulet, Jan 06 2008: (Start)
a(n+1) = a(n) + a(n-1) + (n-1)*a(1) + (n-2)*a(2) + ... + 2*a(n-2) for n>=3.
O.g.f.: 1 + x*(2 - 3*x + 2*x^2) / (1 - 3*x + 2*x^2 - x^3).
a(n+3) = 3*a(n+2) - 2*a(n+1) + a(n). (End)
a(n) = A034943(n) + A034943(n+1). - R. J. Mathar, Apr 09 2008
a(0) = 1, a(n) = term (1,3) in the 1 X 3 matrix [7,3,2].[3,1,0; -2,0,1; 1,0,0]^(n-1) (n>0). - Alois P. Heinz, Jul 24 2008
a(n) = 2*A095263(n-1) -3*A095263(n-2) +2*A095263(n-3) with a(0) = 1. - G. C. Greubel, Apr 19 2021

More terms from Richard Choulet, Jan 06 2008

A136303 Expansion of g.f. (1 +x^2)/((1-x)^2(1 -3x +2*x^2 -x^3)).

Original entry on oeis.org

1, 5, 17, 48, 123, 300, 714, 1679, 3925, 9149, 21296, 49537, 115192, 267824, 622653, 1447533, 3365149, 7823068, 18186475, 42278476, 98285586, 228486323, 531166317, 1234811937, 2870589548, 6673311137, 15513566304, 36064666240, 83840177305

Offset: 0

Richard Choulet, Mar 22 2008

Previous name: Transform of 0 by the reciprocal transformation to T_{1,1} (see link).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Richard Choulet, Curtz-like transformation.
Index entries for linear recurrences with constant coefficients, signature (5,-9,8,-4,1).

Cf. A095263, A097550, A135364, A136302, A136304, A136305, A137229, A137234, A137249.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1+x^2)/((1-x)^2*(1-3*x+2*x^2-x^3)) )); // G. C. Greubel, Apr 19 2021

A136303:= n-> -2*(n+2) + add( (5*binomial(n+k+2, 3*k+2) - 4*binomial(n +k+1, 3*k+2) + 2*binomial(n+k, 3*k+2)), k=0..n/2 );
seq(A136303(n), n=0..40); # G. C. Greubel, Apr 19 2021

LinearRecurrence[{5,-9,8,-4,1},{1,5,17,48,123},40] (* Harvey P. Dale, Apr 01 2018 *)

def A136303_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x^2)/((1-x)^2*(1-3*x+2*x^2-x^3)) ).list()
A136303_list(40) # G. C. Greubel, Apr 19 2021

G.f.: f(z) = 1 +5*z + ... = (1+z^2)/((1-z)^2*(1-3*z+2*z^2-z^3)).
a(n+5) = 5*a(n+4) -9*a(n+3) +8*a(n+2) -4*a(n+1) +a(n) (n>=0). - Richard Choulet, Apr 07 2009
From G. C. Greubel, Apr 19 2021: (Start)
a(n) = -2*(n+2) + 5*A095263(n) - 4*A095263(n-1) + 2*A095263(n-2).
a(n) = -2*(n+2) + Sum_{k=0..floor(n/2)} (5*binomial(n+k+2, 3*k+2) - 4*binomial(n +k+1, 3*k+2) + 2*binomial(n+k, 3*k+2)). (End)

A136304 Expansion of g.f. (1-z)^2(1-sqrt(1-4z))/(2z(1 - 3z + 2z^2 - z^3)).

Original entry on oeis.org

1, 2, 5, 14, 40, 116, 344, 1047, 3273, 10500, 34503, 115838, 396244, 1377221, 4851665, 17285662, 62173297, 225424527, 822919439, 3021713140, 11151957809, 41340655956, 153853915410, 574593145517, 2152679745351, 8087904580883, 30466311814036, 115036597198845

Offset: 0

Richard Choulet, Mar 22 2008

Previous name was: Transform of A000108 by the T_{0,0} transformation (see link).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Richard Choulet, Curtz-like transformation.

Cf. A097550, A135364, A136302, A136303, A136305, A137229, A137234, A137249.

Cf. A000108, A034943.

A034943:= func< n | (&+[Binomial(n+j-1, 3*j): j in [0..Floor(n/2)]]) >;
[(&+[A034943(j+1)*Catalan(n-j): j in [0..n]]): n in [0..35]]; // G. C. Greubel, Apr 19 2021

A034943[n_]:= A034943[n]= Sum[Binomial[n+k-1, 3*k], {k, 0, n/2}];
Table[Sum[A034943[j+1]*CatalanNumber[n-j], {j,0,n}], {n,0,35}] (* G. C. Greubel, Apr 19 2021 *)

def A034943(n): return sum(binomial(n+j-1,3*j) for j in (0..n//2))
[sum(A034943(j+1)*catalan_number(n-j) for j in (0..n)) for n in (0..35)] # G. C. Greubel, Apr 19 2021

G.f.: (1-z)^2*(1-sqrt(1-4*z))/(2*z*(1 - 3*z + 2*z^2 - z^3)).
Conjecture: (n+1)*a(n) + (-8*n+1)*a(n-1) + 3*(7*n-8)*a(n-2) + (-23*n+49)*a(n-3) + (13*n-32)*a(n-4) + 2*(-2*n+7)*a(n-5) = 0. - R. J. Mathar, Feb 29 2016
a(n) = Sum_{j=0..n} A034943(j+1)*A000108(n-j). - G. C. Greubel, Apr 19 2021

New name using g.f., Joerg Arndt, Apr 20 2021

A136305 Expansion of g.f. (3 -x +2x^2)/(1 -3x +2*x^2 -x^3).

Original entry on oeis.org

3, 8, 20, 47, 109, 253, 588, 1367, 3178, 7388, 17175, 39927, 92819, 215778, 501623, 1166132, 2710928, 6302143, 14650705, 34058757, 79177004, 184064203, 427897358, 994740672, 2312491503, 5375890523, 12497429235, 29052998162, 67540026539, 157011512528

Offset: 0

Richard Choulet, Mar 22 2008

Previous name: Transform of A000027 by the T_{1,2} transformation (see link).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Richard Choulet, Curtz-like transformation.
Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Cf. A097550, A135364, A136302, A136303, A136304, A137229, A137234, A137249.

[n le 3 select 2^(n-1)*(n+2) else 3*Self(n-1) - 2*Self(n-2) +Self(n-3): n in [1..41]]; // G. C. Greubel, Apr 19 2021

LinearRecurrence[{3,-2,1}, {3,8,20}, 40] (* G. C. Greubel, Apr 19 2021 *)
CoefficientList[Series[(3-x+2x^2)/(1-3x+2x^2-x^3),{x,0,40}],x] (* Harvey P. Dale, Oct 15 2021 *)

@CachedFunction
def a(n): return 2^n*(n+3) if n<3 else sum((-1)^j*(3-j)*a(n-j-1) for j in (0..2))
[a(n) for n in (0..40)] # G. C. Greubel, Apr 19 2021

G.f.: f(z) = 3 +8*z + ... = (3 -z +2*z^2)/(1 -3*z +2*z^2 -z^3).

a(n+3) = 3*a(n+2) -2*a(n+1) +a(n) (n>=0). - Richard Choulet, Apr 07 2009

A137531 a(n) = 3a(n-1) - 2a(n-2) + a(n-3).

Original entry on oeis.org

1, 4, 10, 23, 53, 123, 286, 665, 1546, 3594, 8355, 19423, 45153, 104968, 244021, 567280, 1318766, 3065759, 7127025, 16568323, 38516678, 89540413, 208156206, 483904470, 1124941411, 2615171499, 6079536145, 14133206848, 32855719753, 76380281708, 177562612466

Offset: 0

Paul Curtz, Apr 25 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Cf. A159347, A097550.

LinearRecurrence[{3, -2, 1}, {1, 4, 10}, 100] (* G. C. Greubel, Feb 17 2017 *)

a=[1,4,10];for(i=1,99,a=concat(a,3*a[#a]-2*a[#a-1]+a[#a-2]));a \\ Charles R Greathouse IV, Jun 01 2011

Vec((1 + x) / (1 - 3*x + 2*x^2 - x^3) + O(x^40)) \\ Colin Barker, Feb 17 2017

G.f.: (1 + x) / (1 - 3*x + 2*x^2 - x^3). - Colin Barker, Feb 17 2017

More terms from Vladimir Joseph Stephan Orlovsky, Jan 20 2009

A097551 Number of positive words of length n in the monoid Br_4 of positive braids on 5 strands.

Original entry on oeis.org

1, 4, 13, 37, 101, 273, 737, 1990, 5374, 14513, 39194, 105848, 285855, 771985, 2084836, 5630344, 15205404, 41063976, 110898081, 299493268, 808816679, 2184304257, 5898969706, 15930859211, 43023152830, 116189067703

Offset: 0

D n Verma, Aug 16 2004

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-5,5,-3,1).

Cf. A097550, A097552, A097553, A097554, A097555, A097556.

R:=PowerSeriesRing(Integers(), 50);
Coefficients(R!( (1+x^2)^2/(1-4*x+5*x^2-5*x^3+3*x^4-x^5) )); // G. C. Greubel, Apr 19 2021

<Ryan Propper, Sep 27 2005 *)
LinearRecurrence[{4,-5,5,-3,1}, {1,4,13,37,101}, 51] (* G. C. Greubel, Apr 19 2021 *)

def A097551_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x^2)^2/(1-4*x+5*x^2-5*x^3+3*x^4-x^5) ).list()
A097551_list(50) # G. C. Greubel, Apr 19 2021

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

More terms from Ryan Propper, Sep 27 2005

A097552 Number of positive words of length n in the monoid Br_5 of positive braids on 6 strands.

Original entry on oeis.org

1, 5, 20, 67, 209, 630, 1873, 5540, 16357, 48265, 142387, 420027, 1239006, 3654820, 10780958, 31801551, 93807834, 276713194, 816245143, 2407749755, 7102350204, 20950424039, 61799299470, 182294802589, 537730934397

Offset: 0

D n Verma, Aug 16 2004

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-8,7,-4,1).

Cf. A097550, A097551, A097553, A097554, A097555, A097556.

R:=PowerSeriesRing(Integers(), 40);
Coefficients(R!( (1+x^2)^3/(1-5*x+8*x^2-7*x^3+4*x^4-x^5) )); // G. C. Greubel, Apr 19 2021

LinearRecurrence[{5,-8,7,-4,1}, {1,5,20,67,209,630,1873}, 40] (* G. C. Greubel, Apr 19 2021 *)

def A097552_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x^2)^3/(1-5*x+8*x^2-7*x^3+4*x^4-x^5) ).list()
A097552_list(40) # G. C. Greubel, Apr 19 2021

G.f.: (1 + x^2)^3/(1 - 5*x + 8*x^2 - 7*x^3 + 4*x^4 - x^5). - T. D. Noe, Nov 02 2006

Corrected by T. D. Noe, Nov 02 2006

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

A034943 Binomial transform of Padovan sequence A000931.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A052921 Expansion of (1 - x)/(1 - 3*x + 2*x^2 - x^3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

A135364 First column of a triangle - see Comments lines.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

A136303 Expansion of g.f. (1 +x^2)/((1-x)^2*(1 -3*x +2*x^2 -x^3)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

A136304 Expansion of g.f. (1-z)^2*(1-sqrt(1-4*z))/(2*z*(1 - 3*z + 2*z^2 - z^3)).

Views

Author

Keywords

A095263 a(n+3) = 3a(n+2) - 2a(n+1) + a(n).

A052921 Expansion of (1 - x)/(1 - 3x + 2x^2 - x^3).

A136303 Expansion of g.f. (1 +x^2)/((1-x)^2(1 -3x +2*x^2 -x^3)).

A136304 Expansion of g.f. (1-z)^2(1-sqrt(1-4z))/(2z(1 - 3z + 2z^2 - z^3)).

A136305 Expansion of g.f. (3 -x +2x^2)/(1 -3x +2*x^2 -x^3).

A137531 a(n) = 3a(n-1) - 2a(n-2) + a(n-3).