This question already has an answer here:

I found that problem and I could use some help.

I have a partial order $(2^S,⊆)$ and |S| = n.

How many different chains are there in that poset?

If I had the Hasse diagram or knew the elements of S it would be easy to find out.

But now with knowing just that |S| = n I have absolutely no idea.

Could anyone help and provide a methodology?



marked as duplicate by Henning Makholm, hardmath, Edward Jiang, user228113, Shailesh Jun 22 '16 at 0:16

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Hi and thanks for answering. That was all the information. It was asking for the "best answer you can give" so I guess it doesn't require a specific one. Since I am new to all that, could you explain why $2^n$ and $2^2^n$ ? $\endgroup$ – Yannis Krz Jun 21 '16 at 15:00
  • 1
    $\begingroup$ @SeanEnglish: The problem seems to be fully specified to me, and it is certainly solvable. At worst, enumerate all the $2^{2^n}$ subsets of $\mathcal P(S)$ and check which of them are chains. $\endgroup$ – Henning Makholm Jun 21 '16 at 15:00
  • $\begingroup$ @HenningMakholm You are right, sorry I didn't see that it was normal inclusion. I was thinking it was an arbitrary ordering on $2^S$, not set-inclusion. My bad! $\endgroup$ – Sean English Jun 21 '16 at 15:06
  • 4
    $\begingroup$ Hmm, it turns out I've asked (and answered) this myself before: How many chains are there in a finite power set? $\endgroup$ – Henning Makholm Jun 21 '16 at 18:17

Let $N^a_b$ mean the number of chains of length exactly $b$ in $\mathcal P(\{1,\ldots,a\})$.

Then the recurrence relation $$ 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} $$ can now be used to compute other $N^a_b$ with relatively little effort.

  • $\begingroup$ So, there will be $2^{2^n}$ subsets but only some of them will be chains. And if I wanted to find out how many exactly I would have to use the relation you mentioned in each one of them? $\endgroup$ – Yannis Krz Jun 21 '16 at 15:32
  • $\begingroup$ @Fandom: Right. The recurrence is my best suggestion for how to count the chains, but possibly someone else can think of something cleverer. :-) $\endgroup$ – Henning Makholm Jun 21 '16 at 15:52
  • $\begingroup$ I see. I guess they don't want a specific answer like "5 chains". Probably it's a more theoretical problem and the best answer would be something like: $2^n <= number of chains <= 2^{2^n}$ and the number can be found by enumerating the subsets and counting the chains. Thanks for the help :) $\endgroup$ – Yannis Krz Jun 21 '16 at 16:04
  • $\begingroup$ Something doesn't seem right. At the other link you say "Except for the degenerate n=0 case, the number of chains is 4 times the nth Fubini number". If $|S|=1$ you get {} and ${a}$. That gives the chains {}, {a}, {{},{a}}. Damn I need a better book. $\endgroup$ – Yannis Krz Jun 21 '16 at 18:49
  • $\begingroup$ @Fandom: If $S=\{a\}$, then the four chains are: $\varnothing, \{\varnothing\}, \{S\}$, and $\{\varnothing,S\}$. On the other hand, your $\{a\}$ is not a chain: it is not even a subset of $\mathcal P(S)$ because its element $a$ is not a subset of $S$. $\endgroup$ – Henning Makholm Jun 21 '16 at 19:06

The notation $(2^S,\subset)$ means the points in your partial order are the elements of $2^S$, the power set of $S$, which is the set of all subsets of $S$. The subsets are ordered so that if $X\subset S$ and $Y\subset S$ then $X\le Y$ if $X\subset Y$. The number of chains is the number of sequences of distinct subsets $T_i$ of $S$ we can find where $T_1\subset T_2\subset\cdots\subset T_k$ for some $1\le k\le n$. You should be able to draw the Hasse diagram for some small examples.

  • $\begingroup$ Thanks for answering. So, let's say that $S={a,b,c}$. So $2^S=8$ and my nodes would be {},{a},{b},{c},{a,b},{b,c},{a,c}{a,b,c}. All my chains would be {},{a}, {b}, {c}, {{a},{a,b}}, {{a},{a,b}, {a,b,c}}, {{b,c},{a,b,c}}...etc up to 256 chains? $\endgroup$ – Yannis Krz Jun 21 '16 at 15:17
  • $\begingroup$ @Fandom: You wont, get 256 chains, because some of the $256$ subsets of $\mathcal P(S)$, such as $\{\{a\},\{b,c\}\}$ are not chains. $\endgroup$ – Henning Makholm Jun 21 '16 at 15:19
  • $\begingroup$ You've also forgotten for instance the chain {{}, {a}} in your tally above. $\endgroup$ – Steven Stadnicki Jun 21 '16 at 15:20
  • $\begingroup$ @StevenStadnicki Yeah, I know. I wasn't writing them in order. I was trying to include more different subsets. $\endgroup$ – Yannis Krz Jun 21 '16 at 15:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.