A233940 Number T(n,k) of binary words of length n with exactly k (possibly overlapping) occurrences of the subword given by the binary expansion of n; triangle T(n,k), n>=0, read by rows.

1, 1, 1, 3, 1, 5, 2, 1, 12, 4, 21, 10, 1, 33, 30, 1, 81, 26, 13, 5, 2, 1, 177, 78, 1, 338, 156, 18, 667, 278, 68, 10, 1, 1178, 722, 142, 6, 2031, 1827, 237, 1, 4105, 3140, 862, 84, 1, 6872, 7800, 1672, 40, 20569, 5810, 3188, 1662, 829, 394, 181, 80, 35, 12, 5, 2, 1

Offset: 0

Author

Alois P. Heinz, Dec 18 2013

Keywords

• nonn
• look
• tabf
• nice

Comments

T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms.

Examples

			T(3,0) = 5: 000, 001, 010, 100, 101 (subword 11 is avoided).
T(3,1) = 2: 011, 110 (exactly one occurrence of 11).
T(3,2) = 1: 111 (two overlapping occurrences of 11).
Triangle T(n,k) begins:
: n\k :   0    1   2   3  4  5 ...
+-----+------------------------
:  0  :   1;                       [row  0 of A007318]
:  1  :   1,   1;                  [row  1 of A007318]
:  2  :   3,   1;                  [row  2 of A034867]
:  3  :   5,   2,  1;              [row  3 of A076791]
:  4  :  12,   4;                  [row  4 of A118424]
:  5  :  21,  10,  1;              [row  5 of A118429]
:  6  :  33,  30,  1;              [row  6 of A118424]
:  7  :  81,  26, 13,  5, 2, 1;    [row  7 of A118390]
:  8  : 177,  78,  1;              [row  8 of A118884]
:  9  : 338, 156, 18;              [row  9 of A118890]
: 10  : 667, 278, 68, 10, 1;       [row 10 of A118869]
		

Links

• Alois P. Heinz, Rows n = 0..500, flattened

Crossrefs

Columns k=0-10 give: A234005 (or main diagonal of A209972), A229905, A236231, A236232, A236233, A236234, A236235, A236236, A236237, A236238, A236239.

T(2^n-1,2^n-2n+1) = A045623(n-1) for n>0.

Last elements of rows give A229293.

Row sums give A000079.

Programs

Maple

F:= proc(n)
local w, L, s,b,s0,R,j,T,p,y,m,ymax;
w:= ListTools:-Reverse(convert(n,base,2));
L:= nops(w);
for s from 0 to L-1 do
  for b from 0 to 1 do
   s0:= [op(w[1..s]),b];
   if s0 = w then R[s,b]:= 1
   else R[s,b]:= 0
   fi;
   for j from min(nops(s0),L-1) by -1 to 0 do
      if s0[-j..-1] = w[1..j] then
        T[s,b]:= j;
        break
      fi
   od;
od;
od;
for s from L-1 by -1 to 0 do
  p[0,s,n]:= 1:
  for y from 1 to n do
     p[y,s,n]:= 0 od od;
for m from n-1 by -1 to 0 do
   for s from L-1 by -1 to 0 do
      for y from 0 to n do
        p[y,s,m]:= `if`(y>=R[s,0],1/2*p[y-R[s,0],T[s,0],m+1],0)
                  +
`if`(y>=R[s,1],1/2*p[y-R[s,1],T[s,1],m+1],0)
od od od:
ymax:= ListTools:-Search(0,[seq(p[y,0,0],y=0..n)])-2;
seq(2^n*p[y,0,0],y=0..ymax);
end proc:
F(0):= 1:
F(1):= (1,1):
for n from 0 to 30 do F(n) od; # Robert Israel, May 22 2015

Mathematica

(* This program is not convenient for a large number of rows *) count[word_List, subword_List] := Module[{cnt = 0, s1 = Sequence @@ subword, s2 = Sequence @@ Rest[subword]}, word //. {a___, s1, b___} :> (cnt++; {a, 2, s2, b}); cnt]; t[n_, k_] := Module[{subword, words}, subword = IntegerDigits[n, 2]; words = PadLeft[IntegerDigits[#, 2], n] & /@ Range[0, 2^n - 1]; Select[words, count[#, subword] == k &] // Length]; row[n_] := Reap[For[k = 0, True, k++, tnk = t[n, k]; If[tnk == 0, Break[], Sow[tnk]]]][[2, 1]]; Table[Print["n = ", n, " ", r = row[n]]; r, {n, 0, 15}] // Flatten (* Jean-François Alcover, Feb 13 2014 *)

Formula

Sum_{k>0} k*T(n,k) = A228612(n).