Counting equivalent expressions
David Wilson
dwilson at gambitcomm.com
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