login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A275046 Number of binary strings with n zeros and n ones avoiding the substrings 10101101 and 1110101. 2

%I

%S 1,2,6,20,70,245,874,3164,11577,42694,158431,590873,2212797,8315535,

%T 31341163,118423810,448455754,1701534151,6467049185,24617030774,

%U 93834205107,358116770601,1368283768753,5233261657558,20034371696497,76763164565117,294357181436313,1129575035419485

%N Number of binary strings with n zeros and n ones avoiding the substrings 10101101 and 1110101.

%C Numerical experiment gives a(n) ~ k * r^n/sqrt(n*Pi) * (1 + O(1/n)), where k=1.06869393488382855... and r=3.91019320429177568...(the largest positive real root of P(x) = 4*x^20 - 20*x^19 + 8*x^18 + 75*x^17 - 233*x^16 + 368*x^15 - 286*x^14 + 154*x^13 + 66*x^12 - 203*x^11 + x^10 - 56*x^9 - 182*x^8 - 11*x^7 - 43*x^6 + 26*x^5 + 62*x^4 + 63*x^3 + 23*x^2 - 8*x - 4). - _Gheorghe Coserea_, Jun 28 2018

%H Gheorghe Coserea and Alois P. Heinz, <a href="/A275046/b275046.txt">Table of n, a(n) for n = 0..1000</a> (first 253 terms from Gheorghe Coserea)

%H Stephen Melczer and Bruno Salvy, <a href="http://arxiv.org/abs/1605.00402">Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables</a>, arXiv:1605.00402 [cs.SC], 2016.

%H R. Pemantle and M. C. Wilson, <a href="https://arxiv.org/abs/math/0512548">Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions</a>, arXiv:math/0512548 [math.CO], 2007.

%F a(n) = [x^n y^n] (1+x^2*y^3+x^2*y^4+x^3*y^4-x^3*y^6) / (1-x-y+x^2*y^3 -x^3*y^3-x^4*y^4-x^3*y^6+x^4*y^6).

%F From _Gheorghe Coserea_, Jul 17 2018: (Start)

%F G.f. y=A(x) satisfies:

%F 0 = (x + 1)*(4*x^20 + 8*x^19 - 23*x^18 - 63*x^17 - 62*x^16 - 26*x^15 + 43*x^14 + 11*x^13 + 182*x^12 + 56*x^11 - x^10 + 203*x^9 - 66*x^8 - 154*x^7 + 286*x^6 - 368*x^5 + 233*x^4 - 75*x^3 - 8*x^2 + 20*x - 4)*(y^4 - y^3) - (12*x^17 + 48*x^16 + 72*x^15 + 49*x^14 - 23*x^13 - 57*x^12 - 91*x^11 - 137*x^10 - 84*x^9 - 34*x^8 - 91*x^7 + 62*x^6 + 24*x^5 - 34*x^4 + 41*x^3 - 10*x^2 - 3*x - 3)*y^2 + (x^15 + 4*x^14 + 6*x^13 + 3*x^12 - 6*x^11 - 11*x^10 - 11*x^9 - 8*x^8 - 3*x^7 + 12*x^6 + 11*x^4 + 5*x^3 - 6*x^2 - 4)*y - x^4 + x + 1.

