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

1, 2, 4, 8, 15, 1, 28, 4, 53, 10, 1, 100, 24, 4, 188, 57, 10, 1, 354, 128, 26, 4, 667, 278, 68, 10, 1, 1256, 596, 164, 28, 4, 2365, 1260, 381, 79, 10, 1, 4454, 2628, 876, 200, 30, 4, 8388, 5430, 1977, 488, 90, 10, 1, 15796, 11136, 4380, 1184, 236, 32, 4, 29747, 22683

Offset: 0

Author

Emeric Deutsch, May 03 2006

Keywords

• nonn
• tabf

Comments

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

Examples

			T(7,2) = 4 because we have 0101010, 0101011, 0010101 and 1010101.
Triangle starts:
   1;
   2;
   4;
   8;
  15,  1;
  28,  4;
  53, 10, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..200, flattened
• P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, page 211.

Crossrefs

Cf. A000079, A118870, A118871, A001787, A118429, A332052.

Programs

Maple

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
# second Maple program:
b:= proc(n, t) option remember; `if`(n=0, 1,
       expand(b(n-1, `if`(t=3, 4, 2))+
       b(n-1, 3-2*irem(t, 2))*`if`(t=4, x, 1)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..16); # Alois P. Heinz, Nov 28 2013

Mathematica

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

Formula

G.f.: G(t,z) = [1+(1-t)z^2]/[1-2z+(1-t)z^2*(1-z)^2].