Home.

How many associations?

To give examples, there are 3 ways to associate 5 inputs to a ternary operation:

O (a, b, O (c, d, e)) O (a, O (b, c, d), e) O (O (a, b, c), d, e)

and 12 ways to associate 7 inputs:

O (a, O (b, c, d), O (e, f, g)) O (O (a, b, c), d, O (e, f, g)) O (O (a, b, c), O (d, e, f), g)
O (a, b, O (c, d, O (e, f, g))) O (a, O (b, c, O (d, e, f)), g) O (O (a, b, O (c, d, e)), f, g)
O (a, b, O (c, O (d, e, f), g)) O (a, O (b, O (c, d, e), f), g) O (O (a, O (b, c, d), e), f, g)
O (a, b, O (O (c, d, e), f, g)) O (a, O (O (b, c, d), e, f), g) O (O (O (a, b, c), d, e), f, g)

With more inputs, the number of associations increases rapidly, which is given by the Fuss-Catalan formula Am (3, 1), and which is listed as OEIS 001764. Here is a table:

number of
invocations:
m
number of
inputs:
2m + 1
number of
associations:
Am (3, 1)
example
011 a
131 O (a, b, c)
253 O (O (a, b, c), d, e)
3712 O (a, O (b, c, d), O (e, f, g))
4955 O (O (a, b, O (c, d, O (e, f, g))), h, i)
511273 O (a, b, O (O (c, O (d, e, f), g), O (h, i, j), k))
6131428 O (a, O (b, O (O (c, d, e), f, O (g, h, i)), j), O (k, l, m))
7157752 O (a, O (b, O (c, d, e), O (O (O (f, g, h), i, j), O (k, l, m), n)), o)
m 2m + 1 (3m)! ÷ (m! (2m + 1)!)

There is a recursive formula:

Am+1 (3, 1) = Am (3, 1) ×
((3m + 1) (3m + 2) (3m + 3)) ÷
((m + 1) (2m + 2) (2m + 3))

or equivalently:

Am+1 (3, 1) = Am (3, 1) ×
(27m3 + 54m2 + 33m + 6) ÷
(4m3 + 14m2 + 16m + 6)

As the magnitude of m increases, the cubic terms predominate, the ratio of successive terms approaches 274 = 6.75, and the growth can be described as exponential. The following table displays some larger values:

m Am (3, 1) m Am (3, 1) m Am (3, 1)
0 1 9 246,675 18 2,619,631,042,665
1 1 10 1,430,715 19 16,332,922,290,300
2 3 11 8,414,640 20 102,240,109,897,695
3 12 12 50,067,108 21 642,312,451,217,745
4 55 13 300,830,572 22 4,048,514,844,039,120
5 273 14 1,822,766,520 23 25,594,403,741,131,680
6 1,428 15 11,124,755,664 24 162,250,238,001,816,900
7 7,752 16 68,328,754,959 251,031,147,983,159,782,228
8 43,263 17 422,030,545,335 266,568,517,413,771,094,628