A118870 -id:A118870 - cp's OEIS frontend

A255992 T(n,k)=Number of length n+k 0..1 arrays with at most one downstep in every k consecutive neighbor pairs.

4, 8, 8, 15, 16, 16, 26, 28, 32, 32, 42, 45, 53, 64, 64, 64, 68, 80, 100, 128, 128, 93, 98, 114, 144, 188, 256, 256, 130, 136, 156, 196, 256, 354, 512, 512, 176, 183, 207, 257, 337, 451, 667, 1024, 1024, 232, 240, 268, 328, 428, 568, 796, 1256, 2048, 2048, 299, 308

Offset: 1

R. H. Hardin, Mar 13 2015

Table starts
....4....8...15...26...42...64...93..130..176..232..299..378..470..576...697
....8...16...28...45...68...98..136..183..240..308..388..481..588..710...848
...16...32...53...80..114..156..207..268..340..424..521..632..758..900..1059
...32...64..100..144..196..257..328..410..504..611..732..868.1020.1189..1376
...64..128..188..256..337..428..530..644..771..912.1068.1240.1429.1636..1862
..128..256..354..451..568..705..854.1016.1192.1383.1590.1814.2056.2317..2598
..256..512..667..796..945.1134.1352.1584.1831.2094.2374.2672.2989.3326..3684
..512.1024.1256.1413.1574.1797.2088.2419.2766.3130.3512.3913.4334.4776..5240
.1024.2048.2365.2510.2645.2848.3175.3606.4090.4592.5113.5654.6216.6800..7407
.2048.4096.4454.4448.4476.4560.4824.5294.5912.6598.7304.8031.8780.9552.10348

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

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

Column 1 is A000079(n+1)
Column 2 is A000079(n+2)
Column 3 is A118870(n+3)
Row 1 is A000125(n+1)

Empirical for column k:
k=1: a(n) = 2*a(n-1)
k=2: a(n) = 2*a(n-1)
k=3: a(n) = 2*a(n-1) -a(n-2) +2*a(n-3) -a(n-4)
k=4: a(n) = 2*a(n-1) -a(n-2) +3*a(n-4) -2*a(n-5)
k=5: a(n) = 2*a(n-1) -a(n-2) +4*a(n-5) -3*a(n-6)
k=6: a(n) = 2*a(n-1) -a(n-2) +5*a(n-6) -4*a(n-7)
k=7: a(n) = 2*a(n-1) -a(n-2) +6*a(n-7) -5*a(n-8)
Empirical for row n:
n=1: a(n) = (1/6)*n^3 + (1/2)*n^2 + (4/3)*n + 2
n=2: a(n) = (1/6)*n^3 + n^2 + (23/6)*n + 3
n=3: a(n) = (1/6)*n^3 + (3/2)*n^2 + (31/3)*n + 4
n=4: a(n) = (1/6)*n^3 + 2*n^2 + (143/6)*n + 6 for n>2
n=5: a(n) = (1/6)*n^3 + (5/2)*n^2 + (145/3)*n + 12 for n>3
n=6: a(n) = (1/6)*n^3 + 3*n^2 + (533/6)*n + 28 for n>4
n=7: a(n) = (1/6)*n^3 + (7/2)*n^2 + (454/3)*n + 64 for n>5

A209972 Number of binary words of length n avoiding the subword given by the binary expansion of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 3, 4, 1, 1, 1, 2, 4, 5, 5, 1, 1, 1, 2, 4, 7, 8, 6, 1, 1, 1, 2, 4, 7, 12, 13, 7, 1, 1, 1, 2, 4, 7, 12, 20, 21, 8, 1, 1, 1, 2, 4, 7, 12, 21, 33, 34, 9, 1, 1, 1, 2, 4, 8, 13, 20, 37, 54, 55, 10, 1, 1, 1, 2, 4, 8, 15, 24, 33, 65, 88, 89, 11, 1, 1

Offset: 0

