A209888 -id:A209888 - cp's OEIS frontend

A107066 Expansion of 1/(1-2*x+x^5).

1, 2, 4, 8, 16, 31, 60, 116, 224, 432, 833, 1606, 3096, 5968, 11504, 22175, 42744, 82392, 158816, 306128, 590081, 1137418, 2192444, 4226072, 8146016, 15701951, 30266484, 58340524, 112454976, 216763936, 417825921, 805385358, 1552430192, 2992405408, 5768046880

Offset: 0

Paul Barry, May 10 2005

Row sums of number triangle A107065.
Same as A018922 plus first 3 additional terms. - Vladimir Joseph Stephan Orlovsky, Jul 08 2011
a(n) is the number of binary words of length n containing no subword 01011. - Alois P. Heinz, Mar 14 2012

			G.f. = 1 + 2*x + 4*x^2 + 8*x^3 + 16*x^4 + 31*x^5 + 60*x^6 + 116*x^7 + 224*x^8 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Otto Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see p. 356.
Jia Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv:2501.07463 [math.CO], 2025. See p. 7.
Thomas Langley, Jeffrey Liese, and Jeffrey Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), Article #11.4.2.
Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,-1).

Cf. A018922, A119407 (partial sums), A000078 (first differences).
Cf. A209888. - Alois P. Heinz, Mar 14 2012
Column k = 1 of array A140996 (with a different offset) and second main diagonal of A140995.
Column k = 4 of A172119 (with a different offset).

a:=[1,2,4,8,16];; for n in [6..40] do a[n]:=2*a[n-1]-a[n-5]; od; a; # G. C. Greubel, Jun 12 2019

I:=[1,2,4,8,16]; [n le 5 select I[n] else 2*Self(n-1) - Self(n-5): n in [1..40]]; // G. C. Greubel, Jun 12 2019

CoefficientList[Series[1/(1 - 2*z + z^5), {z, 0, 40}], z] (* Vladimir Joseph Stephan Orlovsky, Jul 08 2011 *)
LinearRecurrence[{2,0,0,0,-1}, {1,2,4,8,16}, 40] (* G. C. Greubel, Jun 12 2019 *)

{a(n) = if( n<0, n = -n; polcoeff( -x^5 / (1 - 2*x^4 + x^5) + x * O(x^n), n), polcoeff( 1 / (1 - 2*x + x^5) + x * O(x^n), n))} /* Michael Somos, Dec 28 2012 */

(1/(1-2*x+x^5)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Jun 12 2019

a(n) = 2*a(n-1) - a(n-5).
a(n) = Sum_{k=0..floor(n/5)} C(n-4*k, k) * 2^(n-2*k) *(-1)^k.
a(n) = A018922(n-3) for n >= 3. - R. J. Mathar, Mar 09 2007
First difference of A119407. - Michael Somos, Dec 28 2012
From Petros Hadjicostas, Jun 12 2019: (Start)
G.f.: 1/((1 - x)*(1 - x - x^2 - x^3 - x^4)).
Setting k = 1 in the double recurrence for array A140996, we get that a(n+5) = 1 + a(n+1) + a(n+2) + a(n+3) + a(n+4) for n >= 0, which of course we can prove using other methods as well. See also Dunkel (1925).
(End)
a(n) = Sum_{k=0..n+3} A000078(k). - Greg Dresden, Jan 01 2021

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

A317669 Number of equivalence classes of binary words of length n for the subword 10110.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 4, 6, 8, 11, 16, 22, 31, 44, 61, 86, 121, 169, 238, 334, 468, 658, 923, 1295, 1819, 2552, 3582, 5029, 7057, 9906, 13905, 19515, 27393, 38449, 53965, 75748, 106319, 149228, 209460, 293996, 412653, 579204, 812968, 1141085, 1601632, 2248049

Offset: 0

Alois P. Heinz, Aug 03 2018

Two binary words of the same length are equivalent with respect to a given subword if they have equal sets of occurrences of this subword.

			a(11) = 16, the positions of subword 10110 in words of the 16 classes are given by the sets: {}, {0}, {1}, {2}, {3}, {4}, {5}, {6}, {0,3}, {1,4}, {0,5}, {2,5}, {0,6}, {1,6}, {3,6}, {0,3,6}, where 0 indicates the leftmost position. Example words for class {2,5} are xx10110110x, where each x can be replaced by 0 or by 1 and both occurrences of the subword overlap. There is only one word in class {0,3,6}: 10110110110.  Class {1,6} has two words: 01011010110 and 11011010110.

Alois P. Heinz, Table of n, a(n) for n = 0..2500
Michael A. Allen, Combinations without specified separations and restricted-overlap tiling with combs, arXiv:2210.08167 [math.CO], 2022.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,1).

Cf. A209888, A277751, A317783, A317779.

b:= proc(n, t) option remember; `if`(n<0, 0, `if`(n=0, 1,
      add(b(n-j, j), j={1, 5, `if`(t=1, 1, 3)})))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..60);
# second Maple program:
a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
          <0|0|0|0|1>, <1|-1|1|0|1>>^n.<<[1$5][]>>)[1$2]:
seq(a(n), n=0..60);
# third Maple program:
a:= proc(n) option remember; `if`(n<5, 1, a(n-1) +a(n-3) -a(n-4) +a(n-5)) end:
seq(a(n), n=0..60);

LinearRecurrence[{1, 0, 1, -1, 1}, {1, 1, 1, 1, 1}, 100] (* Jean-François Alcover, Sep 23 2022 *)

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

a(n) = a(n-1) +a(n-3) -a(n-4) +a(n-5) for n >= 5, a(n) = 1 for n < 5.

A277751 Number T(n,k) of binary words of length n containing exactly k (possibly overlapping) occurrences of the subword 01101; triangle T(n,k), n>=0, k=0..max(0,floor((n-2)/3)), read by rows.

Original entry on oeis.org

1, 2, 4, 8, 16, 31, 1, 60, 4, 116, 12, 225, 30, 1, 436, 72, 4, 845, 166, 13, 1637, 375, 35, 1, 3172, 828, 92, 4, 6146, 1802, 230, 14, 11909, 3872, 562, 40, 1, 23075, 8243, 1333, 113, 4, 44711, 17404, 3106, 300, 15, 86633, 36501, 7114, 778, 45, 1, 167863, 76104

Offset: 0

Alois P. Heinz, Oct 28 2016

			Triangle T(n,k) begins:
:     1;
:     2;
:     4;
:     8;
:    16;
:    31,   1;
:    60,   4;
:   116,  12;
:   225,  30,  1;
:   436,  72,  4;
:   845, 166, 13;
:  1637, 375, 35, 1;
:  3172, 828, 92, 4;

Alois P. Heinz, Rows n = 0..350, flattened

Columns k=0-2 give: A209888, A317780, A317781.
Row sums give A000079.
Cf. A001787, A317669.

b:= proc(n, t) option remember; expand(
      `if`(n=0, 1,     b(n-1, [2, 2, 2, 5, 2][t])+
      `if`(t=5, x, 1)* b(n-1, [1, 3, 4, 1, 3][t])))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..20);
# second Maple program:
gf:= k-> `if`(k=0, (x+1)*(x^2-x+1), x^5*(x^3*(x-1)^2)^(k-1))
                   /(x^5-2*x^4+x^3-2*x+1)^(k+1):
T:= (n, k)-> coeff(series(gf(k), x, n+1), x, n):
seq(seq(T(n, k), k=0..max(0, floor((n-2)/3))), n=0..20);

b[n_, t_] := b[n, t] = Expand[
     If[n==0, 1,     b[n-1, {2, 2, 2, 5, 2}[[t]]] +
     If[t==5, x, 1]* b[n-1, {1, 3, 4, 1, 3}[[t]]]]];
T[n_] := CoefficientList[b[n, 1], x];
T /@ Range[0, 20] // Flatten (* Jean-François Alcover, Feb 22 2021, after first Maple program *)

G.f. of column k=0: (x+1)*(x^2-x+1)/(x^5-2*x^4+x^3-2*x+1); g.f. of column k>0: x^5*(x^3*(x-1)^2)^(k-1)/(x^5+x^4-x^3+2*x-1)^(k+1).

Sum_{k>=0} k * T(n,k) = A001787(n-4) for n > 3.

cp's OEIS Frontend

A107066 Expansion of 1/(1-2*x+x^5).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

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

A317669 Number of equivalence classes of binary words of length n for the subword 10110.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A277751 Number T(n,k) of binary words of length n containing exactly k (possibly overlapping) occurrences of the subword 01101; triangle T(n,k), n>=0, k=0..max(0,floor((n-2)/3)), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula