A373005 - OEIS

%I #15 May 27 2024 15:47:48

%S 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,

%T 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,

%U 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

%N 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.

%C 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.

%H Noga Alon, Zhihan Jin, and Benny Sudakov, <a href="https://arxiv.org/abs/2405.10275">The Helly number of Hamming balls and related problems</a>, arXiv:2405.10275 [math.CO], 2024. See p. 3.

%H 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 <a href="https://www.researchgate.net/publication/2284223_Specification_of_all_Maximal_Subsets_of_the_Hamming_Space_with_Respect_to_Given_Diameter">ResearchGate</a>.

%H G. Katona, <a href="https://doi.org/10.1007/BF01897141">Intersection theorems for systems of finite sets</a>, Acta Mathematica Academiae Scientiarum Hungaricae 15, 329-337 (1964).

%H Daniel J. Kleitman, <a href="https://doi.org/10.1016/S0021-9800(66)80027-3">On a combinatorial conjecture of Erdös</a>, Journal of Combinatorial Theory, Series A 1, 209-214, (1966).

%F A(n,k) = Sum_{i=0..(k-1)/2} binomial(n,i) if k is odd;

%F A(n,k) = binomial(n-1,k/2-1) + Sum_{i=0..k/2-1} binomial(n,i) if k is even.

%F A(n,3) = n+1.

%F A(n,6) = A014206(n-1).

%F A(n,9) = A000127(n+1).

%F A(n,10) = A059173(n) for n > 0.

%F A(n,12) = A059174(n) for n > 0.

%F A(0,k) = A007877(k) for k > 0.

%e The array begins:

%e   1, 1, 2, 1,  0,  1,  2,  1, ...

%e   0, 1, 2, 2,  2,  2,  2,  2, ...

%e   0, 1, 2, 3,  4,  4,  4,  4, ...

%e   0, 1, 2, 4,  6,  7,  8,  8, ...

%e   0, 1, 2, 5,  8, 11, 14, 15, ...

%e   0, 1, 2, 6, 10, 16, 22, 26, ...

%e   0, 1, 2, 7, 12, 22, 32, 42, ...

%e   0, 1, 2, 8, 14, 29, 44, 64, ...

%e   ...

%t 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

%Y 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).

%K nonn,tabl

%O 0,6

%A _Stefano Spezia_, May 19 2024