cp's OEIS Frontend

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.

%I A225034 #75 May 24 2022 16:23:38
%S A225034 1,3,7,18,48,131,363,1017,2873,8169,23349,67024,193086,557949,1616501,
%T A225034 4694034,13657896,39809649,116218701,339762942,994553160,2914608177,
%U A225034 8550424953,25107964077,73793368593,217057617567,638936722403,1882096946232,5547613247418,16361808691243
%N 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.
%C A225034 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
%C A225034 Row sums of the Riordan array in A239101. - _Philippe Deléham_, Mar 25 2014
%H A225034 Vincenzo Librandi, <a href="/A225034/b225034.txt">Table of n, a(n) for n = 0..1000</a>
%H A225034 Kassie Archer and Christina Graves, <a href="https://arxiv.org/abs/2205.09686">A new statistic on Dyck paths for counting 3-dimensional Catalan words</a>, arXiv:2205.09686 [math.CO], 2022.
%H A225034 Stefano Bilotta, Elisabetta Grazzini, and Elisa Pergola, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Grazzini/grazzini2.html">Counting Binary Words Avoiding Alternating Patterns</a>, J. Integer Seq., 16 (2013), Article 13.4.8.
%H A225034 Donatella Merlini and Massimo Nocentini, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Merlini/merlini5.html">Algebraic Generating Functions for Languages Avoiding Riordan Patterns</a>, Journal of Integer Sequences, Vol. 21 (2018), Article 18.1.3.
%F A225034 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))).
%F A225034 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
%F A225034 a(n) ~ 4*3^(n-1/2) / sqrt(Pi*n). - _Vaclav Kotesovec_, Mar 10 2014
%F A225034 a(n) = Sum_{k = 0..n} A239101(n,k). - _Philippe Deléham_, Mar 25 2014
%e A225034 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:
%e A225034 01: 11,
%e A225034 02: 1001,
%e A225034 03: 011,
%e A225034 04: 0110,
%e A225034 05: 110,
%e A225034 06: 1100,
%e A225034 07: 0011,
%e A225034 therefore a(2)=7.
%e A225034 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:
%e A225034 01: 111,
%e A225034 02: 1110,
%e A225034 03: 0111,
%e A225034 04: 11100,
%e A225034 05: 11001,
%e A225034 06: 10011,
%e A225034 07: 00111,
%e A225034 08: 01110,
%e A225034 09: 111000,
%e A225034 10: 110001,
%e A225034 11: 100011,
%e A225034 12: 000111,
%e A225034 13: 011100,
%e A225034 14: 001110,
%e A225034 15: 010011,
%e A225034 16: 011001,
%e A225034 17: 100110,
%e A225034 18: 110010,
%e A225034 therefore a(3)=18.
%e A225034 From _Joerg Arndt_, Jun 10 2013: (Start)
%e A225034 There are a(3)=18 weakly increasing length-4 words of 5 letters (0,1,2,3,4) with no up-step by 1:
%e A225034 01:  [ 0 0 0 ]
%e A225034 02:  [ 0 0 2 ]
%e A225034 03:  [ 0 0 3 ]
%e A225034 04:  [ 0 0 4 ]
%e A225034 05:  [ 0 2 2 ]
%e A225034 06:  [ 0 2 4 ]
%e A225034 07:  [ 0 3 3 ]
%e A225034 08:  [ 0 4 4 ]
%e A225034 09:  [ 1 1 1 ]
%e A225034 10:  [ 1 1 3 ]
%e A225034 11:  [ 1 1 4 ]
%e A225034 12:  [ 1 3 3 ]
%e A225034 13:  [ 1 4 4 ]
%e A225034 14:  [ 2 2 2 ]
%e A225034 15:  [ 2 2 4 ]
%e A225034 16:  [ 2 4 4 ]
%e A225034 17:  [ 3 3 3 ]
%e A225034 18:  [ 4 4 4 ]
%e A225034 (End)
%t A225034 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 *)
%o A225034 (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
%Y A225034 Cf. A005251, A239101.
%K A225034 nonn,nice
%O A225034 0,2
%A A225034 _Elisabetta Grazzini_, May 02 2013