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

%I #19 Jul 18 2023 10:36:55

%S 0,0,0,1,4,10,22,47,98,199,396,777,1508,2900,5534,10492,19782,37119,

%T 69358,129118,239578,443229,817822,1505389,2764986,5068435,9273928,

%U 16940488,30897020,56271128,102347564,185922589,337353688,611462514

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

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

%H Alois P. Heinz, <a href="/A118430/b118430.txt">Table of n, a(n) for n = 0..1000</a>

%H T. Mansour and M. Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Shattuck/shattuck3.html">Counting Peaks and Valleys in a Partition of a Set</a>, J. Int. Seq. 13 (2010), 10.6.8, Lemma 2.1, k=2, 1 peak.

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,6,-5,2,-1).

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

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

%p 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);

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

%Y Cf. A005314, A118429, A255386.

%K nonn

%O 0,5

%A _Emeric Deutsch_, Apr 27 2006