A bijective proof of the equation linking the Schröder numbers, large and small

DOI10.1016/S0012-365X(01)00122-4MaRDI QIDQ5951939zbMATH OpenWikidataFDO

Authors Emeric Deutsch

Publication date 11 September 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(01)00122-4

zbMATH Keywords

ordered treesSchröder numbers

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Trees (05C05)

Review text

The small Schröder numbers \(S_n\) are known to count (among others) the number of ordered trees with no node of outdegree one and with \(n+1\) leaves; the number of dissections of a convex \((n+2)\)-gon; and the number of generalized bracketings of a string of \(n+1\) letters. The sequence of small Schröder numbers starts as \(S_0= 1\), \(S_1= 1\), \(S_2= 3\), \(S_3= 11\), \(S_4= 45\).NEWLINENEWLINENEWLINEThe large Schröder numbers \(R_n\) are known to count (among others) the number of Schröder paths of semilength \(n\) (i.e. lattice paths from \((0,0)\) to \((2n,0)\) with steps \((1,1)\), \((2,0)\), and \((1,-1)\), that never go below the horizontal axis); the number of Dyck paths (i.e. lattice paths in the plane from \((0,0)\) to \((2n,0)\) with steps \((1,1)\) and \((1,-1)\), that never go below the horizontal axis) with each peak colored either black or white; and the number of parallelogram polyominoes of perimeter \(2n+2\) with each column colored either black or white.NEWLINENEWLINENEWLINEIt is well known that \(R_n= 2S_n\) for \(n\geq 1\). The paper provides a new bijective proof to this identity.

Recommendations

• Deux propriétés combinatoires des nombres de Schröder
• Bijective recurrences concerning Schröder paths
• Bijective proofs of recurrences involving two Schröder triangles
• Chung-Feller property of Schröder objects
• Some Properties and Combinatorial Implications of Weighted Small Schr\"oder Numbers

Cited in

(14)

• Bijective proofs of recurrences involving two Schröder triangles
• Riordan arrays, Łukasiewicz paths and Narayana polynomials
• The m-Schröder paths and m-Schröder numbers
• 2-binary trees: bijections and related issues
• Permutation of elements in double semigroups
• Generalized Schröder matrices arising from enumeration of lattice paths.
• Degenerate flag varieties: moment graphs and Schröder numbers
• Noncrossing linked partitions and large (3,2)-Motzkin paths
• Generalized Schröder matrix and its combinatorial interpretation
• Schröder coloring and applications
• The \(\mathfrak{uvu}\)-avoiding \((a, b, c)\)-generalized Motzkin paths with vertical steps: bijections and statistic enumerations
• A Combinatorial Bijection between Ordered Trees and Lattice Paths
• Some \(\gamma \)-positive polynomials arising from enumerations of the pseudo Schröder paths
• Cumulants in noncommutative probability theory. IV: Noncrossing cumulants: de Finetti's theorem and \(L^{p}\)-inequalities

This page was built for publication: A bijective proof of the equation linking the Schröder numbers, large and small

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5951939)