Subsets differing in at least two elements

187 Views Asked by At

Does it have name or is it even researched. I was trying to calculate some combinatorial problems and ran into a problem. I do not know how to calculate (in general) the maximal number of k-element subsets, such that any pair of these subsets differs in at least two elements.

For example, $3$-element subsets of $\{1,2,3,4,5\}$ with the above property are only $2$, for instance $\{1,2,3\}$ and $\{1,4,5\}$. I know it is going to be most likely complicated, because by my calculations 3-element subsets with this property for $n = 1 \text{ or } 3\mod 6$ turned out to be equal to $\frac {n \choose 2} 3$. And I know why (in case I am not wrong), and I guess it is due to its connection to that type of algebra I do not know the name of, where given two different elements, the result of the operation is the third one (please tell me how is it called).

But this equality does not apply for other numbers in case of $3$-element subsets, because not every pair of elements determines some triplet. And more complication I guess arises in general case of k-element subsets.

Is it something known and solvable, something known and not having a general way of computing it, or is it a not researched topic?

1

There are 1 best solutions below

1
On BEST ANSWER

For $k$-element subsets, this is in general known as the coding-theoretic function $A(n, 4, k)$: the number of codewords in $\{0,1\}^n$ with constant weight $k$ and minimum distance $4$.

For $k=3$, you can find this sequence in the OEIS under A001839 where the following closed formula is given: $$A(n,4,3) = \begin{cases}\left\lfloor \frac n3 \left\lfloor \frac{n-1}{2}\right\rfloor\right\rfloor - 1 & n \equiv 5 \pmod 6 \\ \left\lfloor \frac n3 \left\lfloor \frac{n-1}{2}\right\rfloor\right\rfloor & n \not\equiv 5 \pmod 6 \end{cases}$$ See this index for several other sequences $A(n,d,w)$ in the OEIS.

The paper New table of constant weight codes has a table of $A(n,4,w)$ for various values of $w$. In particular, we also know that $$A(n,4,4) = \begin{cases} \frac{n(n-1)(n-2)}{24} & n \equiv 2,4 \pmod 6 \\ \frac{n(n-1)(n-3)}{24} & n \equiv 1,3 \pmod 6 \\ \frac{n(n^2-3n-6)}{24} & n \equiv 0 \pmod 6 \end{cases}$$ with the exact value being known for $n \equiv 5 \pmod 6$.

It's possible that there are more up-to-date sources, this is just the paper cited in the OEIS entry.