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

A263693 T(n,k)=Number of length n arrays of permutations of 0..n-1 with each element moved by -k to k places and every three consecutive elements having its maximum within 3 of its minimum.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 2, 6, 5, 1, 2, 6, 14, 7, 1, 2, 6, 24, 14, 11, 1, 2, 6, 24, 18, 16, 16, 1, 2, 6, 24, 36, 18, 22, 25, 1, 2, 6, 24, 36, 20, 24, 36, 37, 1, 2, 6, 24, 36, 36, 24, 40, 56, 57, 1, 2, 6, 24, 36, 36, 27, 40, 64, 85, 85, 1, 2, 6, 24, 36, 36, 48, 40, 64, 100, 125, 130, 1, 2, 6, 24, 36

Offset: 1

R. H. Hardin, Oct 23 2015

Table starts
...1...1...1...1...1...1...1...1...1...1...1...1...1...1...1...1...1...1...1
...2...2...2...2...2...2...2...2...2...2...2...2...2...2...2...2...2...2...2
...3...6...6...6...6...6...6...6...6...6...6...6...6...6...6...6...6...6...6
...5..14..24..24..24..24..24..24..24..24..24..24..24..24..24..24..24..24..24
...7..14..18..36..36..36..36..36..36..36..36..36..36..36..36..36..36..36..36
..11..16..18..20..36..36..36..36..36..36..36..36..36..36..36..36..36..36..36
..16..22..24..24..27..48..48..48..48..48..48..48..48..48..48..48..48..48..48
..25..36..40..40..40..49..80..80..80..80..80..80..80..80..80..80..80..80..80
..37..56..64..64..64..64..76.128.128.128.128.128.128.128.128.128.128.128.128
..57..85.100.100.100.100.100.120.200.200.200.200.200.200.200.200.200.200.200
..85.125.144.144.144.144.144.144.168.288.288.288.288.288.288.288.288.288.288
.130.189.216.216.216.216.216.216.216.256.432.432.432.432.432.432.432.432.432
.195.285.324.324.324.324.324.324.324.324.380.648.648.648.648.648.648.648.648

			Some solutions for n=7 k=4
..1....0....0....3....1....0....0....0....0....0....0....0....1....0....1....2
..0....2....1....0....0....1....1....1....1....2....1....2....0....1....0....0
..2....1....2....1....3....2....2....2....2....1....2....1....2....2....3....1
..3....3....3....2....2....4....3....4....3....3....4....4....3....4....2....3
..4....4....4....4....4....3....5....5....4....4....3....3....5....5....5....4
..6....5....6....5....5....6....4....6....5....6....5....6....6....3....4....6
..5....6....5....6....6....5....6....3....6....5....6....5....4....6....6....5

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

Column 1 is A130137(n-1).

Empirical for diagonal: a(n) = a(n-1) +a(n-2) -a(n-3) +a(n-4) for n>12
Empirical for column k:
k=1: a(n) = a(n-1) +a(n-2) -a(n-3) +a(n-4)
k=2: a(n) = a(n-1) +a(n-2) -a(n-3) +a(n-4) for n>12
k=3: a(n) = a(n-1) +a(n-2) -a(n-3) +a(n-4) for n>12
k=4: a(n) = a(n-1) +a(n-2) -a(n-3) +a(n-4) for n>12
k=5: a(n) = a(n-1) +a(n-2) -a(n-3) +a(n-4) for n>12
k=6: a(n) = a(n-1) +a(n-2) -a(n-3) +a(n-4) for n>12
k=7: a(n) = a(n-1) +a(n-2) -a(n-3) +a(n-4) for n>13

A130136 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k 0110's (n>=0, 0<=k<=floor((n-1)/3)). A Fibonacci binary word is a binary word having no 00 subword.

Original entry on oeis.org

1, 2, 3, 5, 7, 1, 11, 2, 16, 5, 25, 8, 1, 37, 16, 2, 57, 26, 6, 85, 48, 10, 1, 130, 78, 23, 2, 195, 136, 39, 7, 297, 220, 80, 12, 1, 447, 371, 136, 31, 2, 679, 598, 258, 54, 8, 1024, 987, 437, 121, 14, 1, 1553, 1584, 790, 212, 40, 2, 2345, 2576, 1332, 432, 71, 9, 3553

Offset: 0

Emeric Deutsch, May 13 2007

Row n has 1+floor((n-1)/3) terms. Row sums are the Fibonacci numbers (A000045).

			T(8,2)=2 because we have 01101101 and 10110110.
Triangle starts:
   1;
   2;
   3;
   5;
   7, 1;
  11, 2;
  16, 5;
  25, 8, 1;
  ...

Cf. A000045, A001629, A130137.

G:=(1+z+z^3-t*z^3)/(1-z-z^2+z^3-t*z^3-z^4+t*z^4): Gser:=simplify(series(G,z=0,23)): for n from 0 to 23 do P[n]:=sort(coeff(Gser,z,n)) od: 1; for n from 1 to 20 do seq(coeff(P[n],t,j),j=0..floor((n-1)/3)) od; # yields sequence in triangular form

gf = (1 + z + (1-t) z^3)/(1 - z - z^2 + (1-t) z^3 - (1-t) z^4);
CoefficientList[#, t]& /@ CoefficientList[gf + O[z]^20, z] // Flatten (* Jean-François Alcover, Aug 25 2021 *)

G.f.: G(t,z) = (1+z+(1-t)z^3)/(1-z-z^2+(1-t)z^3-(1-t)z^4).
T(n,0) = A130137(n).
Sum_{k>=0} k*T(n,k) = A001629(n-2) (n>=2).

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

A263693 T(n,k)=Number of length n arrays of permutations of 0..n-1 with each element moved by -k to k places and every three consecutive elements having its maximum within 3 of its minimum.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A130136 Triangle read by rows: T(n,k) is the number of Fibonacci binary words of length n and having k 0110's (n>=0, 0<=k<=floor((n-1)/3)). A Fibonacci binary word is a binary word having no 00 subword.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula