§2B 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 |
|---|---|---|---|
| 0 | 1 | 1 | a |
| 1 | 3 | 1 | O (a, b, c) |
| 2 | 5 | 3 | O (O (a, b, c), d, e) |
| 3 | 7 | 12 | O (a, O (b, c, d), O (e, f, g)) |
| 4 | 9 | 55 | O (O (a, b, O (c, d, O (e, f, g))), h, i) |
| 5 | 11 | 273 | O (a, b, O (O (c, O (d, e, f), g), O (h, i, j), k)) |
| 6 | 13 | 1428 | O (a, O (b, O (O (c, d, e), f, O (g, h, i)), j), O (k, l, m)) |
| 7 | 15 | 7752 | 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 27⁄4 = 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 | 25 | 1,031,147,983,159,782,228 | ||
| 8 | 43,263 | 17 | 422,030,545,335 | 26 | 6,568,517,413,771,094,628 |