Número de formas de seleccionar subconjuntos

Question

De cuántas maneras pueden los dos distintos subconjuntos del conjunto $\text{A}$ de $k$ $(k \geq 3)$ los elementos se seleccionan de manera que tienen exactamente dos elementos comunes?

Empecé por la elección de dos elementos (que son comunes) en $\dbinom{k}{2}$ maneras. Para el resto de los elementos, supuse $x$ elementos en el subconjunto $\text{P}$ e $y$ elementos en el subconjunto $\text{Q}$. Luego me enteré de que el número de no-negativo integral de soluciones para la ecuación de $$x+y=k-2$$

que es igual a $\dbinom{k-2+2-1}{2-1} = \dbinom{k-1}{1} = k-1$

Por lo tanto, el número total de maneras de seleccionar subconjuntos $= \dbinom {k}{2} \times (k-1)$

Sin embargo, la respuesta dada en mi libro es $\dfrac{k(k-1)}{4} \cdot (3^{k-2}-1)$

Cualquier ayuda será apreciada.
Gracias.

Answer 1

Usted está asumiendo que todos los elementos de $A$ tiene que ser en un subconjunto o la otra, que no es necesario. Después de poner los dos elementos en ambos $P$ e $Q$, cada elemento puede ir en $P$, en $Q$, o ninguno de ellos de forma independiente. Que da un factor de $3$ para cada una de las $k-2$ resto de los elementos. Dividir por $2$ ya cuenta doble-cada asignación de los elementos a $P$ e $Q$ es contada de nuevo en la reversión de los dos conjuntos. El $-1$ viene porque no doulble contar el caso de que ambos $P$ e $Q$ están vacías. Yo se lo dejo a usted para ponerlo todo junto.

Answer 2

¿De cuántas maneras se pueden seleccionar dos subconjuntos distintos del conjunto A de k (k≥3) para que tengan exactamente dos elementos comunes?

Elija dos elementos para la intersección:$$\binom k2=\frac{k(k-1)}2$ $

Los elementos$k-2$ del resto tienen 3 opciones:$A-B,B-A,(A\cup B)'$ y menos para un caso donde todos van a$(A\cup B)'$ porque entonces$A=B$:$$3^{k-2}-1$ $

Como contamos:$(A,B)$ dos veces como$(A,B),(B,A)$, divida entre 2:$$T=\frac{k(k-1)}4(3^{k-2}-1)$ $