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

Author

R. K. Guy, Mar 23 2008

Keywords

• nonn
• easy

Comments

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

Examples

			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
		

Links

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

Crossrefs

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

Programs

Mathematica

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

PARI

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

PARI

{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 */

Formula

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

Extensions

More terms from Max Alekseyev, Mar 23 2008

Name clarified by Michael Somos, Jul 25 2025