Cuántas cadenas hay en un número finito de juego de poder?

Question

Deje $A$ ser un conjunto finito con $n$ elementos. Cuántas cadenas hay en $\mathcal P(A)$ - es decir, ¿cuántos subconjuntos de a $\mathcal P(A)$ son totalmente ordenado por inclusión?

Es bastante fácil calcular la máxima cadenas; hay $n!$ de ellos. Pero contando todas las cadenas que me pone en horrible inclusión-exclusión situaciones, incluso si trato de hacerlo a mano para las pequeñas $n$.

Por supuesto, esto también es el número de cadenas en un álgebra Booleana con $2^n$ elementos, o el número de cadenas en un número finito de celosía con $2^n$ elementos.

Por el lado de cálculo, el número de cadenas para $n$ ejecución de$0$$6$$2, 4, 12, 52, 300, 2164, 18732$. Esta secuencia parece ser desconocido en OEIS.

Answer 1

Excepto para los degenerados $n=0$ de los casos, el número de cadenas es $4$ veces $n$th Fubini número, A000670, también conocido como ordenó la Campana de los números.

Los enlaces de los artículos de Wikipedia listas de maneras diversas fórmulas para estos números, la más elemental de las que están en $$ a_n = \sum_{k=0}^n \sum_{j=0}^k (-1)^{k-j} \binom{k}{j}j^n \qquad\text{and}\qquad a_n \approx \frac{n!}{2(\log 2)^{n+1}}$$ (y a continuación el número de cadenas, a continuación,$4 a_n$).

El factor de $4$ tiene sentido; representa el hecho de que cada uno de $\varnothing$ $A$ puede ser omitido o incluidos en la cadena sin afectar su validez.