an example for counting non-isomorphic trees : there exists 6 non-isomorphic trees on 6 vertexes and there exists 11 non-isomorphic trees on 7 vertexes and there exists 23 non-isomorphic trees on 8 vertexes and so on. I find an approach that based on Product and Sum principles for counting non-isomorphic trees. But I don't know that is it approach have polynomial time and is it approach new ... .In my approach, be considered the longest path of tree and do all computations. I writ a program with mathematica software, but long runs out.
http://mathworld.wolfram.com/Tree.html
http://oeis.org/A000055
You may find it helpful to look at a paper by Corless, Gonnett, Hare, Jefffrey, and Knuth, 1996, "On the Lambert W function", published in Advances in Computational Mathematics, vol 5, pp 329-359. On the second page is mentioned that the tree function T(v), used for enumerating trees, equals -W(-v), where W(z) is the Lambert W function that is the multi-branch solution of W(z) exp(W(x)) = z.
There are some formulas for Lambert W and they should be transferrable to T(v).
I have never looked into the tree enumeration aspect of Lambert W. There are several references in the above Corless, et al, paper.
Hope that helps.
Best wishes,
Ken Roberts
There are recursive formulas for this, as discussed in https://oeis.org/A000055 (you should read the material you link to). There is also a beautiful efficient algorithm for generating all these trees, in about a fixed time per tree, independent of the number of nodes (but since the number of non-isomorphic trees grows very fast with the number of nodes,
1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, 7741, 19320, 48629, 123867, 317955, 823065, 2144505, 5623756, 14828074, 39299897, 104636890, 279793450, 751065460, 2023443032, 5469566585, 14830871802, 40330829030, 109972410221, 300628862480, 823779631721, 2262366343746, 6226306037178,
the total times grows in a non-polynomial way). References below
"""A generator for unlabeled trees.
Based on the algorithm for generation of unlabeled rooted trees by
T. Beyer and S.M. Hedetniemi, Constant time generation of rooted
trees, SIAM Journal on Computing 9, 706-712 (1980),
and the extensions by
R.A. Wright, B. Richmond, A. Odlyzko and B.D. McKay, Constant time
generation of free trees, SIAM Journal of Computing 15, 540-548 (1986).
"""
You don't mention what you want to do with the numbers; is it a serious problem?
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs