|
| |
|
|
A275046
|
|
Number of binary strings with n zeros and n ones avoiding the substrings 10101101 and 1110101.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
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
|
|
|
LINKS
|
|
|
|
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).
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)
|
|
|
EXAMPLE
|
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.
|
|
|
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 *)
|
|
|
PROG
|
(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)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
