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

1, 2, 4, 7, 1, 13, 2, 1, 24, 5, 2, 1, 44, 12, 5, 2, 1, 81, 26, 13, 5, 2, 1, 149, 56, 29, 14, 5, 2, 1, 274, 118, 65, 32, 15, 5, 2, 1, 504, 244, 143, 74, 35, 16, 5, 2, 1, 927, 499, 307, 169, 83, 38, 17, 5, 2, 1, 1705, 1010, 652, 374, 196, 92, 41, 18, 5, 2, 1, 3136, 2027, 1369, 819

Offset

0,2

Comments

Row n has n-1 terms (n >= 2). Sum of entries in row n is 2^n (A000079). T(n,0) = A000073(n+3) (the tribonacci numbers). T(n,1) = A073778(n-1). Sum_{k=0..n-1} k*T(n,k) = (n-2)*2^(n-3) (A001787).

Links

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

Formula

G.f.: G(t,z) = (1 + (1-t)z + (1-t)z^2)/(1 - (1+t)z - (1-t)z^2 - (1-t)z^3). Recurrence relation: T(n,k) = T(n-1,k) + T(n-2,k) + T(n-3,k) + T(n-1,k-1) - T(n-2,k-1) - T(n-3,k-1) for n >= 3.

Example

T(6,2) = 5 because we have 000010, 000011, 010000, 100001 and 110000.
Triangle starts:
   1;
   2;
   4;
   7,  1;
  13,  2,  1;
  24,  5,  2,  1;
  44, 12,  5,  2,  1;
  81, 26, 13,  5,  2,  1;

Maple

G:=(1+(1-t)*z+(1-t)*z^2)/(1-(1+t)*z-(1-t)*z^2-(1-t)*z^3): Gser:=simplify(series(G, z=0, 32)): P[0]:=1: for n from 1 to 13 do P[n]:=coeff(Gser, z^n) od: P[0]; P[1]; for n from 2 to 13 do seq(coeff(P[n], t, k), k=0..n-2) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n, t) option remember; `if`(n=0, 1,
      expand(b(n-1, min(2, t+1))*`if`(t>1, 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^2/(1-y x)+x; 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. A000073, A000079, A001787, A073778, A076791.

Sequence in context: A118429 A110317 A098073 * A247294 A202848 A202841

Adjacent sequences: A118387 A118388 A118389 * A118391 A118392 A118393

Keyword

nonn,tabf

Author

Emeric Deutsch, Apr 27 2006

Status

approved