Como sugiere el título:
¿Cuál es el número máximo de tamaño de $k$ subconjuntos de a $[1, \dots, n]$ son tales que no subconjuntos se superponen en más de $e$ elementos?
Yo sólo se preocupan realmente de la asymptotics, por lo que una respuesta que es correcta hasta factores constantes está bien.
Para $k \le e$, de todos los posibles subconjuntos de calificar, ${n \choose k}$
Para $k = e+1$, todos los posibles subconjuntos de nuevo calificar debido a que los conjuntos son distintos, por tanto, comparten en la mayoría de las $e$ elementos, ${n \choose e+1}$
Para $e+1< k \le \frac{n+e}{2}$, cada subconjunto se utiliza un número de la $e+1$ de los casos, por lo que el total es más bajo por lo menos ese factor:
$$|\text{subconjuntos}| \le \left\lfloor \frac{n \elegir e+1}{k\elegir e+1} \right\rfloor = \left\lfloor \frac{n!(e+1)!(k-e-1)!}{(e+1)!(n-e-1)!k!} \right\rfloor = \left\lfloor \frac{n!(k-e-1)!}{(n-e-1)!k!} \right\rfloor$$
Para $k \gt \frac{n+e}{2}$, cualquiera de los dos subconjuntos se repartirán más de $e$ elementos tan sólo $1$ tal subconjunto puede ser elegido.
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.
