A317669 -id:A317669 - cp's OEIS frontend

A376033 Number A(n,k) of binary words of length n avoiding distance (i+1) between "1" digits if the i-th bit is set in the binary representation of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 2, 1, 2, 4, 1, 2, 3, 8, 1, 2, 4, 5, 16, 1, 2, 3, 6, 8, 32, 1, 2, 4, 4, 9, 13, 64, 1, 2, 3, 8, 6, 15, 21, 128, 1, 2, 4, 5, 12, 9, 25, 34, 256, 1, 2, 3, 6, 7, 18, 13, 40, 55, 512, 1, 2, 4, 4, 8, 11, 27, 19, 64, 89, 1024, 1, 2, 3, 8, 5, 11, 16, 45, 28, 104, 144, 2048

Offset: 0

Alois P. Heinz, Sep 09 2024

Also the number of subsets of [n] avoiding distance (i+1) between elements if the i-th bit is set in the binary representation of k. A(6,3) = 13: {}, {1}, {2}, {3}, {4}, {5}, {6}, {1,4}, {1,5}, {1,6}, {2,5}, {2,6}, {3,6}.
Each column sequence satisfies a linear recurrence with constant coefficients.
The sequence of row n is periodic with period A011782(n) = ceiling(2^(n-1)).

			A(6,6) = 17: 000000, 000001, 000010, 000011, 000100, 000110, 001000, 001100, 010000, 010001, 011000, 100000, 100001, 100010, 100011, 110000, 110001 because 6 = 110_2 and no two "1" digits have distance 2 or 3.
A(6,7) = 10: 000000, 000001, 000010, 000100, 001000, 010000, 010001, 100000, 100001, 100010.
A(7,7) = 14: 0000000, 0000001, 0000010, 0000100, 0001000, 0010000, 0010001, 0100000, 0100001, 0100010, 1000000, 1000001, 1000010, 1000100.
Square array A(n,k) begins:
     1,  1,   1,  1,   1,  1,  1,  1,   1,  1, ...
     2,  2,   2,  2,   2,  2,  2,  2,   2,  2, ...
     4,  3,   4,  3,   4,  3,  4,  3,   4,  3, ...
     8,  5,   6,  4,   8,  5,  6,  4,   8,  5, ...
    16,  8,   9,  6,  12,  7,  8,  5,  16,  8, ...
    32, 13,  15,  9,  18, 11, 11,  7,  24, 11, ...
    64, 21,  25, 13,  27, 16, 17, 10,  36, 17, ...
   128, 34,  40, 19,  45, 25, 27, 14,  54, 25, ...
   256, 55,  64, 28,  75, 37, 41, 19,  81, 37, ...
   512, 89, 104, 41, 125, 57, 60, 26, 135, 57, ...

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

Columns k=0-20 give: A000079, A000045(n+2), A006498(n+2), A000930(n+2), A006500, A130137, A079972(n+3), A003269(n+4), A031923(n+1), A263710(n+1), A224809(n+4), A317669(n+4), A351873, A351874, A121832(n+4), A003520(n+4), A208742, A374737, A375977, A375980, A375978.
Rows n=0-2 give: A000012, A007395(k+1), A010702(k+1).
Main diagonal gives A376091.
A(n,2^k-1) gives A141539.
A(2^n-1,2^n-1) gives A376697.
A(n,2^k) gives A209435.
Cf. A011782, A062383, A098011, A376921.

h:= proc(n) option remember; `if`(n=0, 1, 2^(1+ilog2(n))) end:
b:= proc(n, k, t) option remember; `if`(n=0, 1, add(`if`(j=1 and
      Bits[And](t, k)>0, 0, b(n-1, k, irem(2*t+j, h(k)))), j=0..1))
    end:
A:= (n, k)-> b(n, k, 0):
seq(seq(A(n, d-n), n=0..d), d=0..12);

