A141539 -id:A141539 - 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).

A143291 Triangle T(n,k), n>=2, 0<=k<=n-2, read by rows: numbers of binary words of length n containing at least one subword 10^{k}1 and no subwords 10^{i}1 with i

Original entry on oeis.org

1, 3, 1, 8, 2, 1, 19, 4, 2, 1, 43, 8, 3, 2, 1, 94, 15, 5, 3, 2, 1, 201, 27, 9, 4, 3, 2, 1, 423, 48, 15, 6, 4, 3, 2, 1, 880, 84, 24, 10, 5, 4, 3, 2, 1, 1815, 145, 38, 16, 7, 5, 4, 3, 2, 1, 3719, 248, 60, 24, 11, 6, 5, 4, 3, 2, 1, 7582, 421, 94, 35, 17, 8, 6, 5, 4, 3, 2, 1, 15397, 710, 146, 51, 25, 12, 7, 6, 5, 4, 3, 2, 1

Offset: 2

Alois P. Heinz, Aug 04 2008

T(n,k) = number of subset S of {1,2,...,n+1} such that |S| > 1 and min(S*) = k, where S* is the set {x(2)-x(1), x(3)-x(2), ..., x(h+1)-x(h)} when the elements of S are written as x(1) < x(2) < ... < x(h+1); if max(S*) is used in place of min(S*), the result is the array at A255874. - Clark Kimberling, Mar 08 2015

			T (5,1) = 4, because there are 4 words of length 5 containing at least one subword 101 and no subword 11: 00101, 01010, 10100, 10101.
Triangle begins:
    1;
    3,  1;
    8,  2,  1;
   19,  4,  2, 1;
   43,  8,  3, 2, 1;
   94, 15,  5, 3, 2, 1;
  201, 27,  9, 4, 3, 2, 1;
  423, 48, 15, 6, 4, 3, 2, 1;

Alois P. Heinz, Rows n = 2..142, flattened

Columns k=0-10 give: A008466, A143281, A143282, A143283, A143284, A143285, A143286, A143287, A143288, A143289, A143290.
Row sums are in A000295.
Cf. A141539.

R:= PowerSeriesRing(Integers(), 50);
A143291:= func< n,k | Coefficient(R!( x^k/((x^(k-1) +x-1)*(x^k +x-1)) ), n) >;
[A143291(n,k): k in [2..n], n in [2..12]]; // G. C. Greubel, Jun 01 2025

as:= proc (n, k) option remember;
       if k=0 then 2^n
     elif n<=k and n>=0 then n+1
     elif n>0 then as(n-1, k) +as(n-k-1, k)
     else as(n+1+k, k) -as(n+k, k)
       fi
     end:
T:= (n, k)-> as(n, k) -as(n, k+1):
seq(seq(T(n, k), k=0..n-2), n=2..15);

as[n_, k_] := as[n, k] = Which[ k == 0, 2^n, n <= k && n >= 0, n+1, n > 0, as[n-1, k] + as[n-k-1, k], True, as[n+1+k, k] - as[n+k, k] ]; t [n_, k_] := as[n, k] - as[n, k+1]; Table[Table[t[n, k], {k, 0, n-2}], {n, 2, 14}] // Flatten (* Jean-François Alcover, Dec 11 2013, translated from Maple *)

@CachedFunction
def b(n,k):
    if k==0: return 2^n
    elif n <= k and n>=0: return n+1
    elif n>0: return b(n-1,k) + b(n-k-1,k)
    else: return b(n+k+1,k) - b(n+k,k)
def A143291(n,k): return b(n,k) - b(n,k+1)
print(flatten([[A143291(n,k) for k in range(n-1)] for n in range(2,16)])) # G. C. Greubel, Jun 01 2025

G.f. of column k: x^(k+2) / ((x^(k+1)+x-1)*(x^(k+2)+x-1)).

A145111 Square array A(n,k) of numbers of length n binary words with fewer than k 0-digits between any pair of consecutive 1-digits (n,k >= 0), read by antidiagonals.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 2, 4, 4, 1, 2, 4, 7, 5, 1, 2, 4, 8, 11, 6, 1, 2, 4, 8, 15, 16, 7, 1, 2, 4, 8, 16, 27, 22, 8, 1, 2, 4, 8, 16, 31, 47, 29, 9, 1, 2, 4, 8, 16, 32, 59, 80, 37, 10, 1, 2, 4, 8, 16, 32, 63, 111, 134, 46, 11, 1, 2, 4, 8, 16, 32, 64, 123, 207, 222, 56, 12, 1, 2, 4, 8, 16, 32, 64, 127, 239, 384, 365, 67, 13

