A209972 -id:A209972 - cp's OEIS frontend

A008937 a(n) = Sum_{k=0..n} T(k) where T(n) are the tribonacci numbers A000073.

0, 1, 2, 4, 8, 15, 28, 52, 96, 177, 326, 600, 1104, 2031, 3736, 6872, 12640, 23249, 42762, 78652, 144664, 266079, 489396, 900140, 1655616, 3045153, 5600910, 10301680, 18947744, 34850335, 64099760, 117897840, 216847936, 398845537, 733591314, 1349284788

Offset: 0

N. J. A. Sloane, Alejandro Teruel (teruel(AT)usb.ve)

a(n+1) is the number of n-bit sequences that avoid 1100. - David Callan, Jul 19 2004 [corrected by Kent E. Morrison, Jan 08 2019]. Also the number of n-bit sequences avoiding one of the patterns 1000, 0011, 1110, ... or any binary string of length 4 without overlap at beginning and end. Strings where it is not true are: 1111, 1010, 1001, ... and their bitwise complements. - Alois P. Heinz, Jan 09 2019
Row sums of Riordan array (1/(1-x), x(1+x+x^2)). - Paul Barry, Feb 16 2005
Diagonal sums of Riordan array (1/(1-x)^2, x(1+x)/(1-x)), A104698.
A shifted version of this sequence can be found in Eqs. (4) and (3) on p. 356 of Dunkel (1925) with r = 3. (Equation (3) follows equation (4) in the paper!) The whole paper is a study of the properties of this and other similar sequences indexed by the parameter r. For r = 2, we get a shifted version of A000071. For r = 4, we get a shifted version of A107066. For r = 5, we get a shifted version of A001949. For r = 6, we get a shifted version of A172316. See also the table in A172119. - Petros Hadjicostas, Jun 14 2019
Officially, to match A000073, this should start with a(0)=a(1)=0, a(2)=1. - N. J. A. Sloane, Sep 12 2020
Numbers with tribonacci representation that is a prefix of 100100100100... . - Jeffrey Shallit, Jul 10 2024

			G.f. = x + 2*x^2 + 4*x^3 + 8*x^4 + 15*x^5 + 28*x^6 + 52*x^7 + 96*x^8 + 177*x^9 + ... [edited by _Petros Hadjicostas_, Jun 12 2019]

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 41.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Isha Agarwal, Matvey Borodin, Aidan Duncan, Kaylee Ji, Tanya Khovanova, Shane Lee, Boyan Litchev, Anshul Rastogi, Garima Rastogi, and Andrew Zhao, From Unequal Chance to a Coin Game Dance: Variants of Penney's Game, arXiv:2006.13002 [math.HO], 2020.
Kassie Archer and Noel Bourne, Pattern avoidance in compositions and powers of permutations, arXiv:2505.05218 [math.CO], 2025. See pp. 6, 9.
Erik Bates, Blan Morrison, Mason Rogers, Arianna Serafini, and Anav Sood, A new combinatorial interpretation of partial sums of m-step Fibonacci numbers, arXiv:2503.11055 [math.CO], 2025. See p. 3.
Otto Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see pp. 356 and 369.
Jia Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv:2501.07463 [math.CO], 2025. See p. 7.
Thomas Langley, Jeffrey Liese, and Jeffrey Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), Article # 11.4.2.
William Verreault, MacMahon Partition Analysis: a discrete approach to broken stick problems, arXiv:2107.10318 [math.CO], 2021.
Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

Partial sums of A000073. Cf. A000213, A018921, A027084, A077908, A209972.
Row sums of A055216.
Column k = 1 of A140997 and second main diagonal of A140994.

a:=[0,1,1];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # G. C. Greubel, Sep 13 2019

a008937 n = a008937_list !! n
a008937_list = tail $ scanl1 (+) a000073_list
-- Reinhard Zumkeller, Apr 07 2012

