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
Alois P. Heinz, Antidiagonals n = 0..200, flattened
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.
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.
KEYWORD
AUTHOR
Alois P. Heinz, Sep 09 2024
STATUS
approved