Intransitive Trees

✍ Scribed by Alexander Postnikov

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 288 KB
• Volume: 79
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1996.2735

✦ Synopsis

We study the class of trees T on the set [1, 2, ..., n] such that for any 1 i<j<k 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. 1997 Academic Press n k+ k n&1 .

The first few numbers F n are given below.