[ n eq 1 select 0 else n eq 2 select 1 else n eq 3 select 2 else n eq 4 select 4 else 2*Self(n-1)-Self(n-4): n in [1..40] ]; // Vincenzo Librandi, Aug 21 2011

A008937 := proc(n) option remember; if n <= 3 then 2^n else 2*procname(n-1)-procname(n-4) fi; end;
a:= n-> (Matrix([[1,1,0,0], [1,0,1,0], [1,0,0,0], [1,0,0,1]])^n)[4,1]: seq(a(n), n=0..50); # Alois P. Heinz, Jul 24 2008

CoefficientList[Series[x/(1-2x+x^4), {x, 0, 40}], x]
Accumulate[LinearRecurrence[{1,1,1},{0,1,1},40]] (* Harvey P. Dale, Dec 04 2017 *)
LinearRecurrence[{2, 0, 0, -1},{0, 1, 2, 4},40] (* Ray Chandler, Mar 01 2024 *)

{a(n) = if( n<0, polcoeff( - x^3 / (1 - 2*x^3 + x^4) + x * O(x^-n), -n), polcoeff( x / (1 - 2*x + x^4) + x * O(x^n), n))}; /* Michael Somos, Aug 23 2014 */

a(n) = sum(j=0, n\2, sum(k=0, j, binomial(n-2*j,k+1)*binomial(j,k)*2^k)); \\ Michel Marcus, Sep 08 2017

def A008937_list(prec):
    P = PowerSeriesRing(ZZ, 'x', prec)
    x = P.gen().O(prec)
    return (x/(1-2*x+x^4)).list()
A008937_list(40) # G. C. Greubel, Sep 13 2019

a(n) = A018921(n-2) = A027084(n+1) + 1.
a(n) = (A000073(n+2) + A000073(n+4) - 1)/2.
From Mario Catalani (mario.catalani(AT)unito.it), Aug 09 2002: (Start)
G.f.: x/((1-x)*(1-x-x^2-x^3)).
a(n) = 2*a(n-1) - a(n-4), a(0) = 0, a(1) = 1, a(2) = 2, a(3) = 4. (End)
a(n) = 1 + a(n-1) + a(n-2) + a(n-3). E.g., a(11) = 1 + 600 + 326 + 177 = 1104. - Philippe LALLOUET (philip.lallouet(AT)orange.fr), Oct 29 2007
a(n) = term (4,1) in the 4 X 4 matrix [1,1,0,0; 1,0,1,0; 1,0,0,0; 1,0,0,1]^n. - Alois P. Heinz, Jul 24 2008
a(n) = -A077908(-n-3). - Alois P. Heinz, Jul 24 2008
a(n) = (A000213(n+2) - 1) / 2. - Reinhard Zumkeller, Apr 07 2012
a(n) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n-2j,k+1) *binomial(j,k)*2^k. - Tony Foster III, Sep 08 2017
a(n) = Sum_{k=0..floor(n/2)} (n-2*k)*hypergeom([-k,-n+2*k+1], [2], 2). - Peter Luschny, Nov 09 2017
a(n) = 2^(n-1)*hypergeom([1-n/4, 1/4-n/4, 3/4-n/4, 1/2-n/4], [1-n/3, 1/3-n/3, 2/3-n/3], 16/27) for n > 0. - Peter Luschny, Aug 20 2020
a(n-1) = T(n) + T(n-3) + T(n-6) + ... + T(2+((n-2) mod 3)), for n >= 4, where T is A000073(n+1). - Jeffrey Shallit, Dec 24 2020

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

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

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

Emeric Deutsch, May 03 2006

nonn

Column 0 of A118869 and column 10 of A209972.

			a(5) = 28 because among the 32 (=2^5) binary sequences of length 5 only 01010, 01011, 00101 and 10101 contain the subsequence 0101.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,-1,2,-1).

Cf. A000071, A000073, A005251, A112575, A118869, A209972, A332052.

[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

G.f.: (1 +x^2)/(1 -2*x +x^2 -2*x^3 +x^4).
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) for n>=4.
a(n) = A112575(n-1) + A112575(n+1). - R. J. Mathar, Dec 10 2011