%F 0 = x*(x + 1)*(4*x^20 + 8*x^19 - 23*x^18 - 63*x^17 - 62*x^16 - 26*x^15 + 43*x^14 + 11*x^13 + 182*x^12 + 56*x^11 - x^10 + 203*x^9 - 66*x^8 - 154*x^7 + 286*x^6 - 368*x^5 + 233*x^4 - 75*x^3 - 8*x^2 + 20*x - 4)*(118272*x^52 + 831744*x^51 + 1055904*x^50 - 7689296*x^49 - 38498448*x^48 - 80707744*x^47 - 72043786*x^46 + 66740441*x^45 + 346144275*x^44 + 625268594*x^43 + 589350508*x^42 + 17945175*x^41 - 884101205*x^40 - 1544594497*x^39 - 1347124444*x^38 - 211988089*x^37 + 1025901619*x^36 + 1241901364*x^35 + 616097420*x^34 - 78145486*x^33 - 99242286*x^32 + 531374412*x^31 + 906579073*x^30 + 469457541*x^29 - 557671181*x^28 - 782936093*x^27 - 717539334*x^26 - 40136982*x^25 + 457839043*x^24 - 311428424*x^23 + 3826606*x^22 - 491844856*x^21 - 133463183*x^20 - 60176593*x^19 + 144471284*x^18 - 190012265*x^17 + 85787300*x^16 - 80535081*x^15 + 8793691*x^14 + 10578217*x^13 - 9656310*x^12 + 18022318*x^11 - 26135422*x^10 + 12930260*x^9 - 3354132*x^8 + 541884*x^7 - 9616*x^6 - 57280*x^5 - 9208*x^4 + 9112*x^3 - 1040*x^2 - 280*x + 16)*y'''' + 4*(2838528*x^73 + 28067328*x^72 + 73561152*x^71 - 226808640*x^70 - 1991541264*x^69 - 5248168208*x^68 - 3107619252*x^67 + 20424566388*x^66 + 73353344501*x^65 + 120803944377*x^64 + 68101961985*x^63 - 186797665046*x^62 - 613175796828*x^61 - 923231475195*x^60 - 665765362797*x^59 + 399661471464*x^58 + 1879241350220*x^57 + 2725977199294*x^56 + 1953611739558*x^55 - 308344618572*x^54 - 2604282130026*x^53 - 3293902915065*x^52 - 2023915430978*x^51 - 99057127476*x^50 + 858463211952*x^49 + 317189348208*x^48 - 644601194734*x^47 - 507510602088*x^46 + 879140815897*x^45 + 2316302607265*x^44 + 2466044252703*x^43 + 1507845363339*x^42 - 37352834097*x^41 - 866197857474*x^40 - 550136559577*x^39 - 371957632883*x^38 + 280554188916*x^37 - 169839318847*x^36 - 548085762481*x^35 - 394885238292*x^34 - 961508690348*x^33 - 558871954052*x^32 - 268597349319*x^31 - 396264718574*x^30 - 54570409485*x^29 - 29474141703*x^28 + 54798043451*x^27 - 225168685420*x^26 + 219869326332*x^25 - 211388212265*x^24 + 121755651738*x^23 - 44532380475*x^22 + 41810572525*x^21 - 13020873945*x^20 - 34502727399*x^19 + 51399098138*x^18 - 37480914194*x^17 + 16266551868*x^16 + 4802405683*x^15 - 11015782402*x^14 + 6973213149*x^13 - 2867107486*x^12 + 1145934309*x^11 - 396485541*x^10 + 91079094*x^9 - 20790910*x^8 + 9018972*x^7 - 2729266*x^6 + 15970*x^5 + 152280*x^4 - 23540*x^3 - 4624*x^2 + 804*x - 40)*y''' + 12*(5913600*x^72 + 58552320*x^71 + 162198720*x^70 - 399479776*x^69 - 4024065824*x^68 - 11894928752*x^67 - 13359252044*x^66 + 19743062838*x^65 + 106170302098*x^64 + 196850199947*x^63 + 139990047211*x^62 - 242428556815*x^61 - 914440223127*x^60 - 1404267023705*x^59 - 981820207169*x^58 + 692860011210*x^57 + 2881981766799*x^56 + 3780666319153*x^55 + 1931509675560*x^54 - 1789113064830*x^53 - 4353254267040*x^52 - 3421680202122*x^51 + 86944304476*x^50 + 2529905700017*x^49 + 1255075892612*x^48 - 2347804140484*x^47 - 4006195397861*x^46 - 1459374421865*x^45 + 3708726044890*x^44 + 6578458317742*x^43 + 3981711739329*x^42 - 545975266760*x^41 - 3735058603101*x^40 - 2830413868772*x^39 + 496621169935*x^38 + 2215361366242*x^37 + 2664777396382*x^36 - 126126929968*x^35 - 1185628295801*x^34 - 1766130985147*x^33 - 1321402227308*x^32 - 554605775048*x^31 - 314472036802*x^30 - 124742883035*x^29 - 779639894108*x^28 - 187973020632*x^27 - 436320637251*x^26 - 110965040480*x^25 + 89434870246*x^24 - 59962248938*x^23 + 40664295470*x^22 - 159086840234*x^21 + 87274292183*x^20 - 64615348620*x^19 - 3906157152*x^18 + 42872210460*x^17 - 39037582211*x^16 + 17857634133*x^15 - 4859881314*x^14 + 1719235532*x^13 - 1220377579*x^12 + 826395920*x^11 - 452538461*x^10 + 276451285*x^9 - 77896966*x^8 - 7819744*x^7 + 11091416*x^6 - 2392952*x^5 + 84092*x^4 + 78168*x^3 - 13628*x^2 + 204*x - 40)*y'' + 24*(4730880*x^71 + 47278080*x^70 + 138487680*x^69 - 273327872*x^68 - 3224196672*x^67 - 10522840368*x^66 - 15683954824*x^65 + 2837440368*x^64 + 66783160692*x^63 + 157076042559*x^62 + 176460709731*x^61 - 20753120619*x^60 - 468777180135*x^59 - 901436210799*x^58 - 814713584628*x^57 + 118253282806*x^56 + 1519823466913*x^55 + 2171886524422*x^54 + 984539467703*x^53 - 1380275010648*x^52 - 2578554053427*x^51 - 1051193690751*x^50 + 1862189159015*x^49 + 2884190942011*x^48 + 178354766658*x^47 - 3671225244807*x^46 - 4179646483007*x^45 - 425026505279*x^44 + 4749349227024*x^43 + 5804031914804*x^42 + 1249983354384*x^41 - 3642913361190*x^40 - 5112487295002*x^39 - 1641304278133*x^38 + 2938886288909*x^37 + 4069038198838*x^36 + 1830779914789*x^35 - 1798238310417*x^34 - 1495907299753*x^33 - 1094364204315*x^32 + 807417393365*x^31 - 72154916922*x^30 - 8536980308*x^29 - 794452219816*x^28 - 509673251372*x^27 + 190937602442*x^26 - 234838593532*x^25 + 251283672141*x^24 - 379193047029*x^23 + 161017205569*x^22 - 113347214785*x^21 + 45981090690*x^20 - 22904707029*x^19 - 8687260383*x^18 - 31879707878*x^17 + 37099647203*x^16 - 21102826093*x^15 + 7822806180*x^14 - 6568577261*x^13 + 4330232930*x^12 - 2387982620*x^11 + 1109490464*x^10 - 512581326*x^9 + 162799386*x^8 - 23098368*x^7 - 6139110*x^6 + 3208022*x^5 - 413396*x^4 - 87740*x^3 + 17676*x^2 - 2732*x + 520)*y'.