step(v,b)={vector(#v, i, my(j=(i-1)>>1); if(bittest(i-1,0), if(bitand(b,j)==0, v[1+j], 0), v[1+j] + v[1+#v/2+j]));}
col(n,k)={my(v=vector(2^(1+logint(k,2))), r=vector(1+n)); v[1]=r[1]=1; for(i=1, n, v=step(v,k); r[1+i]=vecsum(v)); r}
A(n,k)=if(k==0, 2^n, col(n,k)[n+1]) \\ Andrew Howroyd, Oct 03 2024

A(n,k) = A(n,k+ceiling(2^(n-1))).
A(n,ceiling(2^(n-1))-1) = n+1.
A(n,ceiling(2^(n-2))) = ceiling(3*2^(n-2)) = A098011(n+2).

A209888 Number of binary words of length n containing no subword 01101.

Original entry on oeis.org

1, 2, 4, 8, 16, 31, 60, 116, 225, 436, 845, 1637, 3172, 6146, 11909, 23075, 44711, 86633, 167863, 325256, 630226, 1221144, 2366125, 4584673, 8883398, 17212733, 33351899, 64623621, 125216632, 242623433, 470114310, 910907331, 1765000872, 3419917668, 6626533192

Offset: 0

Alois P. Heinz, Mar 14 2012

nonn

Notice that the proper suffix 01 of 01101 is also a prefix of 01101. If instead of 01101 subword 01011 is not allowed, we get A107066 with A107066(n) < a(n) for all n >= 8. Word 01101101 of length 8 is the smallest binary word having two or more copies of 01101.

			a(6) = 60 because among the 2^6 = 64 binary words of length 6 only 4, namely 001101, 011010, 011011 and 101101 contain the subword 01101.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,2,-1).

Column 22 of A209972.
Column k=0 of A277751.
Cf. A107066, A317669.

a:= n-> (Matrix(5, (i, j)-> `if`(i=j-1, 1, `if`(i=5, [-1, 2, -1, 0, 2][j], 0)))^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);

CoefficientList[Series[(x + 1)*(x^2 - x + 1)/(x^5 - 2*x^4 + x^3 - 2*x + 1), {x, 0, 40}], x] (* Wesley Ivan Hurt, Apr 28 2017 *)
LinearRecurrence[{2,0,-1,2,-1},{1,2,4,8,16},40] (* Harvey P. Dale, Sep 17 2017 *)

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

a(n) = 2^n if n<5, and a(n) = 2*(a(n-1)+a(n-4)) -a(n-3) -a(n-5) otherwise.

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.

A317779 Number of equivalence classes of binary words of length n for the set of subwords {010, 101, 10110}.

Original entry on oeis.org

1, 1, 1, 3, 7, 14, 26, 47, 86, 160, 300, 562, 1051, 1962, 3661, 6833, 12757, 23820, 44477, 83045, 155052, 289493, 540506, 1009172, 1884217, 3518007, 6568439, 12263866, 22897737, 42752130, 79822071, 149034991, 278261743, 519539714, 970027388, 1811128400

Offset: 0

Alois P. Heinz, Aug 08 2018

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

			a(7) = 47: [||], [|0|], [0||], [|1|], [|2|], [|3|], [|4|], [1||], [2||], [3||], [4||], [|0|0], [|04|], [03||], [04||], [14||], [1|0|], [0|1|], [2|1|], [1|2|], [3|2|], [2|3|], [4|3|], [3|4|], [|1|1], [|2|2], [02|1|], [1|02|], [13|2|], [2|13|], [14|0|], [24|3|], [03|4|], [3|24|], [|03|0], [|14|1], [0|1|1], [1|2|2], [13|02|], [02|13|], [24|13|], [13|24|], [1|02|2], [4|03|0], [0|14|1], [024|13|], [13|024|].  Here [1|02|2] describes the class whose members have an occurrence of 010 at position 1 and occurrences of 101 at positions 0 and 2 and an occurrence of 10110 at position 2 and no other occurrences of the subwords: 1010110.

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (1,1,1,0,0,1,1,-1,-1,-1).

Cf. A000045, A317669, A317783.

a:= n-> coeff(series((x^9+2*x^8+2*x^7-x^6-3*x^5-2*x^4+x^2-1)/
             (-x^10-x^9-x^8+x^7+x^6+x^3+x^2+x-1),x,n+1),x,n):
seq(a(n), n=0..35);

G.f.: (x^9+2*x^8+2*x^7-x^6-3*x^5-2*x^4+x^2-1)/(-x^10-x^9-x^8+x^7+x^6+x^3+x^2+x-1).

A317783 Number of equivalence classes of binary words of length n for the set of subwords {010, 101}.

Original entry on oeis.org

1, 1, 1, 3, 7, 13, 23, 41, 75, 139, 257, 473, 869, 1597, 2937, 5403, 9939, 18281, 33623, 61841, 113743, 209207, 384793, 707745, 1301745, 2394281, 4403769, 8099795, 14897847, 27401413, 50399055, 92698313, 170498779, 313596147, 576793241, 1060888169, 1951277557

Offset: 0

Alois P. Heinz, Aug 06 2018

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

All terms are odd.

			a(6) = 23: [|], [|0], [0|], [|1], [|2], [|3], [1|], [2|], [3|], [|03], [03|], [1|0], [0|1], [2|1], [1|2], [3|2], [2|3], [02|1], [1|02], [13|2], [2|13], [13|02], [02|13].  Here [13|2] describes the class whose members have occurrences of 010 at positions 1 and 3 and an occurrence of 101 at position 2 and no other occurrences of both subwords: 001010.  [|] describes the class that avoids both subwords and has 26 members for n=6, in general 2*A000045(n+1) (for n>0).

Alois P. Heinz, Table of n, a(n) for n = 0..2000
Index entries for linear recurrences with constant coefficients, signature (2,-1,1,0,1).

Cf. A000045, A128588, A164146, A303696, A317669, A317779.

a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
          <0|0|0|0|1>, <1|0|1|-1|2>>^n.<<1, 1, 1, 3, 7>>)[1$2]:
seq(a(n), n=0..45);
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [1$3, 3, 7][n+1],
      2*a(n-1) -a(n-2) +a(n-3) +a(n-5))
    end:
seq(a(n), n=0..45);

LinearRecurrence[{2, -1, 1, 0, 1}, {1, 1, 1, 3, 7}, 40] (* Jean-François Alcover, Apr 30 2022 *)

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

a(n) = 2*a(n-1) -a(n-2) +a(n-3) +a(n-5) for n >= 5.

A375185 Number of subsets of {1,2,...,n} such that no two elements differ by 1, 2, 3, or 5.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 9, 12, 16, 22, 29, 39, 52, 70, 93, 125, 167, 224, 299, 401, 536, 718, 960, 1286, 1720, 2303, 3081, 4125, 5519, 7388, 9886, 13233, 17708, 23702, 31719, 42454, 56815, 76042, 101767, 136204, 182284, 243965, 326505, 436984, 584831, 782716

Offset: 0

Michael A. Allen, Aug 02 2024

a(n-4) for n>3 is the number of equivalence classes of binary words of length n for the subword 100010 (see A317669 for further explanation).

a(n) is the number of compositions of n+5 into parts 1, 6, 10, 14, 18, 22, ...

			For n = 6, the 9 subsets are {}, {1}, {2}, {3}, {4}, {5}, {1,5}, {6}, {2,6}.

Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1,1).
Index entries for subsets of {1,..,n} with disallowed differences

Column k=23 of A376033.

CoefficientList[Series[(1 + x + x^2 + x^3 + x^5)/(1 - x - x^4 + x^5 - x^6),{x,0,45}],x]
LinearRecurrence[{1, 0, 0, 1, -1, 1}, {1, 2, 3, 4, 5, 7}, 45]

a(n) = a(n-1) + a(n-4) - a(n-5) + a(n-6) for n >= 6.

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

A375186 Number of subsets of {1,2,...,n} such that no two elements differ by 1, 2, 4, or 5.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 10, 14, 19, 25, 35, 48, 64, 88, 120, 161, 220, 300, 405, 552, 752, 1018, 1385, 1885, 2556, 3475, 4727, 6416, 8720, 11857, 16102, 21881, 29745, 40406, 54905, 74626, 101389, 137769, 187235, 254404, 345689, 469781, 638339

Offset: 0

Michael A. Allen, Aug 02 2024

a(n-4) for n>3 is the number of equivalence classes of binary words of length n for the subword 100110 (see A317669 for further explanation).

a(n) is the number of compositions of n+5 into parts 1, 6, 9, 12, 15, 18, ...

			For n = 6, the 10 subsets are {}, {1}, {2}, {3}, {4}, {1,4}, {5}, {2,5}, {6}, {3,6}.

Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1,0,1).
Index entries for subsets of {1,..,n} with disallowed differences

Column k=27 of A376033.

CoefficientList[Series[(1 + x + x^2 + x^4 + x^5)/(1 - x - x^3 + x^4 - x^6),{x,0,42}],x]
LinearRecurrence[{1, 0, 1, -1, 0, 1}, {1, 2, 3, 4, 6, 8}, 42]

a(n) = a(n-1) + a(n-3) - a(n-4) + a(n-6) for n>= 6.

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

cp's OEIS Frontend

A376033 Number A(n,k) of binary words of length n avoiding distance (i+1) between "1" digits if the i-th bit is set in the binary representation of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

PARI

Formula

A209888 Number of binary words of length n containing no subword 01101.

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

A317779 Number of equivalence classes of binary words of length n for the set of subwords {010, 101, 10110}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A317783 Number of equivalence classes of binary words of length n for the set of subwords {010, 101}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A375185 Number of subsets of {1,2,...,n} such that no two elements differ by 1, 2, 3, or 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A375186 Number of subsets of {1,2,...,n} such that no two elements differ by 1, 2, 4, or 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica