Mathematical Expressions

Let $C_n$ be the number of valid arrangement with $n$ pairs of parentheses. Trivially, $C_0 = 1$ . In addition, every arrangement of length $n + 1$ can be uniquely expressed by "unwrapping" the first left parenthesis into $(e_1)e_2$ , where the (possibly empty) $e_1$ and $e_2$ together have $n$ pairs. If we sum over the possible lengths of the first expression, we obtain $C_{n + 1} = \sum_{i = 0}^n C_i C_{n - i}$ . This recurrence relations defines the Catalan numbers , so $C_n = \frac{1}{n + 1}{2n \choose n}$ .

A random arrangement of $n$ pairs of parentheses has $2n$ characters. To form a random arrangement, we can choose $n$ out of the $2n$ characters to be left parentheses and fill the other $n$ with right parentheses. Thus the total number of arrangements is $2n \choose n$ .

Therefore, the probability that an arrangement with $n$ pairs of parentheses is valid is $\frac{C_n}{2n \choose n} = \frac{1}{1 + n}$ . For $n = 34$ , this probability is $\frac{1}{1 + 34} = \frac{1}{35}$ . Hence $a + b = 1 + 35 = 36$ .

We will solve this for general $n$ , as there is nothing particularly important about $n = 34$ . We will compute the number of balanced arrangements, then divide by $\binom{2n}{n}$ , the total number of ways of placing brackets, balanced or otherwise.

We can construct a bijection between ways of arranging $2n$ brackets, split evenly between both types, and walks in the plane that start at $(0, 0)$ and end at $(2n, 0)$ , an open bracket corresponding to the move $(x, y) \to (x + 1, y + 1)$ , and a closed bracket corresponding to the move $(x, y) \to (x + 1, y - 1)$ . It is clear that a balanced arrangement corresponds to a path that never falls below the $x$ axis, so we seek to count the number of such "valid" paths.

We will find it easier to count the invalid paths, the paths that do fall below the $x$ axis. For such a path, consider the first point where it crosses below to $y = -1$ , say, $(a, -1)$ . Reflect the remainder of the path (that is, the portion beyond $x = a$ ) over the line $y = -1$ . This reflects the ending point, $(2n, 0)$ , to $(2n, -2$ ). It is also clear that we can take any path that uses the two move types to go from $(0, 0)$ to $(2n, -2)$ , look for the first position where the path crosses to $y = -1$ , reflect over the remainder, and get a path from $(0, 0)$ to $(2n, 0)$ that crosses below the $x$ axis.

This demonstrates a bijection between invalid paths from $(0, 0)$ to $(2n, 0)$ and paths of any kind from $(0, 0)$ to $(2n, -2)$ . The number of the latter is just $\binom{2n}{n + 1}$ (we must go down $n + 1$ times and up $n - 1$ times, for $2n$ total moves). So the number of valid paths is $\binom{2n}{n} - \binom{2n}{n + 1} = \binom{2n}{n} - \frac{n}{n + 1} \binom{2n}{n} = \frac{1}{n + 1} \binom{2n}{n}$ .

Therefore the probability is $\frac{1}{n + 1}$ . For $n = 34$ we have $\frac{1}{n + 1} = \frac{1}{35}$ , giving an answer of 36.

Any invalid sequence of brackets must reach a point where the number of closed brackets exceed the number of open brackets. Consider the first position in the sequence where this happens. Call this position A. Note that the bracket at position A must be a closed bracket. Since there is one more closed bracket than open bracket up till position A, there will be one more open bracket than closed bracket after position A. Now, for every bracket after but not including position A, we change it to an open bracket if it is a closed one, or to a closed bracket if it is an open one. After this change, there will be one more closed bracket than open bracket after position A. Thus, there will be 2 more closed brackets than open brackets in total, i.e. 35 closed brackets and 33 open brackets. Note that every sequence of 35 closed and 33 open brackets will reach a point where the number of closed brackets exceed the number of open brackets, so every such sequence can be obtained from an invalid sequence of 34 open and 34 closed brackets using the above-mentioned procedure, in exactly one way. Therefore, every invalid sequence of 34 open and 34 closed brackets is in a one-to-one correspondence with a sequence of 35 closed and 33 open brackets.