%F (End)

%e For n = 5 there are binomial(10,5) = 252 binary strings with 5 zeros and 5 ones; seven out of this 252 binary strings contain as substrings w1=10101101 or w2=1110101, i.e.

%e 0123456789

%e ----------

%e 1 0001110101 contains w2 at offset 3

%e 2 0010101101 contains w1 at offset 2

%e 3 0011101010 contains w2 at offset 2

%e 4 0101011010 contains w1 at offset 1

%e 5 0111010100 contains w2 at offset 1

%e 6 1010110100 contains w1 at offset 0

%e 7 1110101000 contains w2 at offset 0

%e Therefore a(5) = 252 - 7 = 245.

%t a[n_] := SeriesCoefficient[(1 + x^2 y^3 + x^2 y^4 + x^3 y^4 - x^3 y^6) / (1 - x - y + x^2 y^3 - x^3 y^3 - x^4 y^4 - x^3 y^6 + x^4 y^6), {x, 0, n}, {y, 0, n}]; Table[a[n], {n, 0, 27}] (* _Jean-Fran├žois Alcover_, Aug 20 2018 *)

%o (PARI)

%o r1 = (1+x^2*y^3+x^2*y^4+x^3*y^4-x^3*y^6);

%o r2 = (1-x-y+x^2*y^3-x^3*y^3-x^4*y^4-x^3*y^6+x^4*y^6);

%o diag(expr, N=22, var=variables(expr)) = {

%o my(a = vector(N));

%o for (k = 1, #var, expr = taylor(expr, var[#var - k + 1], N));

%o for (n = 1, N, a[n] = expr;

%o for (k = 1, #var, a[n] = polcoeff(a[n], n-1)));

%o return(a);

%o };

%o diag(r1/r2, 28)

%o F = (x + 1)*(4*x^20 + 8*x^19 - 23*x^18 - 63*x^17 - 62*x^16 - 26*x^15 + 43*x^14 + 11*x^13 + 182*x^12 + 56*x^11 - x^10 + 203*x^9 - 66*x^8 - 154*x^7 + 286*x^6 - 368*x^5 + 233*x^4 - 75*x^3 - 8*x^2 + 20*x - 4)*(y^4 - y^3) - (12*x^17 + 48*x^16 + 72*x^15 + 49*x^14 - 23*x^13 - 57*x^12 - 91*x^11 - 137*x^10 - 84*x^9 - 34*x^8 - 91*x^7 + 62*x^6 + 24*x^5 - 34*x^4 + 41*x^3 - 10*x^2 - 3*x - 3)*y^2 + (x^15 + 4*x^14 + 6*x^13 + 3*x^12 - 6*x^11 - 11*x^10 - 11*x^9 - 8*x^8 - 3*x^7 + 12*x^6 + 11*x^4 + 5*x^3 - 6*x^2 - 4)*y - x^4 + x + 1;

%o \\ test: y = Ser(diag(r1/r2, 100)); 0 == subst(F, 'y, y)

%o (PARI)

%o x='x; y='y; t='t;

%o seq(N) = {

%o my(Fx = substvec(F, [x, y], [t, x]), y0 = 1 + O('t^N), y1=0, n=1);

%o while (n++,

%o y1 = y0 - subst(Fx, 'x, y0)/subst(deriv(Fx, 'x), 'x, y0);

%o if (y1 == y0, break()); y0 = y1); Vec(y0);

%o };

%o seq(28)

%o \\ _Gheorghe Coserea_, Jul 18 2018

%Y Cf. A062257, A078678, A268545-A268555.

%Y Main diagonal of A273914.

%K nonn

%O 0,2

%A _Gheorghe Coserea_, Jul 17 2016

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 30 07:18 EDT 2021. Contains 346348 sequences. (Running on oeis4.)