Un interesante problema de combinatoria

Question

$A$ es un conjunto que contiene a $n$ elementos. Un subconjunto $P_1$ $A$ es elegido. El conjunto se reconstruye mediante la sustitución de los elementos de $P_1$. A continuación, un subconjunto $P_2$ es elegido y, de nuevo, el conjunto es reconstruido mediante la sustitución de los elementos de $P_2$. De esta manera $m$ subconjuntos $P_1,......,P_m$ son elegidos donde $m>1$. Encuentre el número de formas de elegir a $P_1,.......,P_m$ de manera tal que no hay dos de ellos son pares distintos.

No tengo ninguna idea de cómo empezar este problema He intentado un montón de cosas, pero no podía incluso llegar a una conclusión.

Editar

Básicamente reemplazo significa que los elementos que se han seleccionado para la Pi puede ser en cualquier otro subconjuntos de cualquier número de veces

Answer 1

Sugerencia: La siguiente reformulación del problema podría ser útil:

Considere la posibilidad de $(0,1)$-matrices con $m$ filas y $n$ columnas. Encontrar el número de $(0,1)$-matrices, de manera que por cada dos filas hay al menos una posición $j\ (1\leq j \leq n)$ donde ambas filas tienen un $1$ en esta posición.

Aquí vamos a considerar wlog $A=[n]=\{1,2,\ldots,n\}$ y codificar el subconjunto $\emptyset\ne P_k\subset A$ $k$- th $(1\leq k\leq m)$ fila. La posición $j$ $k$- ésima fila es $1$ fib $j\in P_k$.