Catalan Numbers Staircase bijection

Question

I need to give a bijective proof for the following problem (via R. Stanley Catalan Addendum).

($k^8$) tilings of the staircase shape $(n, n − 1, \dots , 1)$ with $n$ rectangles. For example, when $n = 3$

I don't know how to explain the bijection between this and the plane binary tree with $2n+1$ vertices.

Answer 1

These staircase plots have the property that each lower-right corner of the staircase line (from bottom left to top right) belongs to exactly one rectangle; Starting from the top-right south-east corner, choose any width (say k) available up to n; then drop down from the north-west corner of this rectangle down to the diagonal staircase. Now, remark that you have cut off a 'pending' k-1 triangular staircase (of lower order); (now recurse within that new staircase), then continue cutting off rectangles until their combined width (measured at top edge) equals n. These provide the highest level rectangles. For each 'pending' staircase start a bracketing to show under what rectangle it hangs. For the plots in your question, we get, left to right:
3(2(1)) , 3(1 1) , 1 2(1) , 2(1) 1 , 1 1 1
These can be transformed (and back) to nodes of binary trees by generating a left branching for items on the same level, and right branching for items on lower level:

[3]        [3]       [3]      [3]           [3]
 |          |         |        |             |
 3          3         1        2             1
/ \        / \       / \      / \           / \
   2          1     2        1   1         1 
  / \        / \   / \      / \ / \       / \
     1      1         1                  1 
    / \    / \       / \                / \