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

1, 2, 4, 8, 15, 1, 29, 2, 1, 56, 5, 2, 1, 108, 12, 5, 2, 1, 208, 28, 12, 5, 2, 1, 401, 62, 29, 12, 5, 2, 1, 773, 136, 65, 30, 12, 5, 2, 1, 1490, 294, 145, 68, 31, 12, 5, 2, 1, 2872, 628, 319, 154, 71, 32, 12, 5, 2, 1, 5536, 1328, 694, 344, 163, 74, 33, 12, 5, 2, 1, 10671, 2787

Offset

0,2

Comments

Row n has n-2 terms (n>=3). Sum of entries in row n is 2^n (A000079). T(n,0) = A000078(n+4) (tetranacci numbers). T(n,1) = A118898(n). Sum(k*T(n,k),n>=0) = (n-3)*2^(n-4) (A001787).

Links

Alois P. Heinz, Rows n = 0..143, flattened

Formula

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

Example

T(7,2) = 5 because we have 0000010, 0000011, 0100000, 1100000 and 1000001.
Triangle starts:
    1;
    2;
    4;
    8;
   15,  1;
   29,  2, 1;
   56,  5, 2, 1;
  108, 12, 5, 2, 1;
  ...

Maple

G:=(1+(1-t)*(z+z^2+z^3))/(1-(1+t)*z-(1-t)*(z^2+z^3+z^4)): Gser:=simplify(series(G, z=0, 17)): P[0]:=1: for n from 1 to 14 do P[n]:=sort(coeff(Gser, z^n)) od: 1; 2; 4; 8; for n from 4 to 14 do seq(coeff(P[n], t, j), j=0..n-3) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n, t) option remember; `if`(n=0, 1,
      expand(b(n-1, min(3, t+1))*`if`(t>2, x, 1))+b(n-1, 0))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..14);  # Alois P. Heinz, Sep 17 2019

Mathematica

nn=15; a=x^3/(1-y x)+x+x^2; b=1/(1-x); f[list_]:=Select[list, #>0&]; Map[f, CoefficientList[Series[b (1+a)/(1-a x/(1-x)) , {x, 0, nn}], {x, y}]]//Grid  (* Geoffrey Critzer, Nov 18 2012 *)

Crossrefs

Cf. A000079, A000078, A118898, A011787, A076791, A118390.

Sequence in context: A118884 A118890 A118869 * A098056 A097100 A002954

Adjacent sequences: A118894 A118895 A118896 * A118898 A118899 A118900

Keyword

nonn,tabf

Author

Emeric Deutsch, May 04 2006

Status

approved