A073778 a(n) = Sum_{k=0..n} T(k)*T(n-k), where T is A000073; convolution of A000073 with itself.

0, 0, 0, 0, 1, 2, 5, 12, 26, 56, 118, 244, 499, 1010, 2027, 4040, 8004, 15776, 30956, 60504, 117845, 228818, 443057, 855732, 1649022, 3171128, 6086626, 11662252, 22309543, 42614178, 81286743, 154856528, 294660040, 560052736, 1063367384, 2017030256

Offset

0,6

Comments

Number of binary sequences of length n+1 that have exactly one subsequence 000. Example: a(4)=5 because we have 00010,00011,01000,10001 and 11000. Column 1 of A118390. - Emeric Deutsch, Apr 27 2006

Let (b(n)) be the p-INVERT of (1,1,1,0,0,0,0,0,0,...) using p(S) = 1 - S^2; then b(n) = a(n+3) for n >= 0. See A292324. - Clark Kimberling, Sep 15 2017

Links

Michael De Vlieger, Table of n, a(n) for n = 0..3770, terms n = 2..1002 from Vincenzo Librandi.

D. Birmajer, J. Gil and M. Weiner, Linear recurrence sequences and their convolutions via Bell polynomials, arXiv:1405.7727 [math.CO], 2014; see also, J. Int. Seq. 18 (2015) # 15.1.2.

Michael Dairyko, Lara Pudwell, Samantha Tyner 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

Emrah Kilic and Helmut Prodinger, A Note on the Conjecture of Ramirez and Sirvent, J. Int. Seq. 17 (2014) # 14.5.8.

J. L. Ramirez and V. F. Sirvent, Incomplete Tribonacci Numbers and Polynomials, Journal of Integer Sequences, Vol. 17, 2014, #14.4.2.

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

Formula

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

a(n) = Sum_{k=0..n-4} (k+1)*Sum_{j=0..k} binomial(j,n-3*k+2*j-4)*binomial(k,j). - Vladimir Kruchinin, Dec 14 2011

(n-2)*a(n) - (n-1)*a(n-1) - n*a(n-2) - (n+1)*a(n-3) = 0, n > 2. - Michael D. Weiner, Nov 18 2014

Maple

A073778:=proc(n) coeftayl(x^4/(1-x-x^2-x^3)^2, x=0, n); end proc: seq(A073778(n), n=0..40); # Wesley Ivan Hurt, Nov 17 2014

Mathematica

CoefficientList[Series[x^4/(1-x-x^2-x^3)^2, {x, 0, 40}], x]

Prog

(Sage) [( x^4/(1-x-x^2-x^3)^2 ).series(x, n+1).list()[n] for n in (0..40)] # Zerinvary Lajos, Jun 02 2009; modified by G. C. Greubel, Dec 15 2021
(Maxima)
a(n):= sum((k+1)*sum(binomial(j, n-3*k+2*j-4)*binomial(k, j), j, 0, k), k, 0, n-4);
makelist(a(n), n, 0, 30); /* Vladimir Kruchinin, Dec 14 2011 */
(PARI) T(n) = ([0, 1, 0; 0, 0, 1; 1, 1, 1]^n)[1, 3]; \\ A000073
a(n) = sum(k=0, n, T(k)*T(n-k)); \\ Michel Marcus, Oct 20 2021

Crossrefs

Cf. A000073, A118390.

Sequence in context: A116726 A228078 A125180 * A033490 A221950 A116716

Adjacent sequences: A073775 A073776 A073777 * A073779 A073780 A073781

Keyword

easy,nonn

Author

Mario Catalani (mario.catalani(AT)unito.it), Aug 10 2002

Extensions

Two initial zeros inserted by Hans J. H. Tuenter, Oct 20 2021

Status

approved