Mathematics – Combinatorics
Scientific paper
2010-06-15
Mathematics
Combinatorics
Scientific paper
We show that two classes of combinatorial objects--inversion tables with no subsequence of decreasing consecutive numbers and matchings with no 2-nestings--are enumerated by the Fishburn numbers. In particular, we give a simple bijection between matchings with no 2-nestings and inversion tables with no subsequence of decreasing consecutive numbers. We then prove using the involution principle that inversion tables with no subsequence of decreasing consecutive numbers have the same generating function as the Fishburn numbers. The Fishburn numbers have previously been shown by Bousquet-M\'elou, Claesson, Dukes and Kitaev to enumerate $\textbf{(2+2)}$-avoiding posets, matchings with no left- or right-nestings, permutations avoiding a particular pattern, and so-called ascent sequences, and by Dukes and Parviainen to enumerate upper triangular matrices with non-negative entries and no empty rows or columns. Claesson and Linusson conjectured they also enumerated matchings with no 2-nestings. Using these new interpretations of the Fishburn numbers and another version of the involution, we prove the conjectured equality (also proven using matrices by Jel\'{\i}nek and by Yan) of two refinements by Remmel and Kitaev of the Fishburn generating function. In an appendix, we state and prove another conjecture of Claesson and Linusson giving the distribution of left-nestings over the set of all matchings.
No associations
LandOfFree
Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-105225