4 votos

Subconjuntos que difieren en al menos dos elementos

¿Tiene nombre o está investigado? Estaba intentando calcular algunos problemas de combinatoria y me encontré con un problema. No sé cómo calcular (en general) el número máximo de subconjuntos de k elementos, tal que cualquier par de estos subconjuntos difiere en al menos dos elementos.

Por ejemplo, $3$ -subconjuntos de elementos de $\{1,2,3,4,5\}$ con la propiedad anterior sólo son $2$ por ejemplo $\{1,2,3\}$ y $\{1,4,5\}$ . Sé que lo más probable es que sea complicado, porque según mis cálculos los subconjuntos de 3 elementos con esta propiedad para $n = 1 \text{ or } 3\mod 6$ resultó ser igual a $\frac {n \choose 2} 3$ . Y ya sé por qué (por si no me equivoco), y supongo que se debe a su conexión con ese tipo de álgebra que no sé cómo se llama, en la que dados dos elementos diferentes, el resultado de la operación es el tercero (por favor, decidme cómo se llama).

Pero esta igualdad no se aplica para otros números en caso de $3$ -porque no todos los pares de elementos determinan algún triplete. Y supongo que la complicación es mayor en el caso general de los subconjuntos de k elementos.

¿Es algo conocido y solucionable, algo conocido y que no tiene una forma general de calcularlo, o es un tema no investigado?

1voto

Misha Puntos 1723

Para $k$ -de elementos, esto se conoce en general como la función teórica de codificación $A(n, 4, k)$ : el número de palabras de código en $\{0,1\}^n$ con un peso constante $k$ y la distancia mínima $4$ .

Para $k=3$ Esta secuencia se puede encontrar en la OEIS en A001839 donde se da la siguiente fórmula cerrada: $$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}$$ Ver este índice para otras secuencias $A(n,d,w)$ en la OEIS.

El papel Nueva tabla de códigos de peso constante tiene una tabla de $A(n,4,w)$ para varios valores de $w$ . En particular, también sabemos que $$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}$$ siendo el valor exacto desconocido para $n \equiv 5 \pmod 6$ .

Es posible que haya fuentes más actualizadas, éste es sólo el documento citado en la entrada de la OEIS.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X