A143291 Triangle T(n,k), n>=2, 0<=k<=n-2, read by rows: numbers of binary words of length n containing at least one subword 10^{k}1 and no subwords 10^{i}1 with i<k.

1, 3, 1, 8, 2, 1, 19, 4, 2, 1, 43, 8, 3, 2, 1, 94, 15, 5, 3, 2, 1, 201, 27, 9, 4, 3, 2, 1, 423, 48, 15, 6, 4, 3, 2, 1, 880, 84, 24, 10, 5, 4, 3, 2, 1, 1815, 145, 38, 16, 7, 5, 4, 3, 2, 1, 3719, 248, 60, 24, 11, 6, 5, 4, 3, 2, 1, 7582, 421, 94, 35, 17, 8, 6, 5, 4, 3, 2, 1, 15397, 710, 146, 51, 25, 12, 7, 6, 5, 4, 3, 2, 1

Offset

2,2

Comments

T(n,k) = number of subset S of {1,2,...,n+1} such that |S| > 1 and min(S*) = k, where S* is the set {x(2)-x(1), x(3)-x(2), ..., x(h+1)-x(h)} when the elements of S are written as x(1) < x(2) < ... < x(h+1); if max(S*) is used in place of min(S*), the result is the array at A255874. - Clark Kimberling, Mar 08 2015

Links

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

Formula

G.f. of column k: x^(k+2) / ((x^(k+1)+x-1)*(x^(k+2)+x-1)).

Example

T (5,1) = 4, because there are 4 words of length 5 containing at least one subword 101 and no subword 11: 00101, 01010, 10100, 10101.
Triangle begins:
    1;
    3,  1;
    8,  2,  1;
   19,  4,  2, 1;
   43,  8,  3, 2, 1;
   94, 15,  5, 3, 2, 1;
  201, 27,  9, 4, 3, 2, 1;
  423, 48, 15, 6, 4, 3, 2, 1;

Maple

as:= proc (n, k) option remember;
       if k=0 then 2^n
     elif n<=k and n>=0 then n+1
     elif n>0 then as(n-1, k) +as(n-k-1, k)
     else as(n+1+k, k) -as(n+k, k)
       fi
     end:
T:= (n, k)-> as(n, k) -as(n, k+1):
seq(seq(T(n, k), k=0..n-2), n=2..15);

Mathematica

as[n_, k_] := as[n, k] = Which[ k == 0, 2^n, n <= k && n >= 0, n+1, n > 0, as[n-1, k] + as[n-k-1, k], True, as[n+1+k, k] - as[n+k, k] ]; t [n_, k_] := as[n, k] - as[n, k+1]; Table[Table[t[n, k], {k, 0, n-2}], {n, 2, 14}] // Flatten (* Jean-François Alcover, Dec 11 2013, translated from Maple *)

Crossrefs

Columns k=0-10 give: A008466, A143281, A143282, A143283, A143284, A143285, A143286, A143287, A143288, A143289, A143290.

Row sums are in A000295.

Cf. A141539.

Sequence in context: A182510 A112420 A010288 * A258043 A200064 A242072

Adjacent sequences: A143288 A143289 A143290 * A143292 A143293 A143294

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 04 2008

Status

approved