The sequence A006318 at OEIS stands for the Schröder numbers.

They describes the number of lattice paths from the southwest corner $(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$, using only single steps north, $(0,1)$, northeast $(1,1)$ or east $(1,0)$, that do not rise above the SW–NE diagonal (sometimes called Royal Paths).

Also, according to OEIS, they correspond to the number of perfect matchings in number of perfect matchings in a triangular grid of n squares (n = 1, 4, 9, 16, 25, ...).

Tomislav Doslic wrote a very nice paper on a similar relation between perfect matchings in a hexagonal grid and the corresponding lattice path. He also mentions the triangular case, and cites the book "Enumerative Combinatorics" vol2, by Stanley, Ex. 6.39 - where I cannot find an answere.

Therefore I very much hope for some hints or further literature references on the question given in the title.


I was able to find the result at Ex. 6.39 s in Stanley's EC Vol.2. The reference given there is to

Ciucu, M. "Perfect Matchings of Cellular Graphs" Journal of Algebraic Combinatorics 5 (1996), 87-103

In theorem 4.1, Ciucu computes the generating function of the perfect matchings in a triangular grid of squares and concludes that it is the same as the generating function of Schröder numbers. In the remark that follows the proof of theorem 4.1, a bijection between matchings and paths is also given.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.