|
|
A373005
|
|
Array read by ascending antidiagonals: A(n,k) is the maximum possible cardinality of a set of points of diameter at most k-1 in {0,1}^n.
|
|
1
|
|
|
1, 0, 1, 0, 1, 2, 0, 1, 2, 1, 0, 1, 2, 2, 0, 0, 1, 2, 3, 2, 1, 0, 1, 2, 4, 4, 2, 2, 0, 1, 2, 5, 6, 4, 2, 1, 0, 1, 2, 6, 8, 7, 4, 2, 0, 0, 1, 2, 7, 10, 11, 8, 4, 2, 1, 0, 1, 2, 8, 12, 16, 14, 8, 4, 2, 2, 0, 1, 2, 9, 14, 22, 22, 15, 8, 4, 2, 1, 0, 1, 2, 10, 16, 29, 32, 26, 16, 8, 4, 2, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
A(n,k) is also the size of the Hamming ball in {0,1}^n of radius (k-1)/2 if k is odd and of the union of two Hamming balls in {0,1}^n of radius k/2-1 whose centers are of Hamming distance 1 if k is even.
|
|
LINKS
|
S. L. Bezrukov, Specification of all maximal subsets of the unit cube with respect to given diameter. Problemy Peredachi Informatsii, pages 106-109, 1987. On ResearchGate.
|
|
FORMULA
|
A(n,k) = Sum_{i=0..(k-1)/2} binomial(n,i) if k is odd;
A(n,k) = binomial(n-1,k/2-1) + Sum_{i=0..k/2-1} binomial(n,i) if k is even.
A(n,3) = n+1.
|
|
EXAMPLE
|
The array begins:
1, 1, 2, 1, 0, 1, 2, 1, ...
0, 1, 2, 2, 2, 2, 2, 2, ...
0, 1, 2, 3, 4, 4, 4, 4, ...
0, 1, 2, 4, 6, 7, 8, 8, ...
0, 1, 2, 5, 8, 11, 14, 15, ...
0, 1, 2, 6, 10, 16, 22, 26, ...
0, 1, 2, 7, 12, 22, 32, 42, ...
0, 1, 2, 8, 14, 29, 44, 64, ...
...
|
|
MATHEMATICA
|
A[n_, k_]:=If[OddQ[k], Sum[Binomial[n, i], {i, 0, (k-1)/2}], Binomial[n-1, k/2-1]+Sum[Binomial[n, i], {i, 0, k/2-1}]]; Table[A[n-k, k], {n, 0, 12}, {k, 0, n}]//Flatten
|
|
CROSSREFS
|
Cf. A000007 (k=0), A000012 (k=1), A000124 (k=5), A000125 (k=7), A005843 (k=4), A006261 (k=11), A007395 (k=2), A008859 (k=13), A011782 (main diagonal), A014206, A046127 (k=8), A059173, A059174, A130130 (n=1), A158411 (n=2), A373006 (antidiagonal sums).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|