A335247 a(n) is the number of binary (0,1) sequences of length n that have at least two ones in each window of eight consecutive symbols.

1, 2, 4, 8, 16, 32, 64, 127, 247, 487, 961, 1897, 3745, 7393, 14593, 28801, 56833, 112156, 221341, 436825, 862094, 1701380, 3357739, 6626611, 13077820, 25809478, 50935832, 100523529, 198386490, 391522260, 772682018, 1524913233, 3009466064, 5939279536, 11721362180

Offset

0,2

Comments

Application: Not all electronic devices connected to the Internet of Things (IoT) have batteries or are connected to the power cable. These self-contained devices must rely on the harvesting of energy of the signals sent by a transmitter. A minimal number of 1's in transmitted sequences is required so as to carry sufficient energy within a prescribed time span. A binary sequence is said to obey the sliding-window (ell,t)-constraint if the number of 1's within any window of ell consecutive bits of that sequence is at least t, t<ell.

Links

Georg Fischer, Table of n, a(n) for n = 0..1000

Kees Immink and Kui Cai, Properties and constructions of energy-harvesting sliding-window constrained code, IEEE Communications Letters, May 2020.

Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,0,1,2,3,0,-3,-4,-3,0,0,-2,-3,0,0,3,3,0,0,0,1,0,0,0,-1).

Formula

G.f.: -(x^27+x^26-x^23-x^22-3*x^19-5*x^18-3*x^17+3*x^15+4*x^14+2*x^13 +3*x^11 +5*x^10+5*x^9+3*x^8-3*x^7-3*x^6-2*x^5-x^4-x^3-x^2-x-1) / (x^28-x^24-3*x^20 -3*x^19 +3*x^16 +2*x^15+3*x^12+4*x^11+3*x^10-3*x^8-2*x^7-x^6-x^4-x^3-x^2-x+1).

a(n) = a(n-1)+a(n-2)+a(n-3)+a(n-4)+a(n-6)+2*a(n-7)+3*a(n-8)-3*a(n-10) -4*a(n-11) -3*a(n-12) -2*a(n-15)-3*a(n-16)+3*a(n-19)+3*a(n-20)+a(n-24)-a(n-28), n>28.

a(n) ~ c*r^n where c = 1.07317641333 and r = 1.9735326811117101072.

Mathematica

CoefficientList[Series[-(x^27 +x^26 -x^23 -x^22 -3*x^19 -5*x^18 -3*x^17 +3*x^15 +4*x^14 +2*x^13 +3*x^11 +5*x^10 +5*x^9 +3*x^8 -3*x^7 -3*x^6 -2*x^5 -x^4 -x^3 -x^2 -x -1) / (x^28 -x^24 -3*x^20 -3*x^19 +3*x^16 +2*x^15 +3*x^12 +4*x^11 +3*x^10 -3*x^8 -2*x^7 -x^6 -x^4 -x^3 -x^2 -x +1), {x, 0, 100}], x] (* Georg Fischer, Oct 26 2020 *)
LinearRecurrence[{1, 1, 1, 1, 0, 1, 2, 3, 0, -3, -4, -3, 0, 0, -2, -3, 0, 0, 3, 3, 0, 0, 0, 1, 0, 0, 0, -1}, {1, 2, 4, 8, 16, 32, 64, 127, 247, 487, 961, 1897, 3745, 7393, 14593, 28801, 56833, 112156, 221341, 436825, 862094, 1701380, 3357739, 6626611, 13077820, 25809478, 50935832, 100523529}, 40] (* Harvey P. Dale, Feb 21 2022 *)

Crossrefs

Cf. A118647, A120118, A133523, A334251, A133551.

Sequence in context: A054044 A325741 A008859 * A145113 A062257 A208127

Adjacent sequences: A335244 A335245 A335246 * A335248 A335249 A335250

Keyword

nonn,easy

Author

Kees Immink, May 28 2020

Status

approved