cp's OEIS Frontend

A118869 Triangle read by rows: T(n,k) is the number of binary sequences of length n containing k subsequences 0101 (n,k>=0).

%I A118869 #16 Feb 06 2020 22:16:52
%S A118869 1,2,4,8,15,1,28,4,53,10,1,100,24,4,188,57,10,1,354,128,26,4,667,278,
%T A118869 68,10,1,1256,596,164,28,4,2365,1260,381,79,10,1,4454,2628,876,200,30,
%U A118869 4,8388,5430,1977,488,90,10,1,15796,11136,4380,1184,236,32,4,29747,22683
%N A118869 Triangle read by rows: T(n,k) is the number of binary sequences of length n containing k subsequences 0101 (n,k>=0).
%C A118869 Row n has floor(n/2) terms (n>=2). Sum of entries in row n is 2^n (A000079). T(n,0) = A118870(n). T(n,1) = A118871(n). Sum(k*T(n,k), k=0..n-1) = (n-3)*2^(n-4) (A001787).
%H A118869 Alois P. Heinz, <a href="/A118869/b118869.txt">Rows n = 1..200, flattened</a>
%H A118869 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, 2009, page 211.
%F A118869 G.f.: G(t,z) = [1+(1-t)z^2]/[1-2z+(1-t)z^2*(1-z)^2].
%e A118869 T(7,2) = 4 because we have 0101010, 0101011, 0010101 and 1010101.
%e A118869 Triangle starts:
%e A118869    1;
%e A118869    2;
%e A118869    4;
%e A118869    8;
%e A118869   15,  1;
%e A118869   28,  4;
%e A118869   53, 10, 1;
%e A118869   ...
%p A118869 G:=(1+(1-t)*z^2)/(1-2*z+(1-t)*z^2*(1-z)^2): Gser:=simplify(series(G,z=0,20)): P[0]:=1: for n from 1 to 16 do P[n]:=coeff(Gser,z^n) od: 1;2;for n from 1 to 16 do seq(coeff(P[n],t,j),j=0..floor(n/2)-1) od; # yields sequence in triangular form
%p A118869 # second Maple program:
%p A118869 b:= proc(n, t) option remember; `if`(n=0, 1,
%p A118869        expand(b(n-1, `if`(t=3, 4, 2))+
%p A118869        b(n-1, 3-2*irem(t, 2))*`if`(t=4, x, 1)))
%p A118869     end:
%p A118869 T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
%p A118869 seq(T(n), n=0..16); # _Alois P. Heinz_, Nov 28 2013
%t A118869 nn=15;CoefficientList[Series[1/(1-2z-(u-1)z^4/(1-(u-1)z^2)),{z,0,nn}],{z,u}]//Grid (* _Geoffrey Critzer_, Nov 29 2013 *)
%Y A118869 Cf. A000079, A118870, A118871, A001787, A118429, A332052.
%K A118869 nonn,tabf
%O A118869 0,2
%A A118869 _Emeric Deutsch_, May 03 2006