login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
Number of weakly increasing words of length n+1 with n+2 letters such that no up-step is by 1, see example. - Joerg Arndt, Jun 10 2013
Row sums of the Riordan array in A239101. - Philippe Deléham, Mar 25 2014
LINKS
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.
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
EXAMPLE
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)
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 *)
PROG
(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
CROSSREFS
Sequence in context: A279482 A018029 A099483 * A190255 A218250 A267799
KEYWORD
nonn,nice
AUTHOR
Elisabetta Grazzini, May 02 2013
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 16:34 EDT 2024. Contains 371254 sequences. (Running on oeis4.)