A118898 Number of binary sequences of length n containing exactly one subsequence 0000.
0, 0, 0, 0, 1, 2, 5, 12, 28, 62, 136, 294, 628, 1328, 2787, 5810, 12043, 24840, 51016, 104380, 212848, 432732, 877400, 1774672, 3581605, 7213746, 14502449, 29106100, 58323844, 116702074, 233199000, 465405058, 927744428, 1847359520, 3674769991
Offset: 0
Examples
a(6)=5 because we have 000010,000011,010000,100001 and 110000. G.f. = x^4 + 2*x^5 + 5*x^6 + 12*x^7 + 28*x^8 + 62*x^9 + ... - _Zerinvary Lajos_, Jun 02 2009
Links
- Michael De Vlieger, Table of n, a(n) for n = 0..3501
- Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.
- László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
- Index entries for linear recurrences with constant coefficients, signature (2,1,0,-1,-4,-3,-2,-1).
Crossrefs
Cf. A118897.
Programs
-
Maple
g:=z^4/(1-z-z^2-z^3-z^4)^2: gser:=series(g,z=0,40): seq(coeff(gser,z,n),n=0..37);
-
Mathematica
RecurrenceTable[{a[1]==0,a[2]==0,a[3]==0,a[4]==1,a[5]==2,a[6]==5, a[7]==12,a[8]==28,a[n]==2a[n-1]+a[n-2]-a[n-4]-4a[n-5]-3a[n-6]-2a[n-7]-a[n-8]},a,{n,9,50}] (* Bobby Milazzo, Aug 30 2009 *) LinearRecurrence[{2,1,0,-1,-4,-3,-2,-1},{0,0,0,0,1,2,5,12},50] (* Harvey P. Dale, Aug 01 2012 *) -
Sage
taylor( mul(x/(1-x-x^2-x^3-x^4)^2 for i in range(1,2)),x,0,31)# Zerinvary Lajos, Jun 02 2009
Formula
G.f.: z^4/(1-z-z^2-z^3-z^4)^2.
From Bobby Milazzo, Aug 30 2009: (Start)
a(1)=0,a(2)=0,a(3)=0,a(4)=1,a(5)=2,a(6)=5,a(7)=12,a(8)=28
a(n) = 2a(n-1)+a(n-2)-a(n-4)-4a(n-5)-3a(n-6)-2a(n-7)-a(n-8). (End)
Comments