A275046 Number of binary strings with n zeros and n ones avoiding the substrings 10101101 and 1110101.
1, 2, 6, 20, 70, 245, 874, 3164, 11577, 42694, 158431, 590873, 2212797, 8315535, 31341163, 118423810, 448455754, 1701534151, 6467049185, 24617030774, 93834205107, 358116770601, 1368283768753, 5233261657558, 20034371696497, 76763164565117, 294357181436313, 1129575035419485
Offset: 0
Keywords
Examples
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. 0123456789 ---------- 1 0001110101 contains w2 at offset 3 2 0010101101 contains w1 at offset 2 3 0011101010 contains w2 at offset 2 4 0101011010 contains w1 at offset 1 5 0111010100 contains w2 at offset 1 6 1010110100 contains w1 at offset 0 7 1110101000 contains w2 at offset 0 Therefore a(5) = 252 - 7 = 245.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 253 terms from Gheorghe Coserea)
- Stephen Melczer and Bruno Salvy, Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables, arXiv:1605.00402 [cs.SC], 2016.
- R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, arXiv:math/0512548 [math.CO], 2007.
Programs
-
Mathematica
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 *) -
PARI
r1 = (1+x^2*y^3+x^2*y^4+x^3*y^4-x^3*y^6); r2 = (1-x-y+x^2*y^3-x^3*y^3-x^4*y^4-x^3*y^6+x^4*y^6); diag(expr, N=22, var=variables(expr)) = { my(a = vector(N)); for (k = 1, #var, expr = taylor(expr, var[#var - k + 1], N)); for (n = 1, N, a[n] = expr; for (k = 1, #var, a[n] = polcoeff(a[n], n-1))); return(a); }; diag(r1/r2, 28) 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; \\ test: y = Ser(diag(r1/r2, 100)); 0 == subst(F, 'y, y) -
PARI
x='x; y='y; t='t; seq(N) = { my(Fx = substvec(F, [x, y], [t, x]), y0 = 1 + O('t^N), y1=0, n=1); while (n++, y1 = y0 - subst(Fx, 'x, y0)/subst(deriv(Fx, 'x), 'x, y0); if (y1 == y0, break()); y0 = y1); Vec(y0); }; seq(28) \\ Gheorghe Coserea, Jul 18 2018
Formula
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).
From Gheorghe Coserea, Jul 17 2018: (Start)
G.f. y=A(x) satisfies:
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.
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'.
(End)
Comments