Return to Question

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 family of graphs, where one counts the number of complete matchings, but this is not what I am after.

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 family of graphs, where one counts the number of complete matchings, but this is not what I am after.

Edit: I thought that the linearity condition was sufficient to force nice answers, but perhaps not. Ok so there is the classical recursion for Catalan numbers, $$C_{n+1} = \sum_k C_k C_{n-k}.$$ The family of graphs should be defined such that the number of matchings is seen to satisfy the above recursion without too much work.

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.

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 family of graphs, where one counts the number of complete matchings, but this is not what I am after.