The number of invalid sequences of 34 open and 34 closed brackets is equal to the total number of sequences of 35 closed and 33 open brackets, which is ${68 \choose 33}$ . The total number of sequences of 34 open and 34 closed brackets is ${68 \choose 34}$ , so the number of valid sequences is ${68 \choose 34} - {68 \choose 33}$ . Hence, the probability of getting a valid sequence of 34 open and 34 closed brackets is $\frac{{68 \choose 34} - {68 \choose 33}}{{68 \choose 34}} = 1 - \frac{{68 \choose 33}}{{68 \choose 34}} = 1 - \frac{68! 34! 34!}{68! 35! 33!} = 1 - \frac{34}{35} = \frac{1}{35}$ .

So the answer is $1 + 35 = \underline{36}$ .

(In fact, the number of valid sequences for any sequence of $n$ open and $n$ closed brackets is the $n^{th}$ Catalan number.)

This question is identical to: A string of parentheses is valid if there are an equal number of open and closed parentheses and if you begin at the left as you move to the right, add 1 each time you pass an open and subtract 1 each time you pass a closed parenthesis, then the sum is always non-negative. Let us assume that we already have the counts for pairs and we would like to obtain the count for n pairs. Let C i be the number of configurations of i matching pairs of parentheses, so, which can be obtained by direct counts. We know that in any balanced set, the first character has to be “(”. We also know that somewhere in the set is the matching “)” for that opening one. In between that pair of parentheses is a balanced set of parentheses, and to the right of it is another balanced set (A)B Where A and b are both balanced sets. Both A and B can contain up to n −1 pairs of parentheses, but if A contains k pairs, then B contains n – k – 1 pairs. Notice that we will allow either A or B to contain zero pairs, and that there is exactly one way to do so: don’t write down any parentheses. Thus we can count all the configurations where A has 0 pairs and B has n −1 pairs, where A has 1 pair and B has n −2 pairs, and so on. Add them up, and we get the total number of configurations with n balanced pairs. The fornula is: C n = C n-1*C 0+C n−2*C 1+•••+C 1*C n−2+C 0*C n-1

There is a special name for these numbers: Catalan Numbers. The formula for catalan numbers can be obtained through a bijection of triangulations of a n-gon
Given a polygon P with n+ 2 sides, first mark one of its sides as the base. If P is then triangulated, we can further choose and orient one of its 2n+1 edges. There are (4n+2)C n such decorated triangulations. Now given a polygon Q with n+3 sides, again mark one of its sides as the base. If Q is triangulated, we can further mark one of the sides other than the base side. There are (n+2)C n+1 such decorated triangulations. Then there is a simple bijection between these two kinds of decorated triangulations: We can either collapse the triangle in Q whose side is marked, or in reverse expand the oriented edge in P to a triangle and mark its new side. Thus C n+1*(n+2) =C n*(4n + 2) The binomial formula for C n follows immediately from this relation and the initial condition C 1 = 1: C n = 1/ n+1 * (2n)C(n) where C n stands for the nth catalan number while (a)C(b) stands for combination.

Back to the original question: total number of ways = (2n)C(n). number of valid ways = 1/(n+1)* (2n)C(n). so probability = (2n)C(n)/[1/(n+1)*(2n)C(n)]=1/(n+1) plug in n=34, we get 1/35. So a+b=36.

The number of arrangement such that $n$ opening brackets and $n$ closing brackets are well-ordered (i.e., it could have come from a valid mathematical expression) is well-known as Catalan Number: $\frac{1}{n+1}\binom{2n}{n}$

Since the total number of possible arrangement is $\binom{2n}{n}$ , the probability that it is well-ordered is $\frac{1}{n+1}$ . So since in this case $n=34$ , the probability is $\frac{1}{35}$ , and so the answer is $1+35=36$ .

Proof of Catalan Number: Each arrangement can be mapped to a walk in Cartesian coordinate from $(0,0)$ to $(n,n)$ , where opening bracket corresponds to a 1-unit rightward movement, and closing bracket corresponds to a 1-unit upward movement. We can verify that the number of arrangement is indeed $\binom{2n}{n}$ .

Next, a well-ordered arrangement corresponds to a walk that starts rightward, and do not cross the line $x=y$ (since crossing that line would mean that we have more upward movement than rightward movement, which implies more closing brackets than opening brackets).

We calculate the number of not well-ordered arrangement as follows:

Notice that for each walk that crosses the line $x=y$ , it will touch or cross the line $x=y-1$ . So we map the walks that crosses the line $x=y$ by reflecting on the line $x=y-1$ the part of those walks from $(0,0)$ to the point of touch with $x=y-1$ (so $(0,0)$ is mapped to $(-1,1)$ ). Now notice that each original walk that crosses the line $x=y$ is mapped to a reflected walk from $(-1,1)$ to $(n,n)$ because a walk from $(0,0)$ to $(n,n)$ touches or crosses the line $x=y-1$ if and only if the reflected walk crosses the line $x=y-1$ . And so the total number of not well-ordered walk is the number of walks from $(-1,1)$ to $(n,n)$ , which is $\binom{2n}{n+1}$ .

Therefore the total number of well-ordered walk is $\binom{2n}{n}-\binom{2n}{n+1} = \binom{2n}{n} - \frac{n}{n+1}\binom{2n}{n} = \frac{1}{n+1}\binom{2n}{n}$

The number of ways in which we can correctly match $N$ pairs of brackets is equal to the $N$ th Catalan number, $C_{N} = \frac{1}{N+1}{{2N}\choose{N}}$ . Hence the probability of making a correct arrangement is then: $P_{N} = \frac{C_{N}}{{2N}\choose{N}} = \frac{1}{N+1}$ . For $N = 34$ , this is $P_{34} = \frac{1}{35}$ ; hence, the desired sum is $\boxed{36}$ .

The number of ways to combine n pairs of parentheses in a valid way is the nth Catalan number, given by $\frac{2n!}{(n+1)! n!}$ . Since the total number of ways to write 34 open and closed brackets is ${68 \choose 34} = \frac{68!}{34!34!}$ , the probability is $\frac{1}{35}$ , which gives 36 as the answer.

The random way to put 34 open brackets and 34 closed bracket in a line is $\binom{34}{68}$ . Let $C(n)$ be the number of way to get valid mathematical expression from $n$ pairs of brackets. Using induction, we can see that $C(0) = C(1)= 1$ and $C(n) = C(0)C(n-1)+C(1)C(n-2)+...+C(n-1)C(0)$ . This is a form of Catalan number and in the other form, we have $C(n) = \frac{\binom{n}{2n} }{n+1}$ . So the wanted probability is $\frac{1}{35}$ and we have $a =1, b = 35 , a+b=36$ .

We can encode a sequence of open and closed brackets as a path drawn between lattice points in the Cartesian plane. We begin the path at $(0,0)$ and move up and to the right one place for an open bracket, or down and to the right one place for a closed bracket. The path for the sequence $()(()()(()))$ is shown in the figure below.

Any arrangement of $n$ open brackets and $n$ closed brackets will give such a path from $(0,0)$ to $(2n,0)$ . The arrangement will be from a valid mathematical expression if and only if the corresponding path does not dip below the x-axis. It is difficult to count directly the number of arrangements which do not go below the x-axis, but it is easier to count the number that do go below. For any arrangement that does go below the x-axis, the first point below the x-axis will be some point of the form $(2k+1,-1)$ . We can construct a second path from this by flipping the path after the point $(2k+1,0)$ along the line $x = -1$ . This path will be form the point $(0,0)$ to the point $(2n,-2)$ . An example is shown in the figure below, with the starting path solid, and the second path with a dashed line.

For each path that goes below the x-axis, we get a unique second path by this procedure. Also, every path between $(0,0)$ and $(2n,-2)$ can be arrived at by this procedure, so the number of paths from $(0,0)$ to $(2n,0)$ that dip below the x-axis is equal to the number of paths from $(0,0)$ to $(2n,-2)$ . These paths have $n+1$ down segments and $n-1$ up segments, so the number of such paths is $\binom{2n}{n-1}$ . The number of paths of our starting type is $\binom{2n}{n}$ . So the probability that the path does not dip below the x-axis is $\frac{\binom{2n}{n} - \binom{2n}{n-1}}{\binom{2n}{n}} = \frac{1}{n+1}$ . In this case, $n = 34$ , thus $a + b = 1 + 34 +1 = 36$ .

Mathematica:

1

CatalanNumber[34]/(68!/(34!34!))

$\frac{C_{34}}{\frac{68!}{34! 34!}}$

Probability is 1/(n+1)