A209888 Number of binary words of length n containing no subword 01101.

Original entry on oeis.org

1, 2, 4, 8, 16, 31, 60, 116, 225, 436, 845, 1637, 3172, 6146, 11909, 23075, 44711, 86633, 167863, 325256, 630226, 1221144, 2366125, 4584673, 8883398, 17212733, 33351899, 64623621, 125216632, 242623433, 470114310, 910907331, 1765000872, 3419917668, 6626533192

Offset: 0

Alois P. Heinz, Mar 14 2012

nonn

Notice that the proper suffix 01 of 01101 is also a prefix of 01101. If instead of 01101 subword 01011 is not allowed, we get A107066 with A107066(n) < a(n) for all n >= 8. Word 01101101 of length 8 is the smallest binary word having two or more copies of 01101.

			a(6) = 60 because among the 2^6 = 64 binary words of length 6 only 4, namely 001101, 011010, 011011 and 101101 contain the subword 01101.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2,-1).

Column 22 of A209972.
Column k=0 of A277751.
Cf. A107066, A317669.

a:= n-> (Matrix(5, (i, j)-> `if`(i=j-1, 1, `if`(i=5, [-1, 2, -1, 0, 2][j], 0)))^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);

CoefficientList[Series[(x + 1)*(x^2 - x + 1)/(x^5 - 2*x^4 + x^3 - 2*x + 1), {x, 0, 40}], x] (* Wesley Ivan Hurt, Apr 28 2017 *)
LinearRecurrence[{2,0,-1,2,-1},{1,2,4,8,16},40] (* Harvey P. Dale, Sep 17 2017 *)

G.f.: (x+1)*(x^2-x+1) / (x^5-2*x^4+x^3-2*x+1).

a(n) = 2^n if n<5, and a(n) = 2*(a(n-1)+a(n-4)) -a(n-3) -a(n-5) otherwise.

A210021 Number of binary words of length n containing no subword 11011.

Original entry on oeis.org

1, 2, 4, 8, 16, 31, 60, 116, 225, 437, 849, 1649, 3202, 6217, 12071, 23438, 45510, 88368, 171586, 333171, 646922, 1256136, 2439055, 4735945, 9195847, 17855697, 34670640, 67320433, 130716961, 253814826, 492835556, 956945224, 1858113016, 3607922263, 7005549684

Offset: 0

Alois P. Heinz, Mar 16 2012

			a(7) = 116 because among the 2^7 = 128 binary words of length 7 only 12, namely 0011011, 0110110, 0110111, 0111011, 1011011, 1101100, 1101101, 1101110, 1101111, 1110110, 1110111 and 1111011 contain the subword 11011.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Aashir Shukla et al., How many Binary Strings of length N contain within it the substring '11011'?, Mathematics Stack Exchange, circa Sep 09 2016.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1,1).

Column k=27 of A209972. Cf. A276785.

Column k=0 of A277678.

I:=[1,2,4,8,16]; [n le 5 select I[n] else 2*Self(n-1)-Self(n-3)+Self(n-4)+Self(n-5): n in [1..40]]; // Vincenzo Librandi, Oct 24 2016

a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>, <0|0|0|0|1>, <1|1|-1|0|2>>^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);

LinearRecurrence[{2, 0, -1, 1, 1}, {1, 2, 4, 8, 16}, 40] (* Vincenzo Librandi, Oct 24 2016 *)

G.f.: -(x^4+x^3+1)/(x^5+x^4-x^3+2*x-1).

a(n) = 2^n if n<5, and a(n) = 2*a(n-1) -a(n-3) +a(n-4) +a(n-5) otherwise.

A234005 Number of binary words of length n avoiding the subword given by the binary expansion of n.

Original entry on oeis.org

