Two New Interpretations of the Fishburn Numbers and their Refined Generating Functions

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Type

Scientific paper

Abstract

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

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-105225

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.