About Warm-ups Problems News

Problem 9

Posted 05/08/2015
Refresh the webpage if formulas are not shown correctly.
----------------------
Previous    Next
----------------------

This problem is proposed by Ran Pan. If you want to submit your problem, please click here.

----------------------

It is well-known that the number of linear extensions of the following Hasse diagram is counted by Catalan number $C_n=\frac{1}{n+1}\binom{2n}{n}$.


Now we consider the number of linear extensions of following diagrams $D_n$. $D_1$, $D_2$ and $D_3$ are drawn as follows. One can easily figure out what $D_n$ looks like.


$a(n)$ is the number of linear extensions of $D_n$.

Find $a(n)$.




Back to top