A116201 -id:A116201 - cp's OEIS frontend

A116732 a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4) with a(0) = a(1) = a(2) = 0, a(3) = 1.

0, 0, 0, 1, 1, 2, 4, 6, 11, 19, 32, 56, 96, 165, 285, 490, 844, 1454, 2503, 4311, 7424, 12784, 22016, 37913, 65289, 112434, 193620, 333430, 574195, 988811, 1702816, 2932392, 5049824, 8696221, 14975621, 25789274, 44411292, 76479966, 131704911, 226806895

Offset: 0

R. K. Guy, Mar 23 2008

This sequence is an example of a "symmetric" quartic recurrence and has some expected divisibility properties.

a(n-3) counts partially ordered partitions of (n-3) into parts 1,2,3 where only the order of the adjacent 1's and 3's are unimportant (see example). - David Neil McGrath, Jul 25 2015

			Partially ordered partitions of (n-3) into parts 1,2,3 where only the order of adjacent 1's and 3's are unimportant. E.g., a(n-3)=a(6)=19. These are (33),(321),(312),(231),(123),(132),(3111),(2211),(1122),(1221),(2112),(2121),(1212),(21111),(12111),(11211),(11121),(11112),(111111). - _David Neil McGrath_, Jul 25 2015
G.f. = x^3 + x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 11*x^8 + 19*x^9 + 32*x^10 + ... - _Michael Somos_, Jul 25 2025

Michael De Vlieger, Table of n, a(n) for n = 0..4239
Jarib R. Acosta, Yadira Caicedo, Juan P. Poveda, José L. Ramírez, and Mark Shattuck, Some New Restricted n-Color Composition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.6.4.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,-1).

Close to A000786 (& A048239), A115992, A115993. Cf. A116201.

LinearRecurrence[{1, 1, 1, -1}, {0, 0, 0, 1}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 02 2012 *)
CoefficientList[Series[x^3/(1-x-x^2-x^3+x^4),{x,0,40}],x] (* Harvey P. Dale, Mar 25 2018 *)

