show/hide this revision's text 2 added 1131 characters in body

EDIT: Wait, sorry, this counts full binary trees where left and right children are indistinguishable. I suppose this isn't what you want, is it?

Not too hard to fix, fortunately, since the nodes are already labeled: just decide for each internal node whether the child with the higher label is on the right or left. There are 2n ways to pick that. We can incorporate this into our earlier counting method by looking at anagrams of the 2n distinct letters b1c1b2c2...bn-1cn-1bncn. (There are, of course, (2n)! of these). Given such an anagram, get a binary tree as follows:

First, chop off the last letter, treat the cis as bis, and find the tree with this new string as its Prüfer code. Choose the letter you chopped off to be the root, so every internal node now has two children. To decide which is on the left and which is on the right, ask whether bi came before ci in the original string. If so, the child with the smaller label is on the left; otherwise it's on the right.
show/hide this revision's text 1

Wait, you mean n+1 labels for the leaves and n labels for the internal nodes, right?

Note that such trees are counted by the multinomial coefficient {2n choose 2,2,2,2,...,2} (with n 2s), because their Prüfer codes are exactly the ones containing 2 of all but one of the bis and 1 of the last one. If you take such a Prüfer code and affix to its end the label of the root, then you're just counting anagrams of b1b1b2b2...bn-1bn-1bnbn. I'm not a computer scientist, but these are easy enough to loop through, right?