A118647 -id:A118647 - cp's OEIS frontend

A212402 T(n,k)=Number of binary arrays of length n+2*k-1 with no more than k ones in any length 2k subsequence (=50% duty cycle).

3, 11, 5, 42, 19, 8, 163, 74, 33, 13, 638, 291, 132, 57, 21, 2510, 1150, 527, 236, 97, 34, 9908, 4558, 2104, 959, 421, 166, 55, 39203, 18100, 8402, 3872, 1747, 747, 285, 89, 155382, 71971, 33560, 15586, 7143, 3179, 1314, 489, 144, 616666, 286454, 134075

Offset: 1

R. H. Hardin May 14 2012

Table starts
..3..11...42...163...638...2510...9908...39203...155382...616666...2449868
..5..19...74...291..1150...4558..18100...71971...286454..1140954...4547020
..8..33..132...527..2104...8402..33560..134075...535728..2140910...8556568
.13..57..236...959..3872..15586..62632..251419..1008536..4043582..16206152
.21..97..421..1747..7143..29002.117290..473171..1905675..7665886..30810054
.34.166..747..3179.13185..54042.220054..892387..3609005.14567294..58714842
.55.285.1314..5769.24322.100736.413220.1685039..6844362.27724036.112072540
.89.489.2318.10425.44794.187696.776116.3183631.12990818.52815156.214150732

			Some solutions for n=3 k=4
..0....0....0....1....0....0....0....0....1....1....1....0....1....0....1....1
..1....0....1....1....0....0....1....0....1....1....0....1....1....1....0....0
..1....1....1....0....1....0....1....0....1....0....1....0....0....0....0....0
..0....1....1....0....1....0....1....0....0....1....0....1....1....0....1....0
..1....0....0....0....1....1....1....1....0....0....1....0....0....1....0....0
..0....0....0....1....0....1....0....0....0....0....0....0....0....0....1....0
..0....0....0....0....0....0....0....0....0....0....0....0....0....1....1....1
..0....1....1....0....0....1....0....1....0....1....1....0....1....0....0....1
..0....0....0....1....0....1....0....1....1....1....1....1....0....0....0....1
..1....0....0....1....1....0....0....0....1....1....0....1....0....0....1....1

R. H. Hardin, Table of n, a(n) for n = 1..4360

Column 1 is A000045(n+3)
Column 2 is A118647(n+3)
Column 3 is A133551(n+5)
Row 1 is A032443

A241964 T(n,k)=Number of length n+3 0..k arrays with no consecutive four elements summing to more than 2*k.

Original entry on oeis.org

11, 50, 19, 150, 124, 33, 355, 486, 311, 57, 721, 1421, 1597, 775, 97, 1316, 3437, 5778, 5211, 1895, 166, 2220, 7280, 16660, 23320, 16649, 4663, 285, 3525, 13980, 40978, 80132, 92037, 53553, 11518, 489, 5335, 24897, 89622, 228826, 376559, 365810

Offset: 1

R. H. Hardin, May 03 2014

Table starts
..11....50....150.....355.....721.....1316......2220......3525.......5335
..19...124....486....1421....3437.....7280.....13980.....24897......41767
..33...311...1597....5778...16660....40978.....89622....179079.....333091
..57...775...5211...23320...80132...228826....569874...1277427....2634115
..97..1895..16649...92037..376559..1247602...3536286...8889273...20314789
.166..4663..53553..365810.1782453..6853011..22111157..62336336..157897575
.285.11518.172980.1460409.8476317.37822419.138925925.439298830.1233421948

			Some solutions for n=4 k=4
..0....2....0....4....4....4....3....0....4....2....2....3....2....0....3....0
..3....2....4....2....3....0....3....0....1....3....2....1....4....2....4....0
..2....1....1....0....0....0....0....3....0....0....1....0....0....1....0....2
..0....3....0....1....0....2....2....1....2....1....2....0....2....3....0....1
..0....0....0....2....0....3....0....1....2....0....2....1....0....1....0....2
..1....0....0....1....0....0....3....1....4....1....2....3....3....1....2....0
..3....3....0....4....3....2....3....4....0....0....2....0....3....1....3....3

