Abstract
We give new interpretations of Catalan and convoluted Catalan numbers in terms of trees and chain blockers. For a posetP we say that a subsetA ⊆P is a chain blocker if it is an inclusionwise minimal subset ofP that contains at least one element from every maximal chain. In particular, we study the set of chain blockers for the class of posetsP =Ca ×Cb whereCi is the chain 1 < ⋯ <i. We show that subclasses of these chain blockers are counted by Catalan and convoluted Catalan numbers.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
References
Catalan, E.: Sur les nombres de Segner. Rend. Circ. Mat. Palermo1, 190–201 (1887)
Foldes, S., Woodroofe, R.: Antichain cutsets of strongly connected posets. Order30, 351–361 (2013)
Regev, A.: A proof of Catalan’s convolution formula. Integers12, #A29 (2012)
Rival, I., Zaguia, N.: Antichain cutsets. Order1, 235247 (1985)
Stanley, R.P.: Catalan Numbers. Cambridge University Press, Cambridge (2015)
Tedfordm, S.J.: Combinatorial interpretations of convolutions of the Catalan numbers. Integers11, #A3 (2011)
West, J.: Generating trees and the Catalan and Schröder numbers. Discret. Math.146, 247–262 (1995)
Author information
Authors and Affiliations
COMSATS Institute of Information Technology, Lahore, Pakistan
Sarfraz Ahmad
Fachbereich Mathematik und Informatik, Philipps-Universität Marburg, 35032, Marburg, Germany
Volkmar Welker
- Sarfraz Ahmad
You can also search for this author inPubMed Google Scholar
- Volkmar Welker
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toSarfraz Ahmad.
Rights and permissions
About this article
Cite this article
Ahmad, S., Welker, V. Chain Blockers and Convoluted Catalan Numbers.Order33, 347–358 (2016). https://doi.org/10.1007/s11083-015-9370-z
Received:
Accepted:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative