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

Author

Emeric Deutsch, Apr 27 2006

Keywords

• nonn

Comments

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

Examples

			a(4) = 4 because we have 0100, 0101, 0010 and 1010.
		

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

Crossrefs

Cf. A005314, A118429, A255386.

Programs

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

Formula

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