R. H. Hardin, Table of n, a(n) for n = 1..9999

Column 1 is A118647(n+3)
Column 2 is A212226
Column 3 is A212465
Row 1 is A212560(n+1)

Empirical for column k:
k=1: a(n) = a(n-1) +a(n-2) +a(n-4) -a(n-6)
k=2: [order 17]
k=3: [order 44]
k=4: [order 85]
Empirical for row n:
n=1: a(n) = (1/2)*n^4 + (7/3)*n^3 + 4*n^2 + (19/6)*n + 1
n=2: a(n) = (23/60)*n^5 + (9/4)*n^4 + (21/4)*n^3 + (25/4)*n^2 + (58/15)*n + 1
n=3: [polynomial of degree 6]
n=4: [polynomial of degree 7]
n=5: [polynomial of degree 8]
n=6: [polynomial of degree 9]
n=7: [polynomial of degree 10]

A120118 a(n) is the number of binary strings of length n such that no subsequence of length 5 or less contains 3 or more ones.

Original entry on oeis.org

1, 2, 4, 7, 11, 16, 26, 43, 71, 116, 186, 300, 487, 792, 1287, 2087, 3382, 5484, 8898, 14438, 23423, 37993, 61625, 99965, 162165, 263065, 426736, 692229, 1122903, 1821538, 2954849, 4793266, 7775472, 12613097, 20460538, 33190414, 53840404

Offset: 0

Tanya Khovanova, Aug 15 2006, Oct 11 2006

			This sequence is similar to A118647 - where no subsequence of length 4 contains 3 ones. It is obvious that the first 4 terms of these two sequences are the same. There are only 3 sequences of length 5 that contain 3 ones such that no subsequence of length 4 contains 3 ones: 10101, 11001, 10011. Hence the fifth term for this sequence is 3 less than the corresponding term of A118647.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Kees Immink and Kui Cai, Properties and constructions of energy-harvesting sliding-window constrained codes, IEEE Comm. Lett., May 2020.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,0,2,0,0,-1,0,-1).

Cf. A118647, A133523, A133551, A334251, A335247.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( 1 +x*(1 +x+x^2)*(2+x^2+x^3-x^4-x^5-x^7)/(1-x-x^3-2*x^5+x^8+x^10) )); // G. C. Greubel, May 05 2023

LinearRecurrence[{1,0,1,0,2,0,0,-1,0,-1}, {1,2,4,7,11,16,26,43,71,116, 186}, 50] (* Harvey P. Dale, Nov 27 2013 *)

def A120118_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1 +x*(1+x+x^2)*(2+x^2+x^3-x^4-x^5-x^7)/(1-x-x^3-2*x^5 +
     x^8+x^10) ).list()
A120118_list(40) # G. C. Greubel, May 05 2023

a(n) = a(n-1) + a(n-3) + 2*a(n-5) - a(n-8) - a(n-10).

G.f.: 1 + x*(1+x+x^2)*(2+x^2+x^3-x^4-x^5-x^7)/(1-x-x^3-2*x^5+x^8+x^10). - R. J. Mathar, Nov 28 2011

A118646 a(n) is the number of binary strings of length n such that there exists a subsequence of length 4 containing 3 or more ones.

Original entry on oeis.org

0, 0, 1, 5, 13, 31, 71, 159, 346, 739, 1559, 3258, 6756, 13922, 28547, 58300, 118668, 240880, 487835, 986085, 1990025, 4010658, 8073786, 16237521, 32629241, 65522823, 131498801, 263774439, 528880599, 1060044148, 2124001923

Offset: 1

Tanya Khovanova, May 10 2006, Aug 17 2006

nonn

Or there are 3 ones in a row - this is relevant only for a(3).

Complementary to A118647, namely a(n) = 2^(n+3) - A118647(n).

			a(4) is 5 because only the following binary strings of length 4 satisfy the conditions: 0111, 1011, 1101, 1011, 1111.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-1,-2,1,-2,-1,2).

