Counting equivalent expressions

David Wilson dwilson at
Thu Aug 21 16:29:36 CEST 2008

Consider all possible expressions combining n distinct symbols via a 
binary operator. For n = 3, there are 12 such expressions:

(a(bc)) (a(cb)) (b(ac)) (b(ca)) (c(ab)) (c(ba))
((ab)c) ((ac)b) ((ba)c) ((bc)a) ((ca)b) ((cb)a)

In general, there n! orderings and (2n-2)!/(n!(n-1)!) orders of 
evaluation, for a total of (2n-2)!/(n-1)! such expressions.

If the binary operator is both associative and commutative, all of these 
expressions are equivalent, and there is 1 equivalence class.

If the binary operator is associative only, then expressions with 
variables appearing in the same order are equivalent, and there are n! 
equivalence classes.

How many equivalence classes are there if the operator is commutative only?

More information about the SeqFan mailing list