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
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
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).
Comments