Offset: 0

Alois P. Heinz, Oct 02 2008

			A(4,1) = 11, because 11 binary words of length 4 have fewer than 1 0-digit between any pair of consecutive 1-digits: 0000, 0001, 0010, 0100, 1000, 0011, 0110, 1100, 0111, 1110, 1111.
Square array A(n,k) begins:
  1,  1,  1,  1,  1,  1, ...
  2,  2,  2,  2,  2,  2, ...
  3,  4,  4,  4,  4,  4, ...
  4,  7,  8,  8,  8,  8, ...
  5, 11, 15, 16, 16, 16, ...
  6, 16, 27, 31, 32, 32, ...

Alois P. Heinz, Antidiagonals n = 0..140

Columns 0-9 give: A000027(n+1), A000124, A000126(n+1), A007800(n+1), A145112, A145113, A145114, A145115, A145116, A145117.
Main diagonal gives A000079.
Cf. A141539.

f:= proc(n,k) option remember; local j; if n=0 then 1 elif n<=k then 2^(n-1) else add(f(n-j, k), j=1..k) fi end: g:= proc(n,k) option remember; if n<0 then 0 else g(n-1,k) +f(n,k) fi end: A:= (n,k)-> `if`(n=0, g(0,k), A(n-1,k) +g(n-1,k)): seq(seq(A(n, d-n), n=0..d), d=0..14);

a[n_, k_] := SeriesCoefficient[(1 - x + x^(k+1))/(1 - 3*x + 2*x^2 + x^(k+1) - x^(k+2)), {x, 0, n}]; a[0, ] = 1; Table[a[n-k, k], {n, 0, 14}, {k, n, 0, -1}] // Flatten (* _Jean-François Alcover, Jan 15 2014 *)

G.f. of column k: (1-x+x^(k+1))/(1-3*x+2*x^2+x^(k+1)-x^(k+2)).

A017907 Expansion of 1/(1 - x^13 - x^14 - ...).

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 19, 23, 28, 34, 41, 49, 58, 68, 79, 91, 104, 118, 134, 153, 176, 204, 238, 279, 328, 386, 454, 533, 624, 728, 846, 980, 1133, 1309

Offset: 0

N. J. A. Sloane

a(n) = number of compositions of n in which each part is >= 13. - Milan Janjic, Jun 28 2010

a(n+25) equals the number of binary words of length n having at least 12 zeros between every two successive ones. - Milan Janjic, Feb 09 2015

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

Column k=12 of A141539, k=13 of A220122. - Alois P. Heinz, Dec 09 2012

a:= n-> (Matrix(13, (i,j)-> if (i=j-1) then 1 elif j=1 then [1, 0$11, 1][i] else 0 fi)^n)[13,13]: seq(a(n), n=0..80); # Alois P. Heinz, Aug 04 2008

LinearRecurrence[{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 17 2012 *)
CoefficientList[Series[(x-1)/(x-1+x^13),{x,0,70}],x] (* Harvey P. Dale, Feb 07 2015 *)

Vec((x-1)/(x-1+x^13)+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

G.f.: (x-1)/(x-1+x^13). - Alois P. Heinz, Aug 04 2008
For positive integers n and k such that k <= n <= 13*k, and 12 divides n-k, define c(n,k) = binomial(k,(n-k)/12), and c(n,k) = 0, otherwise. Then, for n>=1,  a(n+13) = sum(c(n,k), k=1..n). - Milan Janjic, Dec 09 2011
a(0)=1, a(1)=0, a(2)=0, a(3)=0, a(4)=0, a(5)=0, a(6)=0, a(7)=0, a(8)=0, a(9)=0, a(10)=0, a(11)=0, a(12)=0, a(n)=a(n-1)+a(n-13). - Harvey P. Dale, Feb 07 2015

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

Original entry on oeis.org

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

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

A143291 Triangle T(n,k), n>=2, 0<=k<=n-2, read by rows: numbers of binary words of length n containing at least one subword 10^{k}1 and no subwords 10^{i}1 with i

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A145111 Square array A(n,k) of numbers of length n binary words with fewer than k 0-digits between any pair of consecutive 1-digits (n,k >= 0), read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A017907 Expansion of 1/(1 - x^13 - x^14 - ...).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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