login
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.
15
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,3
COMMENTS
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)).
LINKS
FORMULA
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).
EXAMPLE
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, ...
MAPLE
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);
PROG
(PARI)
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
CROSSREFS
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.
Sequence in context: A253572 A141539 A340547 * A327844 A243851 A168266
KEYWORD
nonn,tabl,base
AUTHOR
Alois P. Heinz, Sep 09 2024
STATUS
approved