Magma (algebra) - Combinatorics and Parentheses

Combinatorics and Parentheses

For the general, non-associative case, the magma operation may be repeatedly iterated. To denote pairings, parentheses are used. The resulting string consists of symbols denoting elements of the magma, and balanced sets of parenthesis. The set of all possible strings of balanced parenthesis is called the Dyck language. The total number of different ways of writing applications of the magma operator is given by the Catalan number . Thus, for example, which is just the statement that and are the only two ways of pairing three elements of a magma with two operations. Less trivially, :, and .

A shorthand is often used to reduce the number of parentheses. This is accomplished by using juxtaposition in place of the operation. For example, if the magma operation is, then abbreviates . Further abbreviations are possible by inserting spaces, for example by writing in place of . Of course, for more complex expressions the use of parenthesis turns out to be inevitable. A way to avoid completely the use of parentheses is prefix notation.