MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does anyone know if there is currently any research or any potential bounds on the number of trees on $n$ vertices with degree at most $3$? One can bound this above by $C_{n}$ the $n$th Catalan number, or $n^{n-2}$ from Cayley's formula, but I think I have found a way to bound it a little better. I just want to make sure I'm not overlooking something that has already been done.

Edit: Some motivation might be nice? I'm looking at these as dual graphs of triangulations of polygons. I'm trying to see if this could be used to establish a lower bound on the number of unlabeled triangulations of an $(n+2)$-gon.

share|cite|improve this question

I'm not sure if this specific problem has been done, but the enumeration of unlabeled trees with degree restrictions (especially in connection with chemical compounds) can be found in Pólya's original paper on "Pólya theory", which is available in English translation as G. Pólya and R. C. Read, Combinatorial enumeration of groups, graphs, and chemical compounds, Springer-Verlag New York, 1987. A more modern approach to unlabeled tree enumeration can be found in François Bergeron, Gilbert Labelle, and Pierre Leroux, Combinatorial Species and Tree-like Structures (Encyclopedia of Mathematics and its Applications volume 67), Cambridge University Press, 1998. For more on asymptotics for unlabeled trees of various sorts, see Frank Harary, Robert W. Robinson,and Allen J. Schwenk, "Twenty-step algorithm for determining the asymptotic number of trees of various species", J. Austral. Math. Soc. Ser. A 20 (1975), 483–503.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.