29 Parentheses Catalan Numbers and Ruin 1 Introduction A sequence of zeroes and ones can represent a message a sequence of data in a computer or in digital communications but it also can represent all sorts of mathematical or real world objects Thus a sequence of length n can represent the outcome of n coin tosses or a binary valued vector of length n or a polynomial of degree up to n 1 with binary coefficients or a number We will now discuss three other interpretations for such a sequence First a sequence of length n can represent a subset of an n element set S Each position j in the sequence can represent one of the n elements A given subset T of S can then be represented by the n length sequence having 1 s in the positions corresponding to the elements of T and 0 s elsewhere For example for n 6 the subset 2 3 5 can be represented as 011010 The 2n binary sequences of length n then correspond to the 2n subsets of an n element set We already know something about subsets of a set Thus the number of such subsets that have k elements in them is the binomial coefficient C n k which is n k k We will deduce some more properties of collections of subsets from the next interpretation 2 Parentheses A another curious interpretation of binary sequences is that obtained by replacing each 1 by a left parenthesis and each 0 by a right one 1 Thus 011010 can be written as The gain we get from this silly looking substitution is that there is a natural definition of closing among parentheses If a left and right parenthesis are adjacent in the proper order like we can close them with one another and ignore them in future closings so that those around them become adjacent as happens similarly with the pairings in the Hu Tucker algorithm Thus in our example above the first two parentheses remain open while the last two close A famous ancient question in this context is how many distinct arrangements of n pairs of left right parentheses are there all of which close The answer to this question is called the n th Catalan number C n Here are the first few answers C 1 1 C 2 2 C 3 5 and and We can deduce the answer to this and many similar questions in terms of binomial coefficients by noticing that every sequence of 2n parentheses or in other terms every subset of a 2n element set has some open part and some closed part when considered as a sequence of parentheses This allows us to define a natural partition of all subsets of a 2nelement set or of an odd sized set as well Each block of the partition consists of all subsets which have the same closed part in the same locations Thus in our original example the closed part consists of the last 4 parentheses and the first two represent its open part 2 The magical fact that makes this information extraordinarily useful is that open parts are extremely simple No open part can contain a left parenthesis followed by a right parenthesis Thus open parts wherever they occur in a sequence all either consist of all parentheses of the same kind or some right ones followed by some left ones If for example the open part of a sequence has four elements the only possibilities are and wherever they are located The binary sequences that correspond to these possibilities are 1111 0111 0011 0001 and 0000 The sets corresponding to them are none of them the last element the last two elements the last three elements and all four elements Here and in general these sets form what we can call a full chain Each set in a full chain contains or is contained in all the others and there are no gaps among them every set in the middle of one has another set in the chain with one more element and another with one less element What other sequences have the same closed part as our example We can replace the open part by any other open part of the same size and location here we can replace at the beginning by and also by The results here expressed as binary sequences are that 001010 011010 and 111010 all have the same closed part and hence lie in the same block in this partition Considered as subsets these are 3 5 2 3 5 and 1 2 3 5 The subsets of a set S that have the same closed parts all have open parts in the same locations and therefore inherit the wonderful properties of open parts 3 Recall that the set S corresponding to n pairs of parentheses must have 2n elements all together one for each parenthesis We will quickly be able to read off what the Catalan number C n is from these properties Once again these properties are 1 Each block in this partition is a full chain and is completely ordered by inclusion 2 Each block is symmetric about the middle size S 2 If as here S has cardinality 2n their sizes are symmetric about n This statement follows from the fact that the closed parts all have the same number of left parentheses as right ones and so the corresponding sets have one element for each closed parenthesis The open parts are also symmetric about the middle size 3 Full chains have no gaps in the them They have an element of every size from some minimum 2n 2 k to 2n 2 k In short each block has some smallest set in it and then consists of what you get by adding the elements in the open part one at a time highest index first to that set until all are added We can draw the following conclusions from these facts 1 Every set of size 2n 2 j is in one full chain of this kind that stretches from at most size 2n 2 j to at least 2n 2 j 2 Any such chain contains at least 2j 1 member subsets 3 Every one of these chains of length at least 2j 1 contains a set of size n j We may deduce from the first and third fact that the number of chains of length 2j 1 or more is the number of subsets of S of size n j This latter is the binomial coefficient C 2n n j 4 We can also answer the question How many of our chains in this partition have length exactly 2j 1 These are chains of length at least 2j 1 but no longer They must all have a member having n j elements but no member having n j 1 elements The number of these must therefore be the difference in binomial coefficients C 2n 2n 2 j C 2n 2n 2 j 1 The first term counts how many of our chains have a member of size m j while the second tells us …