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.
Original entry on oeis.org
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
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]
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.
-
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 *)
A118870
Number of binary sequences of length n with no subsequence 0101.
Original entry on oeis.org
1, 2, 4, 8, 15, 28, 53, 100, 188, 354, 667, 1256, 2365, 4454, 8388, 15796, 29747, 56020, 105497, 198672, 374140, 704582, 1326871, 2498768, 4705689, 8861770, 16688516, 31427872, 59185079, 111457548, 209897245, 395279228, 744391228, 1401840170
Offset: 0
a(5) = 28 because among the 32 (=2^5) binary sequences of length 5 only 01010, 01011, 00101 and 10101 contain the subsequence 0101.
-
[n le 4 select 2^(n-1) else 2*Self(n-1) -Self(n-2) +2*Self(n-3) -Self(n-4): n in [1..41]]; // G. C. Greubel, Jan 14 2022
-
a[0]:=1:a[1]:=2:a[2]:=4:a[3]:=8: for n from 4 to 35 do a[n]:=2*a[n-1]-a[n-2]+2*a[n-3]-a[n-4] od: seq(a[n], n=0..35);
-
CoefficientList[Series[(1+x^2)/(1-2x+x^2-2x^3+x^4),{x,0,40}],x] (* Geoffrey Critzer, Nov 28 2013 *)
-
@CachedFunction
def A112575(n): return sum((-1)^k*binomial(n-k, k)*lucas_number1(n-2*k, 2, -1) for k in (0..(n/2)))
def A118870(n): return A112575(n-1) + A112575(n+1)
[A118870(n) for n in (0..40)] # G. C. Greubel, Jan 14 2022
A332052
Number of binary words of length n with an even number of occurrences of the subword 0101.
Original entry on oeis.org
1, 2, 4, 8, 15, 28, 54, 104, 198, 380, 736, 1424, 2756, 5360, 10456, 20416, 39944, 78352, 153952, 302912, 596976, 1178304, 2328544, 4606848, 9124448, 18089920, 35895552, 71283968, 141664832, 281718528, 560561024, 1115994112, 2222846080, 4429381888, 8829667840
Offset: 0
a(4) = 15 = 2^4 - 1: 0101 is not counted.
a(5) = 28 = 2^5 - 4: 00101, 10101, 01010, 01011 are not counted.
-
a:= n-> 2^n-(<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>
, <0|0|0|0|1>, <4|-10|8|-6|4>>^n)[1, 5]:
seq(a(n), n=0..39);
-
LinearRecurrence[{4,-6,8,-10,4},{1,2,4,8,15},50] (* Harvey P. Dale, Mar 07 2024 *)
A118871
Number of binary sequences of length n containing exactly one subsequence 0101.
Original entry on oeis.org
0, 0, 0, 0, 1, 4, 10, 24, 57, 128, 278, 596, 1260, 2628, 5430, 11136, 22683, 45936, 92574, 185764, 371347, 739840, 1469580, 2911224, 5753048, 11343800, 22322444, 43845120, 85973013, 168314604, 329041842, 642385248, 1252552077, 2439430272, 4745767138, 9223159852
Offset: 0
a(5) = 4 because we have 01010, 01011, 00101 and 10101.
- G. C. Greubel, Table of n, a(n) for n = 0..1000
- Index entries for linear recurrences with constant coefficients, signature (4,-6,8,-11,8,-6,4,-1).
-
R:=PowerSeriesRing(Integers(), 40); [0,0,0,0] cat Coefficients(R!( x^4/(1 -2*x +x^2 -2*x^3 +x^4)^2 )); // G. C. Greubel, Jan 14 2022
-
g:=z^4/(1-2*z+z^2-2*z^3+z^4)^2: gser:=series(g,z=0,40): seq(coeff(gser, z, n), n=0..35);
-
LinearRecurrence[{4,-6,8,-11,8,-6,4,-1}, {0,0,0,0,1,4,10,24}, 40] (* G. C. Greubel, Jan 14 2022 *)
-
@CachedFunction
def A112575(n): return sum((-1)^k*binomial(n-k, k)*lucas_number1(n-2*k, 2, -1) for k in (0..(n/2)))
def A118871(n): return sum( A112575(j+1)*A112575(n-j-3) for j in (0..n-4) )
[A118871(n) for n in (0..40)] # G. C. Greubel, Jan 14 2022
Showing 1-4 of 4 results.
Comments