THE ENUMERATION OF A FAMILY OF LADDER GRAPHS
Douglas G. Rogers · The Quarterly Journal of Mathematics · 1977
A family of ladder graphs is studied which is characterized in terms of relations, called connective relations, on finite, totally ordered sets. The number of such relations on a set Xn of n points is known to be Cn, the nth Catalan number. Here it is shown that the number g(n) of these relations on Xn under which every element is related to at least one other element satisfies g(n) + g(n + 1) = mn, n≥0; g(0) = 1 where mn is the nth Motzkin number. The numbers of certain types of associated graphs on a given number of vertices and with a given number of edges is also determined. Correspondences between connective relations, rooted planar trees and rhyming schemes are established.