v=[0,0,0,1];for(i=1,40,v=concat(v,v[#v]+v[#v-1]+v[#v-2]-v[#v-3]));v \\ Derek Orr, Aug 27 2015

{a(n) = if(n<0, -a(2-n), polcoeff(x^3/(1 - x - x^2 - x^3 + x^4 + x*O(x^n)), n))} /* Michael Somos, Jul 25 2025 */

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

a(n) = -a(2-n) for all n in Z. - Michael Somos, Jul 25 2025

More terms from Max Alekseyev, Mar 23 2008

Name clarified by Michael Somos, Jul 25 2025

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

Original entry on oeis.org

0, 1, 1, 7, 15, 64, 175, 631, 1905, 6433, 20224, 66529, 212625, 692119, 2226799, 7217728, 23284815, 75343591, 243328225, 786800449, 2542156800, 8217744577, 26556314401, 85835882791, 277405671375, 896595420736, 2897714688751

Offset: 0

R. J. Mathar, at the request of R. K. Guy, Sep 03 2010

The member k=7 of a family of sequences starting 0,1,1,k with recurrence a(n) = a(n-1)+k*a(n-2)+a(n-3)-a(n-4).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Hugh Williams, R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory 7 (5) (2011) 1255-1277
Index entries for linear recurrences with constant coefficients, signature (1,7,1,-1).

Cf. A116201 (k=1), A105309 (k=2), A152090 (k=3), A007598 (k=4), A005178 (k=5), A003757 (k=6).

I:=[0, 1, 1, 7]; [n le 4 select I[n] else Self(n-1) + 7*Self(n-2) + Self(n-3) - Self(n-4): n in [1..30]]; // Vincenzo Librandi, Dec 19 2012

CoefficientList[Series[-x*(x - 1)*(1 + x)/(1 - x - 7*x^2 - x^3 + x^4), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 19 2012 *)
LinearRecurrence[{1,7,1,-1},{0,1,1,7},30] (* Harvey P. Dale, Nov 15 2020 *)

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

The roots (r1..r4) of the characteristic polynomials for this "family" of sequences have the following form (not simplified) for k= 1,2,3,4,5,6.... r1=(sqrt(4*k+10+2*sqrt(4*k+9))+sqrt(4*k-6+2*sqrt(4*k+9)))/4. r2=(sqrt(4*k+10+2*sqrt(4*k+9))-sqrt(4*k-6+2*sqrt(4*k+9)))/4. r3=(-sqrt(4*k+10-2*sqrt(4*k+9))-sqrt(4*k-6-2*sqrt(4*k+9)))/4. r4=(-sqrt(4*k+10-2*sqrt(4*k+9))+sqrt(4*k-6-2*sqrt(4*k+9)))/4. For k=1,2,3, r3 and r4 are complex . Closed-form (not simplified) is as follows for all k (note:for k1-k3 set r3 and r4 =0 and round a(n) to nearest integer): a(n)=sqrt(4*k+9)/(4*k+9)*(((r1)^n+(r2)^n)-((r3)^n+(r4)^n)). [Tim Monahan, Sep 17 2011]

A171065 G.f. -x(x-1)(1+x)/(1-x-8*x^2-x^3+x^4).

Original entry on oeis.org

0, 1, 1, 8, 17, 81, 224, 881, 2737, 9928, 32481, 113761, 380800, 1313441, 4441121, 15215688, 51677297, 176530481, 600723424, 2049428881, 6980069457, 23799693448, 81088954561, 276417142721, 941948403200, 3210574806081

Offset: 0

R. J. Mathar, at the request of R. K. Guy, Sep 03 2010

The member k=8 of a family of sequences starting 0,1,1,k with recurrence a(n) = a(n-1)+k*a(n-2)+a(n-3)-a(n-4).

This is the case P1 = 1, P2 = -10, Q = 1 of the 3 parameter family of 4th-order linear divisibility sequences found by Williams and Guy. - Peter Bala, Mar 31 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Hugh Williams, R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory vol. 7 (5) (2011) 1255-1277
H. C. Williams and R. K. Guy, Some Monoapparitic Fourth Order Linear Divisibility Sequences Integers, Volume 12A (2012) The John Selfridge Memorial Volume
Index entries for linear recurrences with constant coefficients, signature (1,8,1,-1).

Cf. A116201 (k=1), A105309 (k=2), A152090 (k=3), A007598 (k=4), A005178 (k=5), A003757 (k=6). A100047.

I:=[0, 1, 1, 8]; [n le 4 select I[n] else Self(n-1) + 8*Self(n-2) + Self(n-3) - Self(n-4): n in [1..30]]; // Vincenzo Librandi, Dec 19 2012

CoefficientList[Series[-x*(x - 1)*(1 + x)/(1 - x - 8*x^2 - x^3 + x^4), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 19 2012 *)
LinearRecurrence[{1,8,1,-1},{0,1,1,8},30] (* Harvey P. Dale, Dec 27 2017 *)

a(n)= +a(n-1) +8*a(n-2) +a(n-3) -a(n-4).
From Peter Bala, Mar 31 2014: (Start)
a(n) = ( T(n,alpha) - T(n,beta) )/(alpha - beta), where alpha = (1 + sqrt(41))/4 and beta = (1 - sqrt(41))/4 and T(n,x) denotes the Chebyshev polynomial of the first kind.
a(n) = the bottom left entry of the 2 X 2 matrix T(n, M), where M is the 2 X 2 matrix [0, 5/2; 1, 1/2].
a(n) = U(n-1,i*(1 + sqrt(2))/2)*U(n-1,i*(1 + sqrt(2))/2), where U(n,x) denotes the Chebyshev polynomial of the second kind.
See the remarks in A100047 for the general connection between Chebyshev polynomials and 4th-order linear divisibility sequences. (End)

A171066 G.f. -x(x-1)(1+x)/(1-x-9*x^2-x^3+x^4).

Original entry on oeis.org

0, 1, 1, 9, 19, 100, 279, 1189, 3781, 14661, 49600, 184141, 641421, 2333629, 8240959, 29700900, 105561739, 378777169, 1350292761, 4835148121, 17260998400, 61748847081, 220582688041, 788748162049, 2818480203099, 10076047502500

Offset: 0

R. J. Mathar, at the request of R. K. Guy, Sep 03 2010

The member k=9 of a family of sequences starting 0,1,1,k with recurrence a(n) = a(n-1)+k*a(n-2)+a(n-3)-a(n-4).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Hugh Williams, R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory vol. 7 (5) (2011) 1255-1277
Index entries for linear recurrences with constant coefficients, signature (1,9,1,-1).

Cf. A116201 (k=1), A105309 (k=2), A152090 (k=3), A007598 (k=4), A005178 (k=5), A003757 (k=6).

I:=[0, 1, 1, 9]; [n le 4 select I[n] else Self(n-1) + 9*Self(n-2) + Self(n-3) - Self(n-4): n in [1..30]]; // Vincenzo Librandi, Dec 19 2012

CoefficientList[Series[-x*(x - 1)*(1 + x)/(1 - x - 9*x^2 - x^3 + x^4), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 19 2012 *)

a(n)= +a(n-1) +9*a(n-2) +a(n-3) -a(n-4)

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

Original entry on oeis.org

0, 1, 1, 10, 21, 121, 340, 1561, 5061, 20890, 72721, 285121, 1028160, 3931201, 14425201, 54480250, 201635301, 756931801, 2813339860, 10529812921, 39218508021, 146573045290, 546474598561, 2040893746561, 7612994269440

Offset: 0

R. J. Mathar, at the request of R. K. Guy, Sep 03 2010

The member k=10 of a family of sequences starting 0,1,1,k with recurrence a(n) = a(n-1)+k*a(n-2)+a(n-3)-a(n-4).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Hugh Williams, R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory vol. 7 (5) (2011) 1255-1277
Index entries for linear recurrences with constant coefficients, signature (1,10,1,-1).

Cf. A116201 (k=1), A105309 (k=2), A152090 (k=3), A007598 (k=4), A005178 (k=5), A003757 (k=6).

I:=[0, 1, 1, 10]; [n le 4 select I[n] else Self(n-1) + 10*Self(n-2) + Self(n-3) - Self(n-4): n in [1..30]]; // Vincenzo Librandi, Dec 19 2012

CoefficientList[Series[-x*(x - 1)*(1 + x)/((x^2 + 3*x + 1)*(x^2 - 4*x + 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 19 2012 *)
LinearRecurrence[{1,10,1,-1},{0,1,1,10},30] (* Harvey P. Dale, Dec 24 2017 *)

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

a(n)= -(-1)^n*A005248(n)/7 + 2*A001075(n)/7.

A171068 G.f. -x(x-1)(1+x)/(1-x-11*x^2-x^3+x^4).

Original entry on oeis.org

0, 1, 1, 11, 23, 144, 407, 2003, 6601, 28897, 103104, 425569, 1582009, 6337475, 24062039, 94930704, 364368599, 1426330907, 5505254161, 21464332033, 83084090112, 323270665729, 1253154734833, 4870751815931, 18895640474711

Offset: 0

R. J. Mathar, at the request of R. K. Guy, Sep 03 2010

The member k=11 of a family of sequences starting 0,1,1,k with recurrence a(n) = a(n-1)+k*a(n-2)+a(n-3)-a(n-4).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Hugh Williams, R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory vol. 7 (5) (2011) 1255-1277
Index entries for linear recurrences with constant coefficients, signature (1,11,1,-1).

Cf. A116201 (k=1), A105309 (k=2), A152090 (k=3), A007598 (k=4), A005178 (k=5), A003757 (k=6).

I:=[0, 1, 1, 11]; [n le 4 select I[n] else Self(n-1) + 11*Self(n-2) + Self(n-3) - Self(n-4): n in [1..30]]; // Vincenzo Librandi, Dec 19 2012

CoefficientList[Series[-x*(x - 1)*(1 + x)/(1 - x - 11*x^2 - x^3 + x^4), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 19 2012 *)

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

A171069 G.f. -x(x-1)(1+x)/(1-x-12*x^2-x^3+x^4).

Original entry on oeis.org

0, 1, 1, 12, 25, 169, 480, 2521, 8425, 38988, 142129, 615889, 2352000, 9845809, 38543569, 158429388, 628446025, 2558296441, 10219534560, 41389108489, 165953373625, 670283913612, 2692893971041, 10860865199521, 43679923392000

Offset: 0

R. J. Mathar, at the request of R. K. Guy, Sep 03 2010

The member k=12 of a family of sequences starting 0,1,1,k with recurrence a(n) = a(n-1)+k*a(n-2)+a(n-3)-a(n-4).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Hugh Williams, R. K. Guy, Some fourth-order linear divisibility sequences, Intl. J. Number Theory vol. 7 (5) (2011) 1255-1277
Index entries for linear recurrences with constant coefficients, signature (1,12,1,-1).

Cf. A116201 (k=1), A105309 (k=2), A152090 (k=3), A007598 (k=4), A005178 (k=5), A003757 (k=6).

I:=[0, 1, 1, 12]; [n le 4 select I[n] else Self(n-1) + 12*Self(n-2) + Self(n-3) - Self(n-4): n in [1..30]]; // Vincenzo Librandi, Dec 19 2012

CoefficientList[Series[-x*(x - 1)*(1 + x)/(1 - x - 12*x^2 - x^3 + x^4), {x, 0, 40}], x] (* Vincenzo Librandi, Dec 19 2012 *)
LinearRecurrence[{1,12,1,-1},{0,1,1,12},30] (* Harvey P. Dale, Nov 04 2024 *)

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

cp's OEIS Frontend

A116732 a(n) = a(n-1) + a(n-2) + a(n-3) - a(n-4) with a(0) = a(1) = a(2) = 0, a(3) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A171065 G.f. -x*(x-1)*(1+x)/(1-x-8*x^2-x^3+x^4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A171066 G.f. -x*(x-1)*(1+x)/(1-x-9*x^2-x^3+x^4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A171068 G.f. -x*(x-1)*(1+x)/(1-x-11*x^2-x^3+x^4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A171069 G.f. -x*(x-1)*(1+x)/(1-x-12*x^2-x^3+x^4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

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

A171065 G.f. -x(x-1)(1+x)/(1-x-8*x^2-x^3+x^4).

A171066 G.f. -x(x-1)(1+x)/(1-x-9*x^2-x^3+x^4).

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

A171068 G.f. -x(x-1)(1+x)/(1-x-11*x^2-x^3+x^4).

A171069 G.f. -x(x-1)(1+x)/(1-x-12*x^2-x^3+x^4).