A303696 -id:A303696 - cp's OEIS frontend

A005251 a(0) = 0, a(1) = a(2) = a(3) = 1; thereafter, a(n) = a(n-1) + a(n-2) + a(n-4).

0, 1, 1, 1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405, 97229, 170625, 299426, 525456, 922111, 1618192, 2839729, 4983377, 8745217, 15346786, 26931732, 47261895, 82938844, 145547525, 255418101, 448227521

Offset: 0

N. J. A. Sloane and R. K. Guy

a(n+3) is the number of n-bit sequences that avoid 010. Example: For n=4 the 12 sequences are all 4-bit sequences except 0100, 0101, 0010, 1010. - David Callan, Mar 25 2004
a(n+2) is the number of compositions (ordered partitions) of n where no two adjacent parts are != 1, see example. - Joerg Arndt, Jan 26 2013
a(n+1) is the number of compositions of n avoiding the part 2. - Joerg Arndt, Jul 13 2014
Number of different positive braids with n crossings of 3 strands.
This is a_2(n) in the Doroslovacki reference. Note that there is a typo in the paper in the formula for a_2(n): the upper bound in the inner sum should be "n-i" not "i-1". - Max Alekseyev, Jun 26 2007
a(n) is the number of peakless Motzkin paths of length n-1 with no UHH...HD's starting at level > 0 (here n > 0 and U=(1,1), H=(1,0), D=(1,-1)). Example: a(5)=7 because from all 8 peakless Motzkin paths of length 5 (see A004148) only UUHDD does not qualify. - Emeric Deutsch, Sep 13 2004
Equals the INVERT transform of (1, 0, 1, 1, 1, ...); equivalent to a(n) = a(n-1) + a(n-3) + a(n-4) + ... - Gary W. Adamson, Apr 27 2009
a(n) is the number of length n-1 words on {0,1} such that each string of 1's is followed by a string of at least two 0's. For example, a(5) = 4 because we have: 0000, 0100, 1000, and 1100. - Geoffrey Critzer, Aug 09 2013
a(n+1) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 0; 0, 1, 1; 1, 0, 0] or [1, 0, 1; 1, 1, 0; 0, 1, 0] or [1, 1, 0; 0, 0, 1; 1, 0, 1] or [1, 0, 1; 1, 0, 0; 0, 1, 1]. - R. J. Mathar, Feb 03 2014
For n >= 2, a(n) is the number of (n-2)-length binary words with no isolated zeros. - Milan Janjic, Mar 07 2015
Apart from the first three terms, the total number of bargraphs of semiperimeter n of height at most two for n >= 2 starts 1, 2, 4, 7, 12, ... - Arnold Knopfmacher, Nov 02 2016
Number of DD-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are DD-equivalent iff the positions of pattern DD are identical in these paths. - Sergey Kirgizov, Apr 08 2018
From Gus Wiseman, Nov 25 2019: (Start)
For n > 0, also the number of subsets of {1, ..., n - 3} such that if x and x + 2 are both in the subset, then so is x + 1. For example, the a(3) = 1 through a(7) = 12 subsets are:
  {}  {}   {}     {}       {}
      {1}  {1}    {1}      {1}
           {2}    {2}      {2}
           {1,2}  {3}      {3}
                  {1,2}    {4}
                  {2,3}    {1,2}
                  {1,2,3}  {1,4}
                           {2,3}
                           {3,4}
                           {1,2,3}
                           {2,3,4}
                           {1,2,3,4}
(End)
The two-dimensional version, which counts sets of pairs where, if two pairs are separated by graph-distance 2, then the intermediate pair or pairs are also in the set, is A329871. - Gus Wiseman, Nov 30 2019
a(n+1) is the number of ways to tile a strip of length n with squares, dominoes, and tetrominoes, where the first tile cannot be a domino. - Greg Dresden and Myanna Nash, Aug 18 2020

			From _Joerg Arndt_, Jan 26 2013: (Start)
