Intransitive trees

[摘要] We study the class of trees T on the set {1, 2, ..., n} such that for any 1 less than or equal to i < j < k less than or equal to n the pairs {i,j} and {j, k} cannot both be edges in T. We derive a formula for the number of such trees. We also give a functional equation and a differential equation for the generating function. We mention some additional combinatorial interpretations of these numbers. (C) 1997 Academic Press.

[发布日期] 1997-08-01