1, 1, 3, 5, 12, 21, 33, 81, 177, 338, 667, 1178, 2031, 4105, 6872, 20569, 42744, 84457, 167863, 315633, 590081, 1325032, 2366125, 4408350, 8146016, 16474904, 30266484, 67320433, 112454976, 230099960, 417825921, 1333610936, 2714234540, 5411487988, 10800172911

Offset: 0

Alois P. Heinz, Dec 18 2013

nonn

			a(0) = 1: the empty word.
a(1) = 1: 0.
a(2) = 3: 00, 01, 11.
a(3) = 5: 000, 001, 010, 100, 101.
a(4) = 12: 0000, 0001, 0010, 0011, 0101, 0110, 0111, 1010, 1011, 1101, 1110, 1111.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Main diagonal of A209972.

Column k=0 of A233940.

A210003 Number of binary words of length n containing no subword 10001.

Original entry on oeis.org

1, 2, 4, 8, 16, 31, 60, 116, 224, 433, 837, 1618, 3128, 6047, 11690, 22599, 43688, 84457, 163271, 315633, 610177, 1179585, 2280356, 4408350, 8522156, 16474904, 31849037, 61570080, 119026354, 230099960, 444825787, 859930531, 1662404788, 3213735970, 6212746113

Offset: 0

Alois P. Heinz, Mar 16 2012

Each of the subwords 10001, 10011, 10111, 11001, 11101 and their binary complements give the same sequence.

			a(7) = 116 because among the 2^7 = 128 binary words of length 7 only 12, namely 0010001, 0100010, 0100011, 0110001, 1000100, 1000101, 1000110, 1000111, 1010001, 1100010, 1100011 and 1110001 contain the subword 10001.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1,1).

Columns k=17, 19, 23, 25, 29 of A209972.

a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>, <0|0|0|0|1>, <1|-1|0|0|2>>^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);

LinearRecurrence[{2,0,0,-1,1},{1,2,4,8,16},40] (* Harvey P. Dale, Oct 05 2015 *)

G.f.: -(x^4+1)/(x^5-x^4+2*x-1).

a(n) = 2^n if n<5, and a(n) = 2*a(n-1) -a(n-4) +a(n-5) otherwise.

A210031 Number of binary words of length n containing no subword 100001.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 63, 124, 244, 480, 944, 1857, 3653, 7186, 14136, 27808, 54703, 107610, 211687, 416424, 819176, 1611457, 3170007, 6235937, 12267137, 24131522, 47470763, 93382976, 183700022, 361368844, 710873303, 1398407365, 2750902517, 5411487988

Offset: 0

Alois P. Heinz, Mar 16 2012

Each of the subwords 100001, 100011, 100101, 100111, 101001, 101011, 101111, 110001, 110101, 111001, 111101 and their binary complements give the same sequence.

			a(8) = 244 because among the 2^8 = 256 binary words of length 8 only 12, namely 00100001, 01000010, 01000011, 01100001, 10000100, 10000101, 10000110, 10000111, 10100001, 11000010, 11000011, 11100001 contain the subword 100001.

Indranil Ghosh, Table of n, a(n) for n = 0..3396 (terms 0..1000 from Alois P. Heinz)
Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,-1,1).

Columns k=33, 35, 37, 39, 41, 43, 47, 49, 53, 57, 61 of A209972.

a:= n-> (Matrix(6, (i, j)-> `if`(i=j-1, 1, `if`(i=6, [1, -1, 0, 0, 0, 2][j], 0)))^n. <<1, 2, 4, 8, 16, 32>>)[1, 1]: seq(a(n), n=0..40);

G.f.: -(x^5+1)/(x^6-x^5+2*x-1).

a(n) = 2^n if n<6, and a(n) = 2*a(n-1) -a(n-5) +a(n-6) otherwise.