The a(5+2) = 12 compositions of 5 where no two adjacent parts are != 1 are
  [ 1]  [ 1 1 1 1 1 ]
  [ 2]  [ 1 1 1 2 ]
  [ 3]  [ 1 1 2 1 ]
  [ 4]  [ 1 1 3 ]
  [ 5]  [ 1 2 1 1 ]
  [ 6]  [ 1 3 1 ]
  [ 7]  [ 1 4 ]
  [ 8]  [ 2 1 1 1 ]
  [ 9]  [ 2 1 2 ]
  [10]  [ 3 1 1 ]
  [11]  [ 4 1 ]
  [12]  [ 5 ]
(End)
G.f. = x + x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 12*x^7 + 21*x^8 + 37*x^9 + ...

S. Burckel, Efficient methods for three strand braids (submitted). [Apparently unpublished]
P. Chinn and S. Heubach, "Compositions of n with no occurrence of k", Congressus Numeratium, 2002, v. 162, pp. 33-51.
John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 205.
R. K. Guy, "Anyone for Twopins?" in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..500
Kassie Archer, Ethan Borsh, Jensen Bridges, Christina Graves, and Millie Jeske, Cyclic permutations avoiding patterns in both one-line and cycle forms, arXiv:2312.05145 [math.CO], 2023. See p. 2.
Andrei Asinowski and Cyril Banderier, On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.
R. Austin and R. K. Guy, Binary sequences without isolated ones, Fib. Quart., 16 (1978), 84-86.
J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
Jean-Luc Baril, Sergey Kirgizov and Armen Petrossian, Enumeration of Łukasiewicz paths modulo some patterns, arXiv:1804.01293 [math.CO], 2018.
N. Bergeron, S. Mykytiuk, F. Sottile and S. van Willigenburg, Shifted quasisymmetric functions and the Hopf algebra of peak functions, arXiv:math/9904105 [math.CO], 1999.
D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 11.
A. Blecher, C. Brennan, A. Knopfmacher and H. Prodinger, The height and width of bargraphs, Discrete Applied Math. 180, (2015), 36-44.
A. Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972, p. 112.
P. Chinn and S. Heubach, Integer Sequences Related to Compositions without 2's, J. Integer Seqs., Vol. 6, 2003.
James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Properties of a Ternary Infinite Word, arXiv:2206.01776 [cs.DM], 2022.
James Currie, Pascal Ochem, Narad Rampersad, and Jeffrey Shallit, Complement Avoidance in Binary Words, arXiv:2209.09598 [math.CO], 2022.
J. Demetrovics et al., On the number of unions in a family of sets, in Combinatorial Math., Proc. 3rd Internat. Conf., Annals NY Acad. Sci., 555 (1989), 150-158.
R. Doroslovacki, Binary sequences without 011...110 (k-1 1's) for fixed k, Mat. Vesnik 46 (1994), no. 3-4, 93-98.
Nazim Fatès, Biswanath Sethi, and Sukanta Das, On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View, in Reversibility and Universality, Andrew Adamatzky, editor, Emergence, Complexity and Computation Vol. 30. Springer, 2018.
Steven Finch, Cantor-solus and Cantor-multus distributions, arXiv:2003.09458 [math.CO], 2020.
R. L. Graham and N. J. A. Sloane, Anti-Hadamard matrices, Linear Alg. Applic., 62 (1984), 113-137.
R. K. Guy, Letter to N. J. A. Sloane, Feb 1986
R. K. Guy, Anyone for Twopins?, in D. A. Klarner, editor, The Mathematical Gardner. Prindle, Weber and Schmidt, Boston, 1981, pp. 2-15. [Annotated scanned copy, with permission]
V. C. Harris and C. C. Styles, A generalization of Fibonacci numbers, Fib. Quart. 2 (1964) 277-289, sequence u(n,1,2).
V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 98
Milan Janjic, Binomial Coefficients and Enumeration of Restricted Words, Journal of Integer Sequences, 2016, Vol 19, #16.7.3.
Vedran Krcadinac, A new generalization of the golden ratio, Fibonacci Quart. 44 (2006), no. 4, 335-340.
Erkko Lehtonen and Tamás Waldhauser, Associative spectra of graph algebras II. Satisfaction of bracketing identities, spectrum dichotomy, arXiv:2011.08522 [math.CO], 2020.
J. J. Madden, A generating function for the distribution of runs in binary words, arXiv:1707.04351 [math.CO], 2017, Theorem 1.1, r=2, k=0.
T. Mansour and M. Shattuck, Counting Peaks and Valleys in a Partition of a Set, J. Int. Seq. 13 (2010), 10.6.8, Lemma 2.1, k=2, 0 peaks.
Denis Neiter and Amsha Proag, Links Between Sums Over Paths in Bernoulli's Triangles and the Fibonacci Numbers, Journal of Integer Sequences, Vol. 19 (2016), Article 16.8.3.
Nicolas Ollinger and Jeffrey Shallit, The Repetition Threshold for Rote Sequences, arXiv:2406.17867 [math.CO], 2024.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
A. G. Shannon, Some recurrence relations for binary sequence matrices, NNTDM 17 (2011), 4, 913.
Bojan Vučković and Miodrag Živković, Row Space Cardinalities Above 2^(n - 2) + 2^(n - 3), ResearchGate, January 2017, p. 3.
Index entries for linear recurrences with constant coefficients, signature (2,-1,1).

Cf. A001608, A004148, A005314, A006498, A011973, A049864, A049853, A078065, A118891, A173022, A176971, A178470, A261041, A303696, A329871, A384153.
Bisection of Padovan sequence A000931.
Partial sums of A005314 shifted 3 times to the right, if we assume A005314(0) = 1.
Compositions without adjacent equal parts are A003242.
Compositions without isolated parts are A114901.
Row sums of A097230(n-2) for n>1.

a005251 n = a005251_list !! n
a005251_list = 0 : 1 : 1 : 1 : zipWith (+) a005251_list
   (drop 2 $ zipWith (+) a005251_list (tail a005251_list))
-- Reinhard Zumkeller, Dec 28 2011

I:=[0,1,1,1]; [n le 4 select I[n] else Self(n-1)+Self(n-2)+Self(n-4): n in [1..45]]; // Vincenzo Librandi, Nov 30 2018

R:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( x*(1-x)/(1-2*x + x^2 - x^3) )); // Marius A. Burtea, Oct 24 2019

A005251 := proc(n) option remember; if n <= 2 then n elif n = 3 then 4 else 2*A005251(n - 1) - A005251(n - 2) + A005251(n - 3); fi; end;
A005251:=(-1+z)/(-1+2*z-z**2+z**3); # Simon Plouffe in his 1992 dissertation
a := n -> `if`(n<=1, n, hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4)):
seq(simplify(a(n)), n=0..36); # Peter Luschny, Apr 08 2018

LinearRecurrence[{2,-1,1},{0,1,1},40]  (* Harvey P. Dale, May 05 2011 *)
a[ n_]:= If[n<0, SeriesCoefficient[ -x(1-x)/(1 -x + 2x^2 -x^3), {x, 0, -n}], SeriesCoefficient[ x(1-x)/(1 -2x +x^2 -x^3), {x, 0, n}]] (* Michael Somos, Dec 13 2013 *)
a[0] = 1; a[1] = a[2] = 0; a[n_] := a[n] = a[n-2] + a[n-3]; Table[a[2 n-1], {n, 1, 20}] (* Rigoberto Florez, Oct 15 2019 *)
Table[If[n==0,0,Length[DeleteCases[Subsets[Range[n-3]],{_,x_,y_,_}/;x+2==y]]],{n,0,10}] (* Gus Wiseman, Nov 25 2019 *)

Vec((1-x)/(1-2*x+x^2-x^3)+O(x^99)) /* Charles R Greathouse IV, Nov 20 2012 */

{a(n) = if( n<0, polcoeff( -x*(1-x)/(1 -x +2*x^2 -x^3) + x*O(x^-n), -n), polcoeff( x*(1-x)/(1 -2*x +x^2 -x^3) + x*O(x^n), n))} /* Michael Somos, Dec 13 2013 */

