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

1, 2, 4, 7, 1, 12, 4, 21, 10, 1, 37, 22, 5, 65, 47, 15, 1, 114, 98, 38, 6, 200, 199, 91, 21, 1, 351, 396, 210, 60, 7, 616, 777, 468, 158, 28, 1, 1081, 1508, 1014, 396, 89, 8, 1897, 2900, 2151, 952, 255, 36, 1, 3329, 5534, 4487, 2212, 687, 126, 9, 5842, 10492, 9229

Offset

0,2

Comments

Row n has ceiling(n/2) terms (n >= 1).

Sum of entries in row n is 2^n (A000079).

T(n,0) = A005251(n+3), T(n,1) = A118430(n).

Sum_{k=0..n-1} k*T(n,k) = (n-2)*2^(n-3) (A001787).

Links

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

Formula

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

Recurrence relation: T(n,k) = 2T(n-1,k) - T(n-2,k) + T(n-3,k) + T(n-2,k-1) - T(n-3,k-1) for n >= 3.

Example

T(6,2) = 5 because we have 010010, 010100, 010101, 001010 and 101010.
Triangle starts:
    1;
    2;
    4;
    7,   1;
   12,   4;
   21,  10,   1;
   37,  22,   5;
   65,  47,  15,  1;
  114,  98,  38,  6;
  200, 199,  91, 21, 1;
  351, 396, 210, 60, 7;
  ...

Maple

G:=(1+(1-t)*z^2)/(1-2*z+(1-t)*z^2-(1-t)*z^3): Gser:=simplify(series(G, z=0, 18)): P[0]:=1: for n from 1 to 16 do P[n]:=sort(coeff(Gser, z^n)) od: 1; for n from 1 to 16 do seq(coeff(P[n], t, j), j=0..ceil(n/2)-1) od; # yields sequence in triangular form
# Alternative:
b:= proc(n, t) option remember; `if`(n=0, 1,
      b(n-1, [1, 3, 1][t])+expand(b(n-1, 2)*`if`(t=3, x, 1)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Apr 02 2026

Mathematica

nn=15; Map[Select[#, #>0&]&, CoefficientList[Series[1/(1-2z-(u-1)z^3/(1-(u-1)z^2)), {z, 0, nn}], {z, u}]]//Grid (* Geoffrey Critzer, Dec 03 2013 *)

Crossrefs

Cf. A000079, A005251, A001787, A118430.

Alternating row sums give A393995.

Sequence in context: A395605 A089349 A118424 * A110317 A098073 A118390

Adjacent sequences: A118426 A118427 A118428 * A118430 A118431 A118432

Keyword

nonn,tabf

Author

Emeric Deutsch, Apr 27 2006

Status

approved