Cf. A118647.

R:=PowerSeriesRing(Integers(), 40); [0,0] cat Coefficients( R!( x^3*(1+2*x-x^2-x^3)/((1-2*x)*(1-x-x^2-x^4+x^6)) )); // G. C. Greubel, May 05 2023

LinearRecurrence[{3,-1,-2,1,-2,-1,2}, {0,0,1,5,13,31,71}, 41] (* G. C. Greubel, May 05 2023 *)

def A118646_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x^3*(1+2*x-x^2-x^3)/((1-2*x)*(1-x-x^2-x^4+x^6)) ).list()
a=A118646_list(41); a[1:] # G. C. Greubel, May 05 2023

a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-6) + 13*2^(n-6).
a(n) = +3*a(n-1) -a(n-2) -2*a(n-3) +a(n-4) -2*a(n-5) -a(n-6) +2*a(n-7).
G.f.: x^3*(1+2*x-x^2-x^3)/( (1-2*x)*(1-x-x^2-x^4+x^6) ). - R. J. Mathar, Nov 28 2011

A334251 a(n) is the number of binary (0,1) sequences of length n that have at most two zeros in a window of seven consecutive symbols.

Original entry on oeis.org

1, 2, 4, 7, 11, 16, 22, 29, 43, 66, 102, 157, 239, 358, 526, 777, 1159, 1740, 2619, 3942, 5923, 8870, 13259, 19822, 29667, 44451, 66641, 99912, 149745, 224338, 335993, 503199, 753720, 1129164, 1691796, 2534807, 3797721, 5689507, 8523275, 12768309, 19127928, 28655867, 42930562

Offset: 0

Kees Immink, Apr 20 2020

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. We investigate binary systems emitting 0's and 1's signals where it is assumed that the 1's carry the energy. 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

			a(3) = 7 as there are 8 possible binary (0,1) sequences of length 3 but exactly one of them has more than 2 zero's in a window of seven consecutive symbols (the sequence (000)) leaving 8-1 = 7 such sequences. - _David A. Corneth_, Apr 20 2020

Kees Immink, Table of n, a(n) for n = 0..50

Cf. A118647, A120118, A133523.

G.f.: (x^20 +x^19 +x^18 +2*x^17 +2*x^16 +x^15 -3*x^13 -4*x^12 -5*x^11 -7*x^10 -5*x^9 -3*x^8 -3*x^7 +2*x^6 +3*x^5 +3*x^4 +3*x^3 +2*x^2 +x +1) / (-x^21 -x^18 +x^15 +3*x^14 +x^12 +2*x^11 -3*x^7 -x^4 -x +1).
From David A. Corneth, Apr 21 2020: (Start)
a(n) ~ c*r^n where c = 1.81880731105 and r = 1.498122533939865577.
a(n) = a(n - 1) + a(n - 4) + 3*a(n - 6) - 2*a(n - 10) - a(n - 12) - 3*a(n - 13) - a(n - 15) + a(n - 18) + a(n - 21), n >= 21. (End)

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.

Original entry on oeis.org

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

Kees Immink, May 28 2020

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

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).

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

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 *)

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.

A125513 a(n) is the number of binary strings of length n such that no subsequence of length 5 or less contains 4 or more ones.

Original entry on oeis.org

2, 4, 8, 15, 26, 48, 89, 165, 305, 561, 1034, 1908, 3521, 6496, 11982, 22101, 40770, 75210, 138741, 255934, 472117, 870911, 1606567, 2963628, 5466988, 10084919, 18603592, 34317946, 63306130, 116780470, 215424285, 397391986, 733066807

Offset: 1

Tanya Khovanova, Dec 28 2006

nonn

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

This sequence is similar to the sequences A118647 (where no substring of length 4 contains 3 or more ones), because the number of ones we are checking for is one less than the length of a substring. It is also similar to A120118 (where no substring of length 5 contains 3 or more ones.).

a(n) = a(n-1) + a(n-2) + a(n-4) + 2a(n-5) - a(n-7) - a(n-10).

