Would you be able to provide a small example?  Are you looking for an algorithm that generates all the full binary trees that have this property for some n? the height of the tree? It isn't quite clear from what you've described is the input of your problem.

More clarification and a small example would be helpful in understanding the problem.

Hi, I am looking for algorithm generating all trees with n leaves, abritrary height. And I consider the class of equivalence, s.t. for example trees

                       /      \                                           /  \

                  /     \       4                                    1    /    \

              /    \    3                                                /   \     4

          1        2                                                 2      3

are equivalent (have the same topology), because you can obtain the other tree by swaping the subtrees in some particular nodes.

It is now clearer?

Best, Jan

If you allow such switches, by switching a `dangling caret' tree for an empty tree, all trees become equivalent to the right vine tree with n-leaves, so you are left with only one tree in your equivalence class.

If you do not want to allow switches with empty trees, then you will be able to show equivalence between any tree and a right vine tree with a collection of solitary dangling carets hanging off (to the left) of the right vine.

Thank you for your answer.

The formulation should be slightly different: what you allow is to interchange the left and right subtree of particular node, not subtrees of different nodes.... How is the situation changed in that case?

Dear sir,

Please refer to this link : http://en.wikipedia.org/wiki/Binary_tree#Combinatorics

The number you look for is related to Catalan number. You should tag your question with : "Combinatorics" and/or "Combinatorics on words". You will find more people that will help you to get the right algorithm.

Best wishes.

Of course, the total number of trees with n leaves is equal to Catalan number. But this does not incorporate the equivalence class, as described above. The number of different topologies will be strongly suppresed.

I realise this question is more than five years old, but I came across it while googling the same question. I thought it would be worth posting the answer for any future travellers. For me (and possibly the original poster?) the context is finding the number of possible topologies of phylogenetic trees (specifically unlabelled binary rooted trees with a fixed number of leaves, which might represent e.g. extant species).

The number of such topologies a(n) can be calculated recursively. For one, two or three species, we have a(1) = a(2) = a(3) = 1. For four species, consider the first bifurcation above the root. It splits the tree into two halves and the species can be allocated to these two halves either as 4 = 3 + 1 or as 4 = 2 + 2. In the former case, there are a(1)*a(3) = 1 possible topologies. In the latter case, likewise only 1 possibility. So we have:

a(4) = a(1)*a(3) + 1 = 2.

Similarly,

a(5) = a(1)*a(4) + a(2)*a(3) = 3

We can use these recursions to find the value of a(n) for any n. For odd n, the recursions are simply of the form:

a(n) = sum_{i = 1 to (n-1)/2} [ a(i)a(n-i) ]

For even n, we have to be careful about the case where the first bifurcation splits the tree into two evenly sized pieces. In this case, the number of possible trees is not just a(n/2)*a(n/2), because choosing topology T1 for the left subtree and T2 for the right subtree is equivalent to choosing left = T2 and right = T1. The number of topologies where the two subtrees differ in topology is just

a(n/2) choose 2 = a(n/2)[a(n/2) - 1] / 2.

To this we must add the trees where both subtrees have the same topology, of which there are a(n/2). So in total we have

a(n/2)[a(n/2) - 1] / 2 + a(n/2) = a(n/2)[ a(n/2) + 1] /2

The recursion for even n is then:

a(n) = a(n/2)[ a(n/2) + 1] /2 + sum_{i = 1 to (n-2)/2} [ a(i)a(n-i) ]

By iterating the recursions, we obtain for n=1,2,...:

a(n) = 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, ...

Plugging this into OEIS, we can connect with the mathematical literature. Apparently they are called Wedderburn-Etherington numbers (https://oeis.org/A001190). The OEIS entry has more details but no closed-form solution.

Googling "phylogeny" and "Wedderburn-Etherington" picks up some theory papers, e.g. Bóna & Flajolet (2009):

http://algo.inria.fr/flajolet/Publications/BoFl09.pdf

Incidentally, counting labelled trees is much easier and was solved by Felsenstein (1978) (https://academic.oup.com/sysbio/article-abstract/27/1/27/1626689?redirectedFrom=fulltext). See also https://en.wikipedia.org/wiki/Phylogenetic_tree#Enumerating_trees