I apologize if the questions are too elementary for the forum, but I am not an expert in this fields.
-
How many (rooted or unrooted) binary trees with $n$ vertices are there up to isomorphism?
-
How many maximal planar graphs with $n$ nodes are there up to isomorphism?
-
How many graphs with $n$ nodes and valence $v$ at every node are there up to isomorphism?
Best Answer
For question 1, I believe you refer to unordered trees, for which a summary of the available information is given page 4 of "The CRT is the scaling limit of unordered binary trees" by Marckert and Miermont, Random Structures & Algorithms, 2011. Also see Sloane A001190, for the Etherington-Wedderburn numbers, and Otter for an asymptotic formula. There is also something in Flajolet Sedgewick Analytic Combinatorics, according to Marckert and Miermont. Quoting Marckert and Miermont, the generating function: $$\mathfrak{T}(z)=\sum_{n\geq 1}T_n\, z^n$$ of rooted binary trees unordered trees counted by the number of leaves satisfies $$\mathfrak{T}(z)=z+\frac{\mathfrak{T}(z^2)+\mathfrak{T}(z)^2}{2}\, ,$$ leading to an asymptotic formula $$T_n\sim_{n\to\infty}^{}\frac{c}{2\sqrt{\pi} n^{3/2}\varrho^n},$$ in which $\varrho$ is the radius of convergence of $\mathfrak{T}$. I would say that this is actually taken from R. Otter, "The number of trees", Ann. of Math. (2), 49, 583-599, 1948, but did not check. For general unordered trees, elements of answer seem to date back to Cayley 1857 for the equation satisfied by the generating function, and to Polya 1937 for the asymptotic formula (see Flajolet Sedgewick page 67).
I must add it is a rather common view that counting up to isomorphism is often much more difficult than "regular counting".
In the same order of idea, I should perhaps cite L. B. Richmond and N. C. Wormald. Almost all maps are asymmetric. J. of Combinat. Theory, Ser. B, 63(1):1–7, 1995. that says the group of isomorphisms of a planar map is nontrivial only for an exponentially small fraction of the set of planar maps with $n$ faces, edges or vertices (to be checked).
The enumeration of planar graphs has received a satisfactory answer only very recently, I think, see "Asymptotic enumeration and limit laws of planar graphs", Omer Giménez and Marc Noy, J. Amer. Math. Soc. 22 (2009), 309-329. I don't think that the enumeration is up to isomorphism, but this should not make any difference for the asymptotics if the result of Richmond and Wormald extends from planar maps to planar graphs.