G.f.: x*(2+2*x+2*x^2+3*x^3+x^4-x^5-x^6-x^7-x^8-x^9)/(1-x-x^2-x^4-2*x^5+x^7+x^ 10) [From Maksym Voznyy (voznyy(AT)mail.ru), Jul 26 2009]

G.f. proposed by Maksym Voznyy checked and corrected by R. J. Mathar, Sep 16 2009.

A130902 a(n) is the number of binary strings of length n such that there exist 4 or more ones in a subsequence of length 5 or less.

Original entry on oeis.org

0, 0, 0, 1, 6, 16, 39, 91, 207, 463, 1014, 2188, 4671, 9888, 20786, 43435, 90302, 186934, 385547, 792642, 1625035, 3323393, 6782041, 13813588, 28087444, 57023945, 115614136, 234117510, 473564782, 956961354, 1932059363, 3897575310, 7856867785, 15827584881

Offset: 0

Tanya Khovanova, Sep 28 2007

nonn

Matthew House, Table of n, a(n) for n = 0..3304
Index entries for linear recurrences with constant coefficients, signature (3,-1,-2,1,0,-4,-1,2,0,-1,2).

Cf. A118647, A118646.

LinearRecurrence[{3,-1,-2,1,0,-4,-1,2,0,-1,2},{0,0,0,1,6,16,39,91,207,463,1014},40] (* Harvey P. Dale, Jul 19 2020 *)

a(n) = 2^n - A125513(n).

G.f.: x^3*(-1-3*x+x^2+x^3-x^4+x^5+x^6) / ( (2*x-1)*(x^10+x^7-2*x^5-x^4-x^2-x+1) ). - R. J. Mathar, Nov 28 2011

More terms from Matthew House, Dec 26 2016

A131283 a(n) is the number of binary strings of length n such that there exist 3 or more ones in a subsequence of length 5 or less.

Original entry on oeis.org

0, 0, 1, 5, 16, 38, 85, 185, 396, 838, 1748, 3609, 7400, 15097, 30681, 62154, 125588, 253246, 509850, 1025153, 2059159, 4132679, 8288643, 16615051, 33291367, 66682128, 133525499, 267312553, 535049374, 1070786975, 2142690382

Offset: 1

Tanya Khovanova, Sep 28 2007

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

Cf. A118646, A118647.

concat([0, 0], Vec(x^3*(1+2*x+3*x^2-x^6-x^7-x^3-2*x^5) / ( (1-2*x)*(1-x-x^3-2*x^5+x^8+x^10) ) + O(x^40))) \\ Michel Marcus, May 28 2020

a(n) = 2^n - A120118(n).
a(n)= +3*a(n-1) -2*a(n-2) +a(n-3) -2*a(n-4) +2*a(n-5) -4*a(n-6) -a(n-8) +2*a(n-9) -a(n-10) +2*a(n-11).
G.f.: x^3*(1 +2*x +3*x^2 -x^6 -x^7 -x^3 -2*x^5) / ( (1-2*x)*(1-x-x^3-2*x^5+x^8+x^10) ). - R. J. Mathar, Nov 28 2011

Showing 1-9 of 9 results.

cp's OEIS Frontend

A212402 T(n,k)=Number of binary arrays of length n+2*k-1 with no more than k ones in any length 2k subsequence (=50% duty cycle).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A241964 T(n,k)=Number of length n+3 0..k arrays with no consecutive four elements summing to more than 2*k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A120118 a(n) is the number of binary strings of length n such that no subsequence of length 5 or less contains 3 or more ones.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A118646 a(n) is the number of binary strings of length n such that there exists a subsequence of length 4 containing 3 or more ones.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A334251 a(n) is the number of binary (0,1) sequences of length n that have at most two zeros in a window of seven consecutive symbols.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A125513 a(n) is the number of binary strings of length n such that no subsequence of length 5 or less contains 4 or more ones.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A130902 a(n) is the number of binary strings of length n such that there exist 4 or more ones in a subsequence of length 5 or less.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions