Counting Binary Ops
How many ways can the terms in an ordered list be combined by
repeating a single binary operation. Show that for 4 terms there
are 5 cases and find the number of cases for 5 terms and 6 terms.
Age
14 to 16
Challenge level
This question is about the number of ways of combining an ordered list of terms by repeating a single binary operation.
For example with three terms $a$, $b$ and $c$ there are just two ways $((a\oplus b)\oplus c)$ and $(a\oplus (b\oplus c))$. Suppose the binary operation $\oplus $ is just ordinary subtraction and $a=12, \; b=7, \; c=5$ then $((a\oplus b)\oplus c)= 5 - 5 =0$ and $(a\oplus (b\oplus c))= 12 - 2 = 10$.
We are not concerned in this question with doing the 'arithmetic' or with whether the answers are the same or different. We just want to find out how many ways there are of combining the terms, or if you like of putting brackets into the expression. Note that we need the brackets because the answers may be different as in the subtraction example.
These two tree diagrams show the two cases for combining 3 terms."
Image
Show that for four terms, (three binary operations) there are five cases and find the number of cases for five terms and six terms.
See also the problems One Basket and Walkabout
You can do this by drawing trees for each case. Don't change the
order in the list of terms. You can only combine adjacent terms and
only two at a time.
Another superb solution from Andrei, School: 205, Bucharest, Romania.
For four terms, I found the following possible combinations:
(a (b (c d)))
(a (b (c d)))
(a ((b c) d))
((a b) (c d))
((a (b c))d)
and (((a b) c) d) i.e. five.
For five terms, there are 14 combinations:
(a(b(c(de)))) (a(b((cd)e)))
(a (b (c (d e)))) (a (b ((c d) e)))
(a ((b c) (d e))) (a ((b (c d)) e))
(a (((b c) d) e)) ((a b) (c (d e)))
((a b) ((c d) e)) ((a (b c)) (d e))
((a (b (c d))) e) ((a ((b c) d)) e)
((a b) c) (d e)) (((a b) (c d)) e)
(((a (b c)) d) e) ((((a b) c) d) e)
For six terms, there are 42 combinations.
I found that these are Catalan numbers, that appear from a great variety of mathematical problems, as the number of ways a regular polygon with n sides could be divided into (n-2) triangles, the number of paths of length 2n through an n by n grid that do not rise above the main diagonal, and, of course the number of ways numbers in a sequence could be grouped using binary operations, as is the case of this problem.
The first terms of the sequence of Catalan numbers are:
1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...
They could be computed using the formula: $$Cat_n={^{2n}C_n \over (n+1)}= {(2n)!\over (n+1)!n!}$$
The correspondence with the problem is that n here must be the number of binary operations, i.e. the number of terms minus one.
The underlying structure of this problem is very similar to
Walkabout. The teachers' notes to Walkabout suggest a possible
approach which would work here too.