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

1, 3, 6, 11, 20, 36, 64, 113, 199, 350, 615, 1080, 1896, 3328, 5841, 10251, 17990, 31571, 55404, 97228, 170624, 299425, 525455, 922110, 1618191, 2839728, 4983376, 8745216, 15346785, 26931731, 47261894, 82938843, 145547524, 255418100, 448227520, 786584465

Offset: 0

Author

N. J. A. Sloane, Nov 17 2002

Keywords

• nonn
• easy

Comments

a(n) is the number of binary words of length n+2 such that there is at least one run of 0's and every run of 0's is of length >=2. a(1)=3 because we have: {0,0,0}, {0,0,1}, {1,0,0}. - Geoffrey Critzer, Jan 12 2013

INVERT transform of A099254: (1, 2, 1, -2, -4, -2, 3, 6, 3, ...). - Gary W. Adamson, Jan 11 2017

a(n) is the number of nonempty subsets A of {1, 2, ..., n+1} with the property that every element in A has at least one consecutive neighbor also in A. That is, for every element x in A, either x-1 is in A or x+1 is in A. - MingKun Yue, Mar 07 2025

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..4092
• Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-1).

Crossrefs

Cf. A018918, A099254, A005314 (first differences).

Programs

Mathematica

nn=40; a=x^2/(1-x); Drop[CoefficientList[Series[(a+1)/(1-x a/(1-x))/(1-x)-1/(1-x), {x,0,nn}], x], 2] (* Geoffrey Critzer, Jan 12 2013 *)
LinearRecurrence[{3, -3, 2, -1}, {1, 3, 6, 11}, 36] (* or *)
CoefficientList[ Series[1/(x^4 - 2 x^3 + 3 x^2 - 3 x + 1), {x, 0, 35}], x] (* Robert G. Wilson v, Nov 25 2016 *)

PARI

Vec((1-x)^(-1)/(1-2*x+x^2-x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 27 2012

Formula

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

a(n) = A005251(n+4) - 1. a(n+1) - a(n) = A005314(n+2). - R. J. Mathar, Sep 19 2008

a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3) - a(n-4). - Seiichi Manyama, Nov 25 2016

a(n) = Sum_{i=1..(n+3)} binomial((n+3)-i, (n+3)-3*i). - Wesley Ivan Hurt, Jul 07 2020

a(n) ~ (48 - 11*r + 29*r^2) / (23 * r^n), where r = 0.569840290998... is the root of the equation r*(2 - r + r^2) = 1. - Vaclav Kotesovec, Apr 15 2024

From MingKun Yue, Mar 07 2025: (Start)

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

a(n) = a(n-1) + Sum_{i=1..(n-3)} a(i) + n. (End)