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

Author

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

Keywords

• easy
• nonn

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.
• Daniel Birmajer, Juan B. Gil, and Michael D. 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
• Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.
• Emrah Kilic and Helmut Prodinger, A Note on the Conjecture of Ramirez and Sirvent, J. Int. Seq. 17 (2014) # 14.5.8.
• László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
• José L. Ramirez and Víctor 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).

Crossrefs

Cf. A000073, A118390.

Programs

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]

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

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

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

Extensions

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