Copyright © University of Cambridge. All rights reserved.

'Counting Binary Ops' printed from https://nrich.maths.org/

Show menu


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.