Alois P. Heinz, Mar 16 2012

			Square array begins:
  1,  1,  1,   1,   1,   1,   1,   1,   1, ...
  1,  1,  2,   2,   2,   2,   2,   2,   2, ...
  1,  1,  3,   3,   4,   4,   4,   4,   4, ...
  1,  1,  4,   5,   7,   7,   7,   7,   8, ...
  1,  1,  5,   8,  12,  12,  12,  13,  15, ...
  1,  1,  6,  13,  20,  21,  20,  24,  28, ...
  1,  1,  7,  21,  33,  37,  33,  44,  52, ...
  1,  1,  8,  34,  54,  65,  54,  81,  96, ...
  1,  1,  9,  55,  88, 114,  88, 149, 177, ...

Alois P. Heinz, Antidiagonals n = 0..150, flattened

Columns give: 0, 1: A000012, 2: A001477(n+1), 3: A000045(n+2), 4, 6: A000071(n+3), 5: A005251(n+3), 7: A000073(n+3), 8, 12, 14: A008937(n+1), 9, 11, 13: A049864(n+2), 10: A118870, 15: A000078(n+4), 16, 20, 24, 26, 28, 30: A107066, 17, 19, 23, 25, 29: A210003, 18, 22: A209888, 21: A152718(n+3), 27: A210021, 31: A001591(n+5), 32: A001949(n+5), 33, 35, 37, 39, 41, 43, 47, 49, 53, 57, 61: A210031.

Main diagonal equals A234005 or column k=0 of A233940.

A[n_, k_] := Module[{bb, cnt = 0}, Do[bb = PadLeft[IntegerDigits[j, 2], n]; If[SequencePosition[bb, IntegerDigits[k, 2], 1]=={}, cnt++], {j, 0, 2^n-1 }]; cnt];
Table[A[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Nov 01 2021 *)

A118869 Triangle read by rows: T(n,k) is the number of binary sequences of length n containing k subsequences 0101 (n,k>=0).

Original entry on oeis.org

1, 2, 4, 8, 15, 1, 28, 4, 53, 10, 1, 100, 24, 4, 188, 57, 10, 1, 354, 128, 26, 4, 667, 278, 68, 10, 1, 1256, 596, 164, 28, 4, 2365, 1260, 381, 79, 10, 1, 4454, 2628, 876, 200, 30, 4, 8388, 5430, 1977, 488, 90, 10, 1, 15796, 11136, 4380, 1184, 236, 32, 4, 29747, 22683

Offset: 0

Emeric Deutsch, May 03 2006

Row n has floor(n/2) terms (n>=2). Sum of entries in row n is 2^n (A000079). T(n,0) = A118870(n). T(n,1) = A118871(n). Sum(k*T(n,k), k=0..n-1) = (n-3)*2^(n-4) (A001787).

			T(7,2) = 4 because we have 0101010, 0101011, 0010101 and 1010101.
Triangle starts:
   1;
   2;
   4;
   8;
  15,  1;
  28,  4;
  53, 10, 1;
  ...

Alois P. Heinz, Rows n = 1..200, flattened
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009, page 211.

Cf. A000079, A118870, A118871, A001787, A118429, A332052.

G:=(1+(1-t)*z^2)/(1-2*z+(1-t)*z^2*(1-z)^2): Gser:=simplify(series(G,z=0,20)): P[0]:=1: for n from 1 to 16 do P[n]:=coeff(Gser,z^n) od: 1;2;for n from 1 to 16 do seq(coeff(P[n],t,j),j=0..floor(n/2)-1) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n, t) option remember; `if`(n=0, 1,
       expand(b(n-1, `if`(t=3, 4, 2))+
       b(n-1, 3-2*irem(t, 2))*`if`(t=4, x, 1)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..16); # Alois P. Heinz, Nov 28 2013

nn=15;CoefficientList[Series[1/(1-2z-(u-1)z^4/(1-(u-1)z^2)),{z,0,nn}],{z,u}]//Grid (* Geoffrey Critzer, Nov 29 2013 *)

G.f.: G(t,z) = [1+(1-t)z^2]/[1-2z+(1-t)z^2*(1-z)^2].

A332052 Number of binary words of length n with an even number of occurrences of the subword 0101.

Original entry on oeis.org

1, 2, 4, 8, 15, 28, 54, 104, 198, 380, 736, 1424, 2756, 5360, 10456, 20416, 39944, 78352, 153952, 302912, 596976, 1178304, 2328544, 4606848, 9124448, 18089920, 35895552, 71283968, 141664832, 281718528, 560561024, 1115994112, 2222846080, 4429381888, 8829667840

Offset: 0

Alois P. Heinz, Feb 06 2020

			a(4) = 15 = 2^4 - 1: 0101 is not counted.
a(5) = 28 = 2^5 - 4: 00101, 10101, 01010, 01011 are not counted.

Alois P. Heinz, Table of n, a(n) for n = 0..3322
Index entries for linear recurrences with constant coefficients, signature (4,-6,8,-10,4).

Cf. A118869, A118870.

a:= n-> 2^n-(<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>
            , <0|0|0|0|1>, <4|-10|8|-6|4>>^n)[1, 5]:
seq(a(n), n=0..39);

LinearRecurrence[{4,-6,8,-10,4},{1,2,4,8,15},50] (* Harvey P. Dale, Mar 07 2024 *)

G.f.: (x^4-4*x^3+2*x^2-2*x+1)/((1-2*x)*(2*x^4-4*x^3+2*x^2-2*x+1)).

a(n) = Sum_{k>=0} A118869(n,2*k).

A118871 Number of binary sequences of length n containing exactly one subsequence 0101.

Original entry on oeis.org

0, 0, 0, 0, 1, 4, 10, 24, 57, 128, 278, 596, 1260, 2628, 5430, 11136, 22683, 45936, 92574, 185764, 371347, 739840, 1469580, 2911224, 5753048, 11343800, 22322444, 43845120, 85973013, 168314604, 329041842, 642385248, 1252552077, 2439430272, 4745767138, 9223159852

Offset: 0

Emeric Deutsch, May 03 2006

nonn

With only two 0's at the beginning, the convolution of A112575 with itself. Column 1 of A118869.

			a(5) = 4 because we have 01010, 01011, 00101 and 10101.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-6,8,-11,8,-6,4,-1).

