A225034 a(n) is the number of binary words containing n 1's and at most n 0's that do not contain the substring 101.
1, 3, 7, 18, 48, 131, 363, 1017, 2873, 8169, 23349, 67024, 193086, 557949, 1616501, 4694034, 13657896, 39809649, 116218701, 339762942, 994553160, 2914608177, 8550424953, 25107964077, 73793368593, 217057617567, 638936722403, 1882096946232, 5547613247418, 16361808691243
Offset: 0
Examples
The binary words having two 1's (n=2) and at most two 0's and which do not have 101 as a substring are: 01: 11, 02: 1001, 03: 011, 04: 0110, 05: 110, 06: 1100, 07: 0011, therefore a(2)=7. The binary words having three 1's (n=3) and at most three 0's and which do not have 101 as a substring are: 01: 111, 02: 1110, 03: 0111, 04: 11100, 05: 11001, 06: 10011, 07: 00111, 08: 01110, 09: 111000, 10: 110001, 11: 100011, 12: 000111, 13: 011100, 14: 001110, 15: 010011, 16: 011001, 17: 100110, 18: 110010, therefore a(3)=18. From _Joerg Arndt_, Jun 10 2013: (Start) There are a(3)=18 weakly increasing length-4 words of 5 letters (0,1,2,3,4) with no up-step by 1: 01: [ 0 0 0 ] 02: [ 0 0 2 ] 03: [ 0 0 3 ] 04: [ 0 0 4 ] 05: [ 0 2 2 ] 06: [ 0 2 4 ] 07: [ 0 3 3 ] 08: [ 0 4 4 ] 09: [ 1 1 1 ] 10: [ 1 1 3 ] 11: [ 1 1 4 ] 12: [ 1 3 3 ] 13: [ 1 4 4 ] 14: [ 2 2 2 ] 15: [ 2 2 4 ] 16: [ 2 4 4 ] 17: [ 3 3 3 ] 18: [ 4 4 4 ] (End)
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..1000
- Kassie Archer and Christina Graves, A new statistic on Dyck paths for counting 3-dimensional Catalan words, arXiv:2205.09686 [math.CO], 2022.
- Stefano Bilotta, Elisabetta Grazzini, and Elisa Pergola, Counting Binary Words Avoiding Alternating Patterns, J. Integer Seq., 16 (2013), Article 13.4.8.
- Donatella Merlini and Massimo Nocentini, Algebraic Generating Functions for Languages Avoiding Riordan Patterns, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
Programs
-
Mathematica
CoefficientList[Series[2 (1 - x^2)/(3 x^2 - 4 x + 1 + Sqrt[(1 - x^2)^2 - 4 (x - x^2) (1 - x^2)]), {x, 0, 30}], x] (* Bruno Berselli, May 02 2013 *) -
PARI
x='x+O('x^66); Vec((2*(1-x^2))/(3*x^2-4*x+1+sqrt((1-x^2)^2-4*(x-x^2)*(1-x^2)))) \\ Joerg Arndt, May 02 2013
Formula
Theorem: G.f. = 2*(1-x^2)/(3*x^2-4*x+1+sqrt((1-x^2)^2-4*(x-x^2)*(1-x^2))).
Conjecture: (n+1)*a(n) - (2*n+3)*a(n-1) - 3*(n-2)*a(n-2) = 0 for n>1. - Bruno Berselli, May 02 2013
a(n) ~ 4*3^(n-1/2) / sqrt(Pi*n). - Vaclav Kotesovec, Mar 10 2014
a(n) = Sum_{k = 0..n} A239101(n,k). - Philippe Deléham, Mar 25 2014
Comments