You may also like

problem icon


Draw a 'doodle' - a closed intersecting curve drawn without taking pencil from paper. What can you prove about the intersections?

problem icon

Russian Cubes

I want some cubes painted with three blue faces and three red faces. How many different cubes can be painted like that?

problem icon

N000ughty Thoughts

How many noughts are at the end of these giant numbers?

Counting Binary Ops

Stage: 4 Challenge Level: Challenge Level:2 Challenge Level:2

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.