[sum( binomial(n-j-1, 2*j) for j in (0..floor((n-1)/3)) ) for n in (0..50)] # G. C. Greubel, Apr 13 2022

a(n) = 2*a(n-1) - a(n-2) + a(n-3).
G.f.: z*(1-z)/(1 - 2*z + z^2 - z^3). - Emeric Deutsch, Sep 13 2004
23*a_n = 3*P_{2n+1} + 7*P_{2n} - 2*P_{2n-1}, where P_n are the Perrin numbers, A001608. - Don Knuth, Dec 09 2008
a(n+1) = Sum_{k=0..n} binomial(n-k, 2k). - Richard L. Ollerton, May 12 2004
From Henry Bottomley, Feb 21 2001: (Start)
a(n) = (Sum_{ja(n) = A005314(n) - A005314(n-1).
a(n) = A049853(n-1) - a(n-1).
a(n) = A005314(n) - a(n-2). (End)
Conjecture: a(n+1) + |A078065(n)| = 2*A005314(n+1). - Creighton Dement, Dec 21 2004
a(n+2) has g.f. (F_3(-x) + F_2(-x))/(F_4(-x) + F_3(-x)) = 1/(-x+1/(-x+1/(-x+1))) where F_n(x) is the n-th Fibonacci polynomial; see A011973. - Qiaochu Yuan (qchu(AT)mit.edu), Feb 19 2009
a(n) = A173022(2^(n-2) - 1) for n > 1. - Reinhard Zumkeller, Feb 07 2010
BINOMIAL transform of A176971 is a(n+1). - Michael Somos, Dec 13 2013
a(n) = hypergeom([(2-n)/3, 1-n/3, (1-n)/3], [1/2, -n+1], 27/4) for n > 1. - Peter Luschny, Apr 08 2018
G.f.: z/(1-z-z^3-z^4-z^5-...) for the compositions of n-1 avoiding 2. The g.f. for the number of compositions of n avoiding the part k is 1/(1-z-...-z^(k-1) - z^(k+1)-...). - Gregory L. Simay, Sep 09 2018
If p,q,r are the three solutions to x^3 = 2x^2 - x + 1, then a(n) = (p-1)*p^n/((p-q)*(p-r)) + (q-1)*q^n/((q-p)*(q-r)) + (r-1)*r^n/((r-p)*(r-q)). - Greg Dresden and AnXing Yang, Aug 12 2025

A128588 Expansion of g.f. x*(1+x+x^2)/(1-x-x^2).

Original entry on oeis.org

1, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338

Offset: 1

Gary W. Adamson, Mar 11 2007

Previous name was: A007318 * A128587.
a(n)/a(n-1) tends to phi, 1.618... = A001622.
Regardless of initial two terms, any linearly recurring sequence with signature (1,1) will yield an a(n)/a(n+1) ratio tending to phi (the Golden Ratio). - Harvey P. Dale, Mar 29 2017
Apart from the initial term, double the Fibonacci numbers. O.g.f.: x*(1+x+x^2)/(1-x-x^2). a(n) gives the number of binary strings of length n-1 avoiding the substrings 000 and 111. a(n) also gives the number of binary strings of length n-1 avoiding the substrings 010 and 101. - Peter Bala, Jan 22 2008
Row lengths of triangle A232642. - Reinhard Zumkeller, May 14 2015
a(n) is the number of binary strings of length n-1 avoiding the substrings 000 and 111. - Allan C. Wechsler, Feb 13 2025

Reinhard Zumkeller, Table of n, a(n) for n = 1..2500
J.-P. Allouche and T. Johnson, Narayana's Cows and Delayed Morphisms.
Andrei Asinowski and Cyril Banderier, On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020) Leibniz International Proceedings in Informatics (LIPIcs) Vol. 159, 1:1-1:16.
Elena Barcucci, Antonio Bernini, Stefano Bilotta, and Renzo Pinzani, Non-overlapping matrices, arXiv:1601.07723 [cs.DM], 2016. See 1st column of Table 2 p. 11.
Jean-Luc Baril, Nathanaël Hassler, Sergey Kirgizov, and José L. Ramírez, Grand zigzag knight's paths, arXiv:2402.04851 [math.CO], 2024.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, page 52.
B. Winterfjord, Binary strings and substring avoidance.
Index entries for linear recurrences with constant coefficients, signature (1,1).

Cf. A000045, A001622, A128587, A128586, A007318.
Cf. A006355, A055389.
Cf. A014217, A069403, A153819.
Cf. A232642, A242593.
Cf. A038754, A068922.
Main diagonal of A303696.

Concatenation([1], List([2..40], n-> 2*Fibonacci(n))); # G. C. Greubel, Jul 10 2019

a128588 n = a128588_list !! (n-1)
a128588_list = 1 : cows where
                   cows = 2 : 4 : zipWith (+) cows (tail cows)
-- Reinhard Zumkeller, May 14 2015

[1] cat [2*Fibonacci(n): n in [2..40]]; // G. C. Greubel, Jul 10 2019

a:= n-> `if`(n<2, n, 2*(<<0|1>, <1|1>>^n)[1,2]):
seq(a(n), n=1..50);  # Alois P. Heinz, Apr 28 2018

nn=40; a=(1-x^3)/(1-x); b=x*(1-x^2)/(1-x); CoefficientList[Series[a^2 /(1-b^2), {x,0,nn}], x]  (* Geoffrey Critzer, Sep 01 2012 *)
LinearRecurrence[{1,1}, {1,2,4}, 40] (* Harvey P. Dale, Mar 29 2017 *)
Join[{1}, 2*Fibonacci[Range[2,40]]] (* G. C. Greubel, Jul 10 2019 *)

{a(n) = if( n<2, n==1, 2 * fibonacci(n))}; /* Michael Somos, Jul 18 2015 */

[1]+[2*fibonacci(n) for n in (2..40)] # G. C. Greubel, Jul 10 2019

G.f.: x*(1+x+x^2)/(1-x-x^2).
Binomial transform of A128587; a(n+2) = a(n+1) + a(n), n>3.
a(n) = A068922(n-1), n>2. - R. J. Mathar, Jun 14 2008
For n > 1: a(n+1) = a(n) + if a(n) odd then max{a(n),a(n-1)} else min{a(n),a(n-1)}, see also A038754. - Reinhard Zumkeller, Oct 19 2015
E.g.f.: 4*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5) - x. - Stefano Spezia, Feb 19 2023

