¿De cuántas formas se puede distribuir un par sobre un conjunto?

Question

Supongamos un conjunto $S$ de tamaño $n$. Sea $P$ el conjunto de todos los pares de $S$ tales que un elemento solo puede ser pareado con $k$ otros elementos. Por lo tanto, el tamaño de $P$ es $\frac{nk}{2}$.

La pregunta es: ¿cuántos subconjuntos de $S$, de tamaño $g$, contienen al menos un elemento de $P$?

Al principio intenté $$ \frac{\frac{nk}{2} \binom{n-2}{g-2}}{\binom{g}{2}} $$

Y mi razonamiento fue: selecciono un par de $P$ y lo combino con todos los subconjuntos de $S$ de tamaño $g-2$, que no contienen ninguno de los dos elementos ya seleccionados, para crear un subconjunto de tamaño $g$. Luego divido por $\binom{g}{2}$ porque es el número de permutaciones del par en el subconjunto creado.

Sin embargo, me di cuenta de que estaba equivocado porque $\binom{g}{2}$ no representa el número correcto de permutaciones del par, y ahora realmente no sé cómo debería calcular este número.

Cualquier ayuda es apreciada. Gracias de antemano

Answer 1

No hay información suficiente para responder a la pregunta. Por ejemplo, supongamos que $n=6$, $k=2$, $g=3$. Entonces:

• Una elección posible de $P$ es $\{\{1,2\}, \{1,3\}, \{2,3\}, \{4,5\}, \{4,6\}, \{5,6\}\}$. En este caso, de los $\binom 63 = 20$ subconjuntos $A \subseteq S$ de tamaño $3$, todos los $20$ deben contener un elemento de $P$: cualquier $A$ contiene al menos dos de $\{1,2,3\}$ (y contiene uno de los primeros tres elementos de $P$) o al menos dos de $\{4,5,6\}$ (y contiene uno de los últimos tres elementos de $P$).
• Otra elección posible de $P$ es $\{\{1,2\}, \{2,3\}, \{3,4\},\{4,5\}, \{5,6\},\{1,6\}\}$. En este caso, de los $\binom 63 = 20$ subconjuntos $A \subseteq S$ de tamaño $3$, solo $18$ contienen un elemento de $P$: las excepciones son $\{1,3,5\}$ y $\{2,4,6\}$.

La respuesta depende de la estructura de $P$, no solo del tamaño de $P$, ni siquiera de cuántos pares contienen cada elemento.