Five ways to put the brackets
Tonight's idea
Work out \(2 + 3 + 4\). You can do \((2 + 3) + 4\) or \(2 + (3 + 4)\). Both give 9. An operation \(\ast\) is associative when \((x \ast y) \ast z = x \ast (y \ast z)\) for all inputs. Then the brackets never matter, however long the chain.
Subtraction is not associative: \((9 - 4) - 2 = 3\) but \(9 - (4 - 2) = 7\). Then each way of placing the brackets is a different calculation.
Keep the inputs in order and bracket them fully, two things at a time. Each bracketing is a tree: the inputs sit along the bottom, and every join is one use of the operation. Three inputs make 2 trees. Bigger trees are made by plugging smaller trees together. Mathematicians study all the ways of combining things by studying how trees plug together.
Four inputs in a fixed order can be bracketed in exactly 5 ways. An associative operation gives the same answer all 5 times. Any other operation might not.
Watch one: rock, paper, scissors
Turn the game into an operation. \(x \star y\) is the winner when \(x\) meets \(y\): rock (R) beats scissors (S), scissors beats paper (P), and paper beats rock. If both are the same, \(x \star x = x\). So \(R \star S = S \star R = R\), \(S \star P = P \star S = S\) and \(P \star R = R \star P = P\).
Read each tree from the bottom up. A circle shows the result of that join.
Left tree. \(R \star P = P\), then \(P \star S = S\). So \((R \star P) \star S = S\).
Right tree. \(P \star S = S\), then \(R \star S = R\). So \(R \star (P \star S) = R\).
Same inputs, same order, different answers. So \(\star\) is not associative, even though swapping the two inputs never changes \(x \star y\). Order and grouping are separate questions.
Your turn
- Draw the 5 trees for four inputs \(a, b, c, d\) and write the bracketing under each one. Start from the top join, which is the last operation done. It splits the inputs as 1 and 3, as 2 and 2, or as 3 and 1.
- Put brackets into \(16 - 8 - 4 - 2\) in all 5 ways and work each one out. How many different answers are there? Which one do you get by working from left to right?
- Which of these four operations are associative: addition, "the larger of the two", subtraction, "the average of the two"? For each one that is not, find three numbers that show it.
- How many ways are there to bracket five inputs \(a, b, c, d, e\)? Do not draw them all. Use the top join: it splits the inputs as 1 and 4, 2 and 3, 3 and 2, or 4 and 1, and you know how many trees each part can be.
Stretch: luck, or a rule?
(a) Work out all 5 bracketings of \(64 \div 16 \div 4 \div 2\). (b) In exercise 2, and again here, the same two bracketings agree. Rewrite \((a - (b - c)) - d\) and \(a - (b - (c - d))\) without brackets to show that they agree for all numbers. (c) Let \(x \circ y\) mean "double \(x\), then add \(y\)", so \(3 \circ 1 = 7\). Work out all 5 bracketings of \(2 \circ 1 \circ 1 \circ 1\). How many different answers this time?
Answers
- See the picture. Top join splitting 3 and 1: the first three inputs make one of their 2 trees, giving \(((ab)c)d\) and \((a(bc))d\). Splitting 2 and 2: only \((ab)(cd)\). Splitting 1 and 3: \(a((bc)d)\) and \(a(b(cd))\). That is \(2 + 1 + 2 = 5\). Every tree has 3 joins, because each join turns two pieces into one.
- \(((16 - 8) - 4) - 2 = 2\). \((16 - (8 - 4)) - 2 = 10\). \((16 - 8) - (4 - 2) = 6\). \(16 - ((8 - 4) - 2) = 14\). \(16 - (8 - (4 - 2)) = 10\). Five bracketings but four different answers: 2, 6, 10 and 14. Working from left to right is the first one, 2. That is what \(16 - 8 - 4 - 2\) means when no brackets are written.
- Addition and "the larger of the two" are associative: either way round, three numbers give their total, or the largest of the three. Subtraction is not: \((5 - 3) - 1 = 1\) but \(5 - (3 - 1) = 3\). The average is not: try 0, 0, 4. Grouping the first two: the average of 0 and 0 is 0, then the average of 0 and 4 is 2. Grouping the last two: the average of 0 and 4 is 2, then the average of 0 and 2 is 1. Your numbers may differ. One failure is enough, even though some choices do agree: \((x - y) - 0 = x - (y - 0)\). Like \(\star\), the average does not care about the order of its two inputs but does care about grouping.
- 14. Splitting 1 and 4: the single input is 1 tree and the other four make 5, so \(1 \times 5 = 5\). Splitting 2 and 3: \(1 \times 2 = 2\). Splitting 3 and 2: \(2 \times 1 = 2\). Splitting 4 and 1: \(5 \times 1 = 5\). In total \(5 + 2 + 2 + 5 = 14\). The counts for 1, 2, 3, 4, 5 inputs are 1, 1, 2, 5, 14. They are called the Catalan numbers, and the same rule gives the next one, 42.
Stretch. (a) In the order of the picture: \(\tfrac{1}{2}\), 8, 2, 32, 8. (b) \((a - (b - c)) - d = (a - b + c) - d = a - b + c - d\), and \(a - (b - (c - d)) = a - (b - c + d) = a - b + c - d\). The same expression, so it is a rule, not luck: subtraction can never give more than 4 different answers from four inputs. Division works the same way: as long as nothing divides by zero, those two bracketings both equal \((a \times c) \div (b \times d)\). (c) Start with \(2 \circ 1 = 5\) and \(1 \circ 1 = 3\). Then \(((2 \circ 1) \circ 1) \circ 1 = 11 \circ 1 = 23\). \((2 \circ (1 \circ 1)) \circ 1 = 7 \circ 1 = 15\). \((2 \circ 1) \circ (1 \circ 1) = 5 \circ 3 = 13\). \(2 \circ ((1 \circ 1) \circ 1) = 2 \circ 7 = 11\). \(2 \circ (1 \circ (1 \circ 1)) = 2 \circ 5 = 9\). Five different answers, the most that five bracketings could ever give.