Counting equivalent expressions

David Wilson dwilson at
Thu Aug 21 18:33:17 CEST 2008

Mitch Harris wrote:
> [My quote elided]
> Unordered binary trees? Double factorial...
> Not obvious (but if memory serves, not a terrible combinatorial
> explanation, see Stanley reference)
The light went on when I read your note. There would be (2n-2)!/(n-1)! 
trees each with with n leaves and n-1 interior nodes. Each of these 
interior nodes could be flipped in one of two orders by commutativity, 
so that's 2^(n-1) trees per equivalence class, or (2n-2)!/(2^n (n-1))! 
equivalence classes. I'm not sure I've got it exactly right, but this is 
close enough to the double factorial expression that I'm willing to take 
your word.

More information about the SeqFan mailing list