Skip to main content
2 of 4
edited tags
Martin Sleziak
  • 4.7k
  • 4
  • 35
  • 40

Catalan numbers from matchings?

There are several examples of interpreting the Catalan numbers as non-nesting or non-crossing matchings of some graph. My question is: Is there a family of graphs $G_1,G_2,\dotsc$ with the number of vertices growing linearly, such that the number of matchings (not complete matchings) of $G_i$ is the $i$th Catalan number?

I have checked Richard Stanley's book on Catalan numbers, but such an interpretation is not there. The closest I found is a graph, where one counts the number of complete matchings, but this is not what I am after.

Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133