A118430 Number of binary sequences of length n containing exactly one subsequence 010.

0, 0, 0, 1, 4, 10, 22, 47, 98, 199, 396, 777, 1508, 2900, 5534, 10492, 19782, 37119, 69358, 129118, 239578, 443229, 817822, 1505389, 2764986, 5068435, 9273928, 16940488, 30897020, 56271128, 102347564, 185922589, 337353688, 611462514

Offset

0,5

Comments

With only two 0's at the beginning, the convolution of A005314 with itself. Column 1 of A118429.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

T. Mansour and M. Shattuck, Counting Peaks and Valleys in a Partition of a Set, J. Int. Seq. 13 (2010), 10.6.8, Lemma 2.1, k=2, 1 peak.

Index entries for linear recurrences with constant coefficients, signature (4,-6,6,-5,2,-1).

Formula

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

Example

a(4) = 4 because we have 0100, 0101, 0010 and 1010.
a(5) = 10: 00010, 00100, 00101, 01000, 01001, 01011, 10010, 10100, 10101, 11010.

Maple

g:=z^3/(1-2*z+z^2-z^3)^2: gser:=series(g, z=0, 40): seq(coeff(gser, z, n), n=0..38);

Mathematica

LinearRecurrence[{4, -6, 6, -5, 2, -1}, {0, 0, 0, 1, 4, 10}, 40] (* Jean-François Alcover, May 11 2019 *)

Prog

(PARI) a(n)=([0, 1, 0, 0, 0, 0; 0, 0, 1, 0, 0, 0; 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 1, 0; 0, 0, 0, 0, 0, 1; -1, 2, -5, 6, -6, 4]^n*[0; 0; 0; 1; 4; 10])[1, 1] \\ Charles R Greathouse IV, May 13 2026
(PARI) Vec(x^3/(1-2*x+x^2-x^3)^2+O(x^99)) \\ Charles R Greathouse IV, May 13 2026

Crossrefs

Cf. A005314, A118429, A255386.

Sequence in context: A266374 A008267 A056112 * A178452 A324536 A137247

Adjacent sequences: A118427 A118428 A118429 * A118431 A118432 A118433

Keyword

nonn,easy

Author

Emeric Deutsch, Apr 27 2006

Status

approved