New name from Joerg Arndt, Feb 16 2024

A164146 Number of binary strings of length n with equal numbers of 010 and 101 substrings.

Original entry on oeis.org

1, 2, 4, 6, 12, 20, 38, 66, 124, 224, 424, 788, 1502, 2838, 5438, 10386, 20004, 38508, 74516, 144264, 280216, 544736, 1061292, 2069596, 4042254, 7902294, 15466842, 30297422, 59404174, 116558270, 228876426, 449713994, 884199348, 1739434972, 3423770240, 6742430340

Offset: 0

R. H. Hardin, Aug 11 2009

			a(5) = 20: 00000, 00001, 00011, 00101, 00110, 00111, 01011, 01100, 01110, 01111, 10000, 10001, 10011, 10100, 11000, 11001, 11010, 11100, 11110, 11111. - _Alois P. Heinz_, Apr 16 2015

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 501 terms from R. H. Hardin)
Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, arXiv preprint arXiv:1112.6207, 2011. See subpages for rigorous derivations of g.f., recurrence, asymptotics for this sequence. [From _N. J. A. Sloane_, Apr 07 2012]

Cf. A118430, A255386, A260505, A260668, A260697, A303430.
Column k=1 of A303696.
Column k=0 of A307796.

CoefficientList[Series[-(4*x^4-2*x^3-2*x^2+x+Sqrt[(2*x-1)*(2*x^2-1)*(2*x^2-2*x+1)]) / ((x-1)*(2*x-1)*(2*x^2-1)),{x,0,33}],x] (* Stefano Spezia, Jul 31 2025 *)

