|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms.
|
|
|
LINKS
|
|
|
|
FORMULA
|
|
|
|
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 ...
+-----+------------------------
: 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):
|
|
|
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.
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
