A234005 -id:A234005 - cp's OEIS frontend

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

Alois P. Heinz, Dec 18 2013

T(n,k) is defined for n,k >= 0. The triangle contains only the positive terms.

			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]

Alois P. Heinz, Rows n = 0..500, flattened

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.

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

(* 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 *)

Sum_{k>0} k*T(n,k) = A228612(n).

A209972 Number of binary words of length n avoiding the subword given by the binary expansion of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 3, 4, 1, 1, 1, 2, 4, 5, 5, 1, 1, 1, 2, 4, 7, 8, 6, 1, 1, 1, 2, 4, 7, 12, 13, 7, 1, 1, 1, 2, 4, 7, 12, 20, 21, 8, 1, 1, 1, 2, 4, 7, 12, 21, 33, 34, 9, 1, 1, 1, 2, 4, 8, 13, 20, 37, 54, 55, 10, 1, 1, 1, 2, 4, 8, 15, 24, 33, 65, 88, 89, 11, 1, 1

Offset: 0

Alois P. Heinz, Mar 16 2012

			Square array begins:
  1,  1,  1,   1,   1,   1,   1,   1,   1, ...
  1,  1,  2,   2,   2,   2,   2,   2,   2, ...
  1,  1,  3,   3,   4,   4,   4,   4,   4, ...
  1,  1,  4,   5,   7,   7,   7,   7,   8, ...
  1,  1,  5,   8,  12,  12,  12,  13,  15, ...
  1,  1,  6,  13,  20,  21,  20,  24,  28, ...
  1,  1,  7,  21,  33,  37,  33,  44,  52, ...
  1,  1,  8,  34,  54,  65,  54,  81,  96, ...
  1,  1,  9,  55,  88, 114,  88, 149, 177, ...

Alois P. Heinz, Antidiagonals n = 0..150, flattened

Columns give: 0, 1: A000012, 2: A001477(n+1), 3: A000045(n+2), 4, 6: A000071(n+3), 5: A005251(n+3), 7: A000073(n+3), 8, 12, 14: A008937(n+1), 9, 11, 13: A049864(n+2), 10: A118870, 15: A000078(n+4), 16, 20, 24, 26, 28, 30: A107066, 17, 19, 23, 25, 29: A210003, 18, 22: A209888, 21: A152718(n+3), 27: A210021, 31: A001591(n+5), 32: A001949(n+5), 33, 35, 37, 39, 41, 43, 47, 49, 53, 57, 61: A210031.

Main diagonal equals A234005 or column k=0 of A233940.

A[n_, k_] := Module[{bb, cnt = 0}, Do[bb = PadLeft[IntegerDigits[j, 2], n]; If[SequencePosition[bb, IntegerDigits[k, 2], 1]=={}, cnt++], {j, 0, 2^n-1 }]; cnt];
Table[A[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Nov 01 2021 *)

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula