A376033 -id:A376033 - cp's OEIS frontend

A376697 Number of binary words of length 2^n-1 with at least n "0" between any two "1" digits.

1, 2, 4, 14, 106, 3970, 2951330, 601479320126, 4878266198984685082072, 20251346657999168900614712784617499550822, 2947350921470608599960387502833128388134614870362931531590353774089056633192

Offset: 0

Alois P. Heinz, Oct 02 2024

nonn

			a(0) = 1: the empty word.
a(1) = 2: 0, 1.
a(2) = 4: 000, 100, 010, 001.
a(3) = 14: 0000000, 1000000, 0100000, 0010000, 0001000, 0000100, 1000100, 0000010, 1000010, 0100010, 0000001, 1000001, 0100001, 0010001.

Alois P. Heinz, Table of n, a(n) for n = 0..14

Cf. A000225, A141539, A376033, A376091.

from math import comb
def A376697(n): return 1 + sum(comb(2**n-(n*i)-1,i+1) for i in range(0,(2**n-2)//(n+1)+1)) # John Tyler Rascoe, Oct 04 2024

a(n) = A141539(2^n-1,n).
a(n) = A376091(2^n-1).
a(n) = A376033(2^n-1,2^n-1).
a(n) = 1 + Sum_{i=0..floor((2^n-2)/(n+1))} binomial(2^n-(n*i)-1,i+1). - John Tyler Rascoe, Oct 04 2024

A376091 Number 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 n.

Original entry on oeis.org

1, 2, 4, 4, 12, 11, 17, 14, 81, 57, 81, 61, 260, 126, 236, 106, 5000, 1623, 2653, 1181, 6848, 4751, 2838, 1286, 42024, 7526, 14272, 6416, 55012, 10422, 21992, 3970, 12595401, 1148865, 2411809, 268605, 2146689, 656872, 1018489, 186997, 25401600, 5147033, 1567504

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 n. a(6) = 17: {}, {1}, {2}, {3}, {4}, {5}, {6}, {1,2}, {1,5}, {1,6}, {2,3}, {2,6}, {3,4}, {4,5}, {5,6}, {1,2,6}, {1,5,6}.

			a(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.

Alois P. Heinz, Table of n, a(n) for n = 0..1023

Main diagonal of A376033.

Cf. A062383, A376697.

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-> b(n$2, 0):
seq(a(n), n=0..50);

a(2^n-1) = A376697(n).

A376921 Number T(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; triangle T(n,k), n>=0, 0<=k<=ceiling(2^(n-1))-1, read by rows.

Original entry on oeis.org

1, 2, 4, 3, 8, 5, 6, 4, 16, 8, 9, 6, 12, 7, 8, 5, 32, 13, 15, 9, 18, 11, 11, 7, 24, 11, 12, 8, 16, 9, 10, 6, 64, 21, 25, 13, 27, 16, 17, 10, 36, 17, 16, 11, 21, 12, 13, 8, 48, 18, 21, 12, 24, 15, 14, 9, 32, 14, 15, 10, 20, 11, 12, 7

Offset: 0

Alois P. Heinz, Oct 10 2024

For more information see A376033.

			Triangle T(n,k) begins:
   1;
   2;
   4,  3;
   8,  5,  6, 4;
  16,  8,  9, 6, 12,  7,  8, 5;
  32, 13, 15, 9, 18, 11, 11, 7, 24, 11, 12, 8, 16, 9, 10, 6;
  ...

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

Cf. A376033.

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:
T:= (n, k)-> b(n, k, 0):
seq(seq(T(n, k), k=0..ceil(2^(n-1))-1), n=0..7);

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

Original entry on oeis.org

1, 2, 4, 8, 12, 16, 21, 29, 45, 73, 117, 178, 260, 376, 552, 832, 1273, 1945, 2937, 4385, 6521, 9730, 14612, 22040, 33252, 50032, 75053, 112437, 168549, 253065, 380429, 572018, 859572, 1290664, 1937152, 2907744, 4366321, 6558769, 9853041, 14800001, 22226225

Offset: 0

Michael A. Allen, Feb 22 2022

			When n = 5, the 16 subsets are {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {3,5}, {4,5}, {1,2,3}, {2,3,4}, and {3,4,5}.

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

See A375981 for other sequences related to restricted combinations.

Column k=12 of A376033.

CoefficientList[Series[(1 + x + 2x^2 + 4x^3 + 4x^4 + 3x^5 + 2x^6)/(1 - x - x^5 - x^6 - 2*x^7),{x,0,35}],x]
LinearRecurrence[{1,0,0,0,1,1,2},{1,2,4,8,12,16,21},50] (* Harvey P. Dale, Mar 01 2023 *)

a(n) = a(n-1) + a(n-5) + a(n-6) + 2*a(n-7) + delta(n,0) + delta(n,1) + 2*delta(n,2) + 4*delta(n,3) + 4*delta(n,4) + 3*delta(n,5) + 2*delta(n,6).

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

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

Original entry on oeis.org

1, 2, 3, 5, 7, 9, 12, 16, 23, 33, 47, 66, 91, 126, 175, 245, 344, 482, 674, 940, 1311, 1830, 2557, 3575, 4997, 6982, 9752, 13620, 19025, 26579, 37136, 51885, 72487, 101264, 141463, 197624, 276088, 385711, 538860, 752810, 1051698, 1469249, 2052584, 2867532

Offset: 0

Michael A. Allen, Feb 22 2022

			When n = 5, the 9 subsets are {}, {1}, {2}, {3}, {4}, {5}, {1,3}, {2,4}, and {3,5}.

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

Column k=13 of A376033.

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

a(n) = a(n-1) + a(n-5) + a(n-7) + delta(n,0) + delta(n,1) + delta(n,2) + 2*delta(n,3) + 2*delta(n,4) + delta(n,5) + delta(n,6), a(n<0) = 0.

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

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

Original entry on oeis.org

1, 2, 3, 5, 8, 13, 18, 28, 41, 62, 91, 141, 208, 317, 473, 719, 1069, 1623, 2425, 3666, 5487, 8295, 12424, 18751, 28130, 42416, 63657, 95944, 144083, 217023, 326060, 490985, 737849, 1110753, 1669685, 2512993, 3778125, 5685594, 8549027, 12863637, 19344100, 29104549

Offset: 0

Michael A. Allen, Jul 18 2024

a(n) is the number of permutations of 0..n with each element moved by -1 to 1 places and every 5 consecutive elements having their maximum within 5 of their minimum.

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

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

Column k=17 of A376033.

CoefficientList[Series[(1 + 2*x + 2*x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 3*x^6 + 2*x^7 + x^8 + x^9)/(1 - x^2 - x^3 - x^4 + x^5 - x^6 - x^7 - x^8 - x^10),{x,0,41}],x]
LinearRecurrence[{0,1,1,1,-1,1,1,1,0,1},{1,2,3,5,8,13,18,28,41,62},50] (* Harvey P. Dale, Feb 15 2025 *)

a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-5) + a(n-6) + a(n-7) + a(n-8) + a(n-10) for n >= 10.

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

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

Original entry on oeis.org

1, 2, 4, 6, 9, 15, 21, 29, 45, 69, 100, 152, 236, 349, 517, 789, 1185, 1757, 2653, 4014, 5992, 8986, 13573, 20363, 30485, 45901, 69041, 103481, 155468, 233908, 351104, 527033, 792405, 1190493, 1787129, 2685209, 4035261, 6059758, 9101828, 13676670, 20544125

Offset: 0

Michael A. Allen, Sep 20 2024

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

Michael A. Allen, Combinations without specified separations, Communications in Combinatorics and Optimization (in press).
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,0,-1,1,2,-1,0,1,-1).
Index entries for subsets of {1,..,n} with disallowed differences

Column k=18 of A376033.

CoefficientList[Series[(1 + x + 2*x^2 + x^3 + x^4 + 3*x^5 + x^6 - x^7 - x^10)/(1 - x - x^3 + x^5 - x^6 - 2*x^7 + x^8 - x^10 + x^11),{x,0,39}],x]
LinearRecurrence[{1, 0, 1, 0, -1, 1, 2, -1, 0, 1, -1}, {1, 2, 4, 6, 9, 15, 21, 29, 45, 69, 100}, 39]

a(n) = a(n-1) + a(n-3) - a(n-5) + a(n-6) + 2*a(n-7) - a(n-8) + a(n-10) - a(n-11) for n >= 11.

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

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

Original entry on oeis.org

1, 2, 4, 8, 12, 18, 24, 34, 47, 73, 111, 177, 267, 409, 600, 900, 1324, 2004, 2996, 4564, 6848, 10377, 15513, 23385, 34953, 52685, 78969, 119138, 178840, 269604, 404656, 609310, 914548, 1376530, 2067231, 3111457, 4674751, 7034897, 10570855, 15903377, 23898528

Offset: 0

Michael A. Allen, Sep 20 2024

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

Michael A. Allen, Combinations without specified separations, Communications in Combinatorics and Optimization (in press).
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1,1,1,1,-1,-1,-1,-1).
Index entries for subsets of {1,..,n} with disallowed differences

Column k=20 of A376033.

CoefficientList[Series[(1 + x + x^2 + 3*x^3 + x^4 + x^5 - x^6 - 3*x^7 - 4*x^8 - 3*x^9 - 2*x^10 - x^11)/(1 - x - x^2 + x^3 - x^4 + x^5 - x^6 - x^7 - x^8 + x^9 + x^10 + x^11 + x^12),{x,0,38}],x]
LinearRecurrence[{1, 1, -1, 1, -1, 1, 1, 1, -1, -1, -1, -1}, {1, 2, 4, 8, 12, 18, 24, 34, 47, 73, 111, 177}, 39]

a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-4) - a(n-5) + a(n-6) + a(n-7) + a(n-8) - a(n-9) - a(n-10) - a(n-11) - a(n-12) for n >= 12.

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

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

Original entry on oeis.org

1, 2, 3, 4, 6, 9, 12, 17, 25, 35, 49, 71, 101, 142, 203, 290, 410, 583, 832, 1181, 1677, 2389, 3397, 4825, 6865, 9766, 13879, 19736, 28074, 39913, 56748, 80709, 114765, 163175, 232045, 329975, 469189, 667178, 948743, 1349062, 1918310, 2727839, 3878912, 5515657

Offset: 0

Michael A. Allen, Sep 21 2024

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

Michael A. Allen, Combinations without specified separations, Communications in Combinatorics and Optimization (in press).
Michael A. Allen, Connections between Combinations Without Specified Separations and Strongly Restricted Permutations, Compositions, and Bit Strings, arXiv:2409.00624 [math.CO], 2024.
Index entries for linear recurrences with constant coefficients, signature (1,0,1,0,-1,1).
Index entries for subsets of {1,..,n} with disallowed differences

Column k=19 of A376033.

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

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

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

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

cp's OEIS Frontend

A376697 Number of binary words of length 2^n-1 with at least n "0" between any two "1" digits.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A376091 Number 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 n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A376921 Number T(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; triangle T(n,k), n>=0, 0<=k<=ceiling(2^(n-1))-1, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs