A bijective proof of the equation linking the Schröder numbers, large and small (Q5951939)
From MaRDI portal
scientific article; zbMATH DE number 1687465
Language | Label | Description | Also known as |
---|---|---|---|
English | A bijective proof of the equation linking the Schröder numbers, large and small |
scientific article; zbMATH DE number 1687465 |
Statements
A bijective proof of the equation linking the Schröder numbers, large and small (English)
0 references
11 September 2002
0 references
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\). The 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. It is well known that \(R_n= 2S_n\) for \(n\geq 1\). The paper provides a new bijective proof to this identity.
0 references
Schröder numbers
0 references
ordered trees
0 references