G.f.: -(4*x^4-2*x^3-2*x^2+x+sqrt((2*x-1)*(2*x^2-1)*(2*x^2-2*x+1))) / ((x-1)*(2*x-1)*(2*x^2-1)). - Alois P. Heinz, Apr 16 2015

A307796 Number T(n,k) of binary words of length n such that k is the difference of numbers of occurrences of subword 101 and subword 010; triangle T(n,k), n>=0, -floor(n/3)<=k<=floor(n/3), read by rows.

Original entry on oeis.org

1, 2, 4, 1, 6, 1, 2, 12, 2, 6, 20, 6, 1, 12, 38, 12, 1, 3, 28, 66, 28, 3, 10, 56, 124, 56, 10, 1, 24, 119, 224, 119, 24, 1, 4, 60, 236, 424, 236, 60, 4, 15, 134, 481, 788, 481, 134, 15, 1, 42, 304, 950, 1502, 950, 304, 42, 1, 5, 114, 656, 1902, 2838, 1902, 656, 114, 5

Offset: 0

Alois P. Heinz, Apr 29 2019

			T(8,2) = 10: 01101101, 10101101, 10110101, 10110110, 10110111, 10111011, 10111101, 11011011, 11011101, 11101101.
T(8,-2) = 10: 00010010, 00100010, 00100100, 01000010, 01000100, 01001000, 01001001, 01001010, 01010010, 10010010.
T(9,3)  = 1: 101101101.
T(9,-3) = 1: 010010010.
Triangle T(n,k) begins:
  :                      1                   ;
  :                      2                   ;
  :                      4                   ;
  :                1,    6,   1              ;
  :                2,   12,   2              ;
  :                6,   20,   6              ;
  :           1,  12,   38,  12,   1         ;
  :           3,  28,   66,  28,   3         ;
  :          10,  56,  124,  56,  10         ;
  :      1,  24, 119,  224, 119,  24,  1     ;
  :      4,  60, 236,  424, 236,  60,  4     ;
  :     15, 134, 481,  788, 481, 134, 15     ;
  :  1, 42, 304, 950, 1502, 950, 304, 42, 1  ;

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

Columns k=0-2 give: A164146, A284449, A286209.
Row sums give A000079.
T(3n-4,n-2) gives A000217 for n >= 3.
Cf. A002264, A057711, A303696.

b:= proc(n, t, h) option remember; `if`(n=0, 1, expand(
      `if`(h=3, 1/x, 1)*b(n-1, [1, 3, 1][t], 2)+
      `if`(t=3, x, 1)*b(n-1, 2, [1, 3, 1][h])))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=-iquo(n, 3)..iquo(n, 3)))(b(n, 1$2)):
seq(T(n), n=0..15);

b[n_, t_, h_] := b[n, t, h] = If[n == 0, 1, Expand[If[h == 3, 1/x, 1]* b[n-1, {1, 3, 1}[[t]], 2] + If[t == 3, x, 1]*b[n-1, 2, {1, 3, 1}[[h]]]]];
T[n_] := Table[Coefficient[#, x, i], {i, -Quotient[n, 3], Quotient[n, 3]}]& @ b[n, 1, 1];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 08 2019, after Alois P. Heinz *)

T(n,k) = T(n,-k).

Sum_{k = -floor(n/3)..floor(n/3)} T(n,k) * k^2/2 = A057711(n-2) for n > 1.

A303430 Number of binary words of length n with exactly twice as many occurrences of subword 101 as occurrences of subword 010.

Original entry on oeis.org

1, 2, 4, 6, 10, 17, 28, 49, 84, 148, 263, 472, 858, 1568, 2893, 5372, 10034, 18824, 35428, 66898, 126683, 240483, 457334, 870956, 1660850, 3171112, 6061596, 11597587, 22206775, 42551339, 81591256, 156553245, 300565760, 577360360, 1109601934, 2133499936

Offset: 0

Alois P. Heinz, Apr 23 2018

nonn

			a(0) = 1: the empty word.
a(1) = 2: 0, 1.
a(2) = 4: 00, 01, 10, 11.
a(3) = 6: 000, 001, 011, 100, 110, 111.
a(4) = 10: 0000, 0001, 0011, 0110, 0111, 1000, 1001, 1100, 1110, 1111.
a(5) = 17: 00000, 00001, 00011, 00110, 00111, 01100, 01110, 01111, 10000, 10001, 10011, 10101, 11000, 11001, 11100, 11110, 11111.

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

Cf. A005251, A164146, A260668, A284449.

Column k=2 of A303696.

b:= proc(n, t, h, c) option remember; `if`(abs(c)>2*n, 0,
     `if`(n=0, 1, b(n-1, [1, 3, 1][t], 2, c-`if`(h=3, 2, 0))
                + b(n-1, 2, [1, 3, 1][h], c+`if`(t=3, 1, 0))))
    end:
a:= n-> b(n, 1$2, 0):
seq(a(n), n=0..50);

A306293 Number of binary words of length n such that in every prefix and in every suffix the number of 0's and the number of 1's differ by at most two.

Original entry on oeis.org

1, 2, 4, 6, 10, 16, 26, 42, 70, 110, 194, 288, 550, 754, 1586, 1974, 4630, 5168, 13634, 13530, 40390, 35422, 120146, 92736, 358390, 242786, 1071074, 635622, 3205030, 1664080, 9598706, 4356618, 28763350, 11405774, 86224514, 29860704, 258542470, 78176338

Offset: 0

Alois P. Heinz, Feb 04 2019

All terms with index n > 0 are even.

			a(3) = 6: 001, 010, 011, 100, 101, 110.
a(4) = 10: 0010, 0011, 0100, 0101, 0110, 1001, 1010, 1011, 1100, 1101.
a(5) = 16: 00101, 00110, 01001, 01010, 01011, 01100, 01101, 01110, 10001, 10010, 10011, 10100, 10101, 10110, 11001, 11010.
a(6) = 26: 001010, 001011, 001100, 001101, 001110, 010010, 010011, 010100, 010101, 010110, 011001, 011010, 011100, 100011, 100101, 100110, 101001, 101010, 101011, 101100, 101101, 110001, 110010, 110011, 110100, 110101.
a(7) = 42: 0010101, 0010110, 0011001, ..., 1100110, 1101001, 1101010.
a(8) = 70: 00101010, ..., 00111100, ..., 11000011, ..., 11010101.

Alois P. Heinz, Table of n, a(n) for n = 0..4193
Index entries for linear recurrences with constant coefficients, signature (0,8,0,-22,0,23,0,-6).

Bisections of a(n+2)/2 give: A007689 (even part), A001906(n+2) (odd part).

Cf. A068911, A128588, A303696, A306306, A306315.

a:= n-> `if`(n<2, 1+n, 2*(<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>,
        <-6|23|-22|8>>^iquo(n-2, 2, 'r').[<<2, 5, 13, 35>>,
        <<3, 8, 21, 55>>][1+r])[1, 1]):
seq(a(n), n=0..50);

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

a(n) <= A306306(n).

A317783 Number of equivalence classes of binary words of length n for the set of subwords {010, 101}.

Original entry on oeis.org

1, 1, 1, 3, 7, 13, 23, 41, 75, 139, 257, 473, 869, 1597, 2937, 5403, 9939, 18281, 33623, 61841, 113743, 209207, 384793, 707745, 1301745, 2394281, 4403769, 8099795, 14897847, 27401413, 50399055, 92698313, 170498779, 313596147, 576793241, 1060888169, 1951277557

Offset: 0

Alois P. Heinz, Aug 06 2018

Two binary words of the same length are equivalent with respect to a given subword set if they have equal sets of occurrences for each single subword.

All terms are odd.

			a(6) = 23: [|], [|0], [0|], [|1], [|2], [|3], [1|], [2|], [3|], [|03], [03|], [1|0], [0|1], [2|1], [1|2], [3|2], [2|3], [02|1], [1|02], [13|2], [2|13], [13|02], [02|13].  Here [13|2] describes the class whose members have occurrences of 010 at positions 1 and 3 and an occurrence of 101 at position 2 and no other occurrences of both subwords: 001010.  [|] describes the class that avoids both subwords and has 26 members for n=6, in general 2*A000045(n+1) (for n>0).

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

Cf. A000045, A128588, A164146, A303696, A317669, A317779.

a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
          <0|0|0|0|1>, <1|0|1|-1|2>>^n.<<1, 1, 1, 3, 7>>)[1$2]:
seq(a(n), n=0..45);
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [1$3, 3, 7][n+1],
      2*a(n-1) -a(n-2) +a(n-3) +a(n-5))
    end:
