OFFSET
0,4
COMMENTS
T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms.
LINKS
Alois P. Heinz, Rows n = 0..500, flattened
FORMULA
Sum_{k>0} k*T(n,k) = A228612(n).
EXAMPLE
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]
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 *)
CROSSREFS
KEYWORD
AUTHOR
Alois P. Heinz, Dec 18 2013
STATUS
approved