Premium
Forests of label‐increasing trees
Author(s) -
Riordan John
Publication year - 1979
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190030204
Subject(s) - combinatorics , mathematics , branching (polymer chemistry) , tree (set theory) , path (computing) , binary tree , order (exchange) , weight balanced tree , discrete mathematics , binary search tree , chemistry , computer science , organic chemistry , finance , economics , programming language
Label‐increasing trees are fully labeled rooted trees with the restriction that the labels are in increasing order on every path from the root; the best known example is the binary case—no tree with more than two branches at the root, or internal vertices of degree greater than three—extensively examined by Foata and Schutzenberger in A Survey of Combinatorial Theory. The forests without branching restrictions are enumerated by number of trees by F n ( x ) = x ( x + 1)…( x + n − 1), n >1 ( F 0 ( x ) = 1), whose equivalent: F n ( x ) = Y n ( xT 1 ,…, xT n ), F n (1)= T n + 1 = n !, is readily adapted to branching restriction.