login
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.
14

%I #23 Jan 25 2018 11:06:43

%S 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,

%T 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,

%U 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

%N 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.

%C 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

%H Alois P. Heinz, <a href="/A143291/b143291.txt">Rows n = 2..142, flattened</a>

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

%e 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.

%e Triangle begins:

%e 1;

%e 3, 1;

%e 8, 2, 1;

%e 19, 4, 2, 1;

%e 43, 8, 3, 2, 1;

%e 94, 15, 5, 3, 2, 1;

%e 201, 27, 9, 4, 3, 2, 1;

%e 423, 48, 15, 6, 4, 3, 2, 1;

%p as:= proc (n, k) option remember;

%p if k=0 then 2^n

%p elif n<=k and n>=0 then n+1

%p elif n>0 then as(n-1, k) +as(n-k-1, k)

%p else as(n+1+k, k) -as(n+k, k)

%p fi

%p end:

%p T:= (n, k)-> as(n, k) -as(n, k+1):

%p seq(seq(T(n, k), k=0..n-2), n=2..15);

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

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

%Y Row sums are in A000295.

%Y Cf. A141539.

%K nonn,tabl

%O 2,2

%A _Alois P. Heinz_, Aug 04 2008