Contando las funciones de $A$ $\mathcal{P}(B)$cubriendo $B$

Question

La pregunta es, ¿cuántas funciones hay de $A$ $\mathcal{P}(B)$tal que $$\bigcup_{x\in A} f(x) = B.$$ de Ambos conjuntos son finitos. La única manera que se me ocurre es la de contar con la mano (los pequeños conjuntos en mi caso), pero me preguntaba si este es un problema conocido con un conocido de la solución.

Otra manera de plantear el problema es: Contar el número de membranas que recubren el conjunto de $B$ con exactamente $N$ etiquetado subconjuntos (donde $N$ es el tamaño de $A$), pero no veo que ayudar porque entonces uno tiene que comenzar a contar de permutaciones y los casos en que dos subconjuntos son repetidos, etc.

Parece relacionado con el conjunto cubren problema y la máxima cobertura problema, y he leído esta pregunta que también está relacionado, pero pensé que tal vez mi versión es un poco más fácil/más difícil?

Me acaba de llegar con una posibilidad para una recursividad: $n_{A,B} = |A|^{2^{|B|}} - \sum_{S\subset B} n_{A,B/S}$. Hace que el sonido de la derecha? Última edición: No... todavía estoy repitiendo subconjuntos de todas partes.

Muchas gracias por su ayuda!

Answer 1

Tome $y\in B$$C_y=\{x\in A:y\in f(x)\}$, que es un subconjunto de a $A$

A continuación, observe que la única indeseables caso es $C_y=\emptyset$, sólo en ese caso, tendrás $y\notin \bigcup_{x\in A}f(x)$. Así que usted puede eligió $C_y$ $2^{|A|}-1$ maneras.

Repita esto para todos los $y\in B$ y usted recibirá su número es

$$\left(2^{|A|}-1\right)^{|B|}$$

EDIT: Para explicarlo en palabras, cada elemento de a $B$ tiene que ser cubierta por $f$ de cada elemento de un no-vacío subconjunto de elementos de $A$, y la elección de estos no vacía de subconjuntos de forma exclusiva define $f$