login
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.
15
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,4
COMMENTS
T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms.
LINKS
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
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.
Sequence in context: A199478 A134867 A102573 * A134033 A185051 A095026
KEYWORD
nonn,look,tabf,nice
AUTHOR
Alois P. Heinz, Dec 18 2013
STATUS
approved