An Elementary Evaluation of the Catalan Numbers
David Singmaster · American Mathematical Monthly · 1978
2. The derivation. Consider any product of n + 1 terms. We insist on putting in the final set of parentheses for the final operation, so we have n pairs of parentheses. For example, when n = 2, we have the products ((ab)c) and (a(bc)). It is remarkable, though well known in Logic and Computer Science, that only the left or only the right parentheses are necessary. Indeed, if we omit the right (left) parentheses and replace all the left (right) parentheses by some operator symbol, say X, then we have the Polish (reverse Polish) notation of 1Fukasiewicz. For example, when n=2, the products above have the Polish forms XXabc and XaXbc and the reverse Polish forms abXcX and abcXX. Henceforth we shall only deal with the reverse Polish forms, which are more convenient. Any product of n + 1 terms or operands gives a unique reverse Polish string of n + 1 operands and n operators. A simple induction verifies that we have more operands than right parentheses occurring in any initial segment of a product. Thus the same relation must hold for operands and operators in the corresponding reverse Polish string. We say a string of n + 1 operands and n operators, is well-formed if this is the case. Given a well-formed string, we can recover the product of n + 1 terms as follows. Read the string from left to right. The first symbol must be an operand and we write this down. Continuing, if the next symbol is an operand, we write it at the right of the last symbol written. If the next symbol is an operator, we write a parenthesis about the last two operands and consider the parenthesized expression as a new operand, replacing the enclosed two. Since the string is well-formed, we will get a correctly parenthesized product as the result of continuing this process. So we have a bijection between the products of n + 1 operands and the well-formed strings of n + 1 operands and n operators.