Problem #12
There are many ways to indicate the order of operations in the
expression a + b + c + d using parentheses,
for example (a + b) + (c + d) or
a + ((b + c) + d). In fact, it is well-known
that if there are n terms, there are
Binomial[2n-2,n-1]/n (these are known as
Catalan numbers) ways of parenthesizing the
expression. For four terms this yields 5 ways of parenthesizing. Of
course, the associative law tells us that these all give the same result
algebraically.
Consider the expression
a + b × c + d.
In this case, inserting parentheses to indicate the order of operations
can result in algebraically distinct expressions. For example,
(a + b) × (c + d) is not equal to
a + ((b × c) + d). [Note that we are
not using the traditional order of operations where multiplication takes
priority over addition; the order must be explicitly indicated by
parentheses.]
This month's problems:
-
How many algebraically distinct expressions can be
obtained from the expression above?
-
What if we place four pairs of parentheses in
a + b × c + d × e +
f?
-
Six pairs of parentheses in
a + b × c + d × e +
f × g + h?