seq(a(n), n=0..45);

LinearRecurrence[{2, -1, 1, 0, 1}, {1, 1, 1, 3, 7}, 40] (* Jean-François Alcover, Apr 30 2022 *)

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

a(n) = 2*a(n-1) -a(n-2) +a(n-3) +a(n-5) for n >= 5.

A307795 Number of binary words of length n with three times as many occurrences of subword 101 as occurrences of subword 010.

Original entry on oeis.org

1, 2, 4, 6, 10, 16, 26, 42, 70, 116, 196, 332, 572, 996, 1758, 3134, 5650, 10276, 18836, 34720, 64310, 119582, 223066, 417028, 780876, 1463800, 2746304, 5155556, 9682418, 18189458, 34178904, 64236714, 120749592, 227018306, 426886298, 802872340, 1510325700

Offset: 0

Alois P. Heinz, Apr 29 2019

nonn

			a(8) = 70: 00000000, 00000001, 00000011, 00000110, 00000111, 00001100, 00001110, 00001111, 00011000, 00011001, 00011100, 00011110, 00011111, 00110000, 00110001, 00110011, 00111000, 00111001, 00111100, 00111110, 00111111, 01100000, 01100001, 01100011, 01100110, 01100111, 01110000, 01110001, 01110011, 01111000, 01111001, 01111100, 01111110, 01111111, 10000000, 10000001, 10000011, 10000110, 10000111, 10001100, 10001110, 10001111, 10011000, 10011001, 10011100, 10011110, 10011111, 10101101, 10110101, 11000000, 11000001, 11000011, 11000110, 11000111, 11001100, 11001110, 11001111, 11100000, 11100001, 11100011, 11100110, 11100111, 11110000, 11110001, 11110011, 11111000, 11111001, 11111100, 11111110, 11111111.

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

Column k=3 of A303696.

b:= proc(n, t, h, c) option remember; `if`(abs(c)>3*n, 0,
     `if`(n=0, 1, b(n-1, [1, 3, 1][t], 2, c-`if`(h=3, 3, 0))
                + b(n-1, 2, [1, 3, 1][h], c+`if`(t=3, 1, 0))))
    end:
a:= n-> b(n, 1$2, 0):
seq(a(n), n=0..50);

Showing 1-8 of 8 results.

cp's OEIS Frontend

A005251 a(0) = 0, a(1) = a(2) = a(3) = 1; thereafter, a(n) = a(n-1) + a(n-2) + a(n-4).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

A128588 Expansion of g.f. x*(1+x+x^2)/(1-x-x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A164146 Number of binary strings of length n with equal numbers of 010 and 101 substrings.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A307796 Number T(n,k) of binary words of length n such that k is the difference of numbers of occurrences of subword 101 and subword 010; triangle T(n,k), n>=0, -floor(n/3)<=k<=floor(n/3), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A303430 Number of binary words of length n with exactly twice as many occurrences of subword 101 as occurrences of subword 010.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A306293 Number of binary words of length n such that in every prefix and in every suffix the number of 0's and the number of 1's differ by at most two.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A317783 Number of equivalence classes of binary words of length n for the set of subwords {010, 101}.

Views