Skip to main content
### Number and algebra

### Geometry and measure

### Probability and statistics

### Working mathematically

### For younger learners

### Advanced mathematics

# Counting Binary Ops

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.

Or search by topic

Age 14 to 16

Challenge Level

- Problem
- Getting Started
- Student Solutions
- Teachers' Resources

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.