login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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

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

Adjacent sequences: A233937 A233938 A233939 * A233941 A233942 A233943

KEYWORD

nonn,look,tabf,nice

AUTHOR

Alois P. Heinz, Dec 18 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 2 05:15 EST 2023. Contains 359997 sequences. (Running on oeis4.)