¿Cuántas cadenas diferentes hay en un Poset?

Question

He encontrado ese problema y me vendría bien algo de ayuda.

Tengo un pedido parcial $(2^S,)$ y |S| = n.

¿Cuántas cadenas diferentes hay en ese conjunto?

Si tuviera el diagrama de Hasse o conociera los elementos de S sería fácil averiguarlo.

Pero ahora con saber sólo que |S| = n no tengo ni idea.

¿Podría alguien ayudar y proporcionar una metodología?

Gracias

Answer 1

La notación $(2^S,\subset)$ significa que los puntos de su orden parcial son los elementos de $2^S$ el conjunto de potencias de $S$ que es el conjunto de todos los subconjuntos de $S$ . Los subconjuntos se ordenan de manera que si $X\subset S$ y $Y\subset S$ entonces $X\le Y$ si $X\subset Y$ . El número de cadenas es el número de secuencias de subconjuntos distintos $T_i$ de $S$ podemos encontrar donde $T_1\subset T_2\subset\cdots\subset T_k$ para algunos $1\le k\le n$ . Deberías ser capaz de dibujar el diagrama de Hasse para algunos pequeños ejemplos.

Answer 2

Dejemos que $N^a_b$ significa el número de cadenas de longitud exacta $b$ en $\mathcal P(\{1,\ldots,a\})$ .

Entonces la relación de recurrencia $$N^0_b = \begin{cases} 1 & \text{when }b\in\{0,1\} \\ 0 & \text{otherwise} \end{cases} \\ N^{a+1}_b = (b+1)N^a_b + (b-1)N^a_{b-1}$$ puede utilizarse ahora para calcular otros $N^a_b$ con relativamente poco esfuerzo.