A365746 Table read by antidiagonals upward: T(n,k) is the number of binary strings of length k with the property that every substring of length A070939(n) is lexicographically earlier than the binary expansion of n; n, k >= 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 2, 4, 5, 2, 1, 0, 1, 2, 4, 4, 8, 2, 1, 0, 1, 2, 4, 5, 4, 13, 2, 1, 0, 1, 2, 4, 6, 7, 4, 21, 2, 1, 0, 1, 2, 4, 7, 10, 11, 4, 34, 2, 1, 0, 1, 2, 4, 8, 13, 16, 16, 4, 55, 2, 1, 0, 1, 2, 4, 8, 8, 24

Offset: 0

Peter Kagey, Sep 17 2023

			Table begins:
 n\k | 0  1  2  3   4   5   6   7    8    9   10   11
-----+----------------------------------------------------
   0 | 1, 0, 0, 0,  0,  0,  0,  0,   0,   0,   0,   0, ...
   1 | 1, 1, 1, 1,  1,  1,  1,  1,   1,   1,   1,   1, ...
   2 | 1, 2, 2, 2,  2,  2,  2,  2,   2,   2,   2,   2, ...
   3 | 1, 2, 3, 5,  8, 13, 21, 34,  55,  89, 144, 233, ...
   4 | 1, 2, 4, 4,  4,  4,  4,  4,   4,   4,   4,   4, ...
   5 | 1, 2, 4, 5,  7, 11, 16, 23,  34,  50,  73, 107, ...
   6 | 1, 2, 4, 6, 10, 16, 26, 42,  68, 110, 178, 288, ...
   7 | 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, ...
   8 | 1, 2, 4, 8,  8,  8,  8,  8,   8,   8,   8,   8, ...
   9 | 1, 2, 4, 8,  9, 11, 15, 23,  32,  43,  58,  81, ...
For (n,k) = (3,4), we see that T(3,4) = 8 because there are 8 binary strings of length k = 4 where all length A070939(3) = 2 substrings are lexicographically earlier than "11" (the binary expansion of n = 3): 0000, 0001, 0010, 0100, 0101, 1000, 1001, and 1010.

Cf. A030190, A070939, A209972.

Cf. A000045 (row 3), A164316 (row 5), A128588 (row 6), A000073 (row 7).

A365746Row[s_,
  numberOfTerms_] := (digits = If[s == 0, 1, Ceiling[Log[2, s + 1]]];
  m = 2^(digits - 1);
  transferMatrix =
   If[s == 0, {{0}},
    Table[If[(Ceiling[i/2] ==
         j) || ((i <= s - m) && (Ceiling[i/2] == j - m/2)), 1, 0], {i,
       1, m}, {j, 1, m}]];
  sequence =
   Table[2^k, {k, 0, digits - 1}] ~Join~
    Table[MatrixPower[transferMatrix, k] // Total // Total, {k, 1,
      numberOfTerms - digits}];
  Take[sequence, numberOfTerms])

G.f. for row n = 0: 1;
G.f. for row n = 1: 1/(1 - x);
G.f. for row n = 2: (1 + x)/(1 - x);
G.f. for row n = 3: (1 + x)/(1 - x - x^2);
G.f. for row n = 4: (1 + x + 2x^2)/(1 - x);
G.f. for row n = 5: (1 + x + 2x^2)/(1 - x - x^3);
G.f. for row n = 6: (1 + x + x^2)/(1 - x - x^2);
G.f. for row n = 7: (1 + x + x^2)/(1 - x - x^2 - x^3);
G.f. for row n = 8: (1 + x + 2 x^2 + 4 x^3)/(1 - x);
G.f. for row n = 9: (1 + x + 2x^2 + 4x^3)/(1 - x - x^4).

cp's OEIS Frontend

A008937 a(n) = Sum_{k=0..n} T(k) where T(n) are the tribonacci numbers A000073.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

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

A118870 Number of binary sequences of length n with no subsequence 0101.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

A209888 Number of binary words of length n containing no subword 01101.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A210021 Number of binary words of length n containing no subword 11011.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A234005 Number of binary words of length n avoiding the subword given by the binary expansion of n.

Views

Author

Keywords

Examples

Links

Crossrefs

A210003 Number of binary words of length n containing no subword 10001.

Views

Author