Cf. A112575, A118430, A118869, A118870.

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

g:=z^4/(1-2*z+z^2-2*z^3+z^4)^2: gser:=series(g,z=0,40): seq(coeff(gser, z, n), n=0..35);

LinearRecurrence[{4,-6,8,-11,8,-6,4,-1}, {0,0,0,0,1,4,10,24}, 40] (* G. C. Greubel, Jan 14 2022 *)

@CachedFunction
def A112575(n): return sum((-1)^k*binomial(n-k, k)*lucas_number1(n-2*k, 2, -1) for k in (0..(n/2)))
def A118871(n): return sum( A112575(j+1)*A112575(n-j-3) for j in (0..n-4) )
[A118871(n) for n in (0..40)] # G. C. Greubel, Jan 14 2022

G.f.: x^4/(1-2*x+x^2-2*x^3+x^4)^2.

a(n) = Sum_{j=0..n-4} A112575(j+1)*A112575(n-j-3). - G. C. Greubel, Jan 14 2022

cp's OEIS Frontend

A255992 T(n,k)=Number of length n+k 0..1 arrays with at most one downstep in every k consecutive neighbor pairs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A209972 Number of binary words of length n avoiding the subword given by the binary expansion of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A118869 Triangle read by rows: T(n,k) is the number of binary sequences of length n containing k subsequences 0101 (n,k>=0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A332052 Number of binary words of length n with an even number of occurrences of the subword 0101.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A118871 Number of binary sequences of length n containing exactly one subsequence 0101.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula