Strings with brackets

The possible orders for parentheses are " _ ( _ ) _ ( _ ) _ " and " _ ( _ ( _ ) _ ) _ " where the _'s denote some amount of 1's.

Case 1: If our string is of the form " _ ( _ ) _ ( _ ) _ " , then we must place a one in gap #2 and in gap #4 to prevent the "()" substring from occurring. This yields $9 - 2 = 7$ free ones to place in the blanks. Since we have $7$ free ones and $4$ parenthesis that are dividers, by balls-and-urns, there are $\binom{7+4}{4} = 330$ possible strings in this case.

Case 2: If our string is of the form " _ ( _ ( _ ) _ ) _ " , then we must place a one in gap #3 to prevent the "()" substring from occurring. This yields $9 - 1 = 8$ free ones to place in the blanks. Since we have $8$ free ones and $4$ parenthesis that are dividers, by balls-and-urns, there are $\binom{8+4}{4} = 495$ possible strings in this case.

Thus, the total number of strings is $330 + 495 = \boxed{825}$ .

Ignoring the $1$ 's, we see that there are only two possible configurations of the parentheses: $()()$ and $( ( ) ).$ We take the first case:

Case 1: The parentheses are in the form $()()$

There are five possible places to put $1$ 's between the parentheses: $\_(\_)\_(\_)\_$ Because we can't have the substring $(),$ we must place at least one of the $1$ 's in the second and fourth places. That leaves $7$ $1$ 's left to put in the five places. We use the stars-and-bars technique to determine that there are $\binom{11}{4} = 330$ possible ways to place the ones in this case.

Case 2: The parentheses are in the form $(())$

Again, there are five possible places to put $1$ 's between the parentheses: $\_(\_(\_)\_)\_$ This time we must place a $1$ in the middle place to split up the two middle parentheses, leaving $8$ $1$ 's to place. Using stars-and-bars again, we find that there are $\binom{12}{4} = 495$ ways to distribute the $1$ 's.

Thus, in total there are $330+495=\boxed{825}$ strings that satisfy the conditions.

We can obtain the generating function for the sequence using the methods provided in Analytic Combinatorics

The required g.f would be: $G(z) =SEQ(z)\left(SEQ(z)\left(SEQ(z)z\right)SEQ(z)\right)SEQ(z) + SEQ(z)\left(SEQ(z)z\right)SEQ(z)\left(SEQ(z)z\right)SEQ(z)$ substitute each SEQ(z) with 1/(1-z), which is the g.f for sequence of z, hence:

$G(z) = \dfrac{z+z^2}{(1-z)^5}$

We find that $[z^n] = \binom{n+2}{4}+\binom{n+3}{4}$ , and the answer is $[z^9] = \binom{11}{4}+\binom{12}{4} = \fbox{825}$

The parentheses must occur in one of the two orders $()()$ or $(())$ .

In the first case there must be at least one $1$ between each () pair. Thus a valid sequence must be of the type $A(1B)C(1D)E$ , where $A,B,C,D,E$ are (possibly empty) strings of $1$ s which provide places for the other seven $1$ s. Thus we need to know in how many ways we can place the substrings " $(1$ ", " $)$ ", " $(1$ " and " $)$ " (in that order) amongst seven $1$ s. This is ${}^{11}C_4=330$ .

In the second case there must be at least one $1$ between the middle pair of parentheses. Thus a valid sequence must be of the type $A(B(1C)D)E$ , where $A,B,C,D,E$ are (possibly empty) strings of $1$ s which provide places for the other eight $1$ s. Thus we need to know in how many ways we can place the substrings " $($ ", " $(1$ ", " $)$ " and " $)$ " (in that order) amongst eight $1$ s. This is ${}^{12}C_4=495$ .

Thus there are $330+495=825$ acceptable sequences.

We will find the number of solutions meeting rules #2 and #3 first, then use inclusion-exclusion counting to account for rule #1.

Firstly, we need the number of arrangements like $111o11oo111o1$ , which is ${}^{13}C_{4}$ by definition. For each such arrangement there are $2$ possible ways we can insert the brackets to comply with rules #2 and #3: $oooo$ could correspond to either $(())$ or $()()$ .

Now to account for rule #1. The number of ways to position $()$ in a sequence, e.g. like $oooooooo()ooo$ is ${}^{12}C_{1}$ . And then the number of ways to change 2 $o$ 's to the two brackets is ${}^{11}C_{2}$ . Note that there was only $1$ possible ordering of brackets this time.

So, we have counted ${}^{12}C_{1} \times {}^{11}C_{2}$ sequences so far. However, for sequences containing a double violation of rule #1, we have counted those twice. The number of such sequences , e.g. $ooo()oooo()oo$ is ${}^{11}C_{2}$ .

Summarizing: $\begin{aligned} \text{Include} & {}^{13}C_{4} \\ \text{Exclude} & {}^{12}C_{1} \times {}^{11}C_{2} \\ \text{Include} & {}^{11}C_{2} \end{aligned}$ which works out to $1430 - 660 + 55 = \boxed{825}$

There are two cases:

Case 1: $(1)(1)$

Case 2: $((1))$

In the first case, we can distribute the remaining seven 1's in 5 places, namely a(b1)c(d1)e. So this is 11 choose 7 (the formula for distributing n things to k people is n + k - 1 choose n)

In the second case, we can distribute the remaining 8's to 5 places, namely a(b(c1)d)e. So this is 12 choose 8. In total this is 825.

Taking the second and third conditions together, there are only two ways to arrange the brackets and they are as follows.

Case 1 : ( ) ( ). Number of ways of arranging the brackets $=1$ . Now let us arrange the given $9 1's$ . There are 5 empty spaces near the brackets. Let us denote the number of $1's$ in these spaces as $a_{1}, a_{2}, a_{3}, a_{4}$ and $a_{5}$ . So the arrangement now looks like $a_{1} ( a_{2} ) a_{3} ( a_{4} ) a_{5}$ . To satisfy condition 1, we need at least one $1$ between each of the () substring i.e. $a_{2} \ge 1$ and $a_{4} \ge 1$ . The rest i.e. $a_{1}, a_{3}$ and $a_{5}$ $\ge 0$ . Now we know that $a_{1} + a_{2} + a_{3} + a_{4} + a_{5} = 9$ . Put $a_{2}=b_{2} + 1$ and $a_{4}=b_{4} +1$ so that each $b_{2}$ and $b_{4}$ is $\ge 0$ . Therefore the equation now becomes

$a_{1} + b_{2} + a_{3} + b_{4} + a_{5} = 9-1-1 = 7$ . Using stars and bars technique, the number of solutions to this equation $= \binom{7+5-1}{5-1} = \binom{11}{4} = 330$

Case 2 : ( ( ) ). Number of ways of arranging the brackets $=1$ . Proceeding just like we did in case 1, the arrangement now looks like $a_{1} ( a_{2} ( a_{3} ) a_{4} ) a_{5}$ . To satisfy condition 1, we need at least one $1$ between the () substring i.e. $a_{3} \ge 1$ . The rest i.e. $a_{1}, a_{2}, a_{4}$ and $a_{5}$ $\ge 0$ . Now we know that $a_{1} + a_{2} + a_{3} + a_{4} + a_{5} = 9$ . Put $a_{3}=b_{3} + 1$ so that $b_{3} \ge 0$ . Therefore the equation now becomes

$a_{1} + a_{2} + b_{3} + a_{4} + a_{5} = 9-1 = 8$ . Using stars and bars technique, the number of solutions to this equation $= \binom{8+5-1}{5-1} = \binom{12}{4} = 495$ .

Therefore, total number of strings possible $= 330 + 495 = 825$

If we consider only the parentheses, we see that the only two acceptable patterns are "()()" and "(())". Therefore, we take these two to be different cases.

For the case "()()". We need a 1 in between each pair of parentheses as to not have the substring "()". This gives us "(1)(1)", but we have 7 more 1's to be distributed into 5 slots (the underscores) " _ (1 _ ) _ (1 _ ) _ ". By stars and bars, there are $\binom{7+4}{4} = 330$ ways to do this. The second case proceeds similarly but only 1 "1" is committed to "((1))" giving us 8 more 1's to be placed in 5 slots. This can be done in $\binom{8+4}{4} = 495$ ways. Which means that the total number of acceptable strings is $330 + 495 = \boxed{825}$ .

Because of the last two conditions, the only orders in which the parentheses can come in are ( ) ( ) and ( ( ) ). In the process of counting, we will first count the number of valid strings where the substring "( (" does not occur, and then we will add back in the valid strings that do contain "( (".

Because the substring "( )" never occurs, we will package each "(" with a 1, forming two packages of "( 1". Note that since "( 1" always come together, the substring "( (" never occurs. To count for each ordering, note that there are $13 - 2 = 11$ places where we can put our four parenthesis. Since there are two orderings in which we can place the parentheses, the number of valid strings not containing "( (" is $11 \choose 4$ $\times 2 = 660$ .

In the ( ) ( ) ordering, the substring "( (" will never occur. To count the number of valid strings containing "( (" in the ( ( ) ) ordering, we package the two "(" with a 1, forming one package of "( ( 1". There are again 11 spaces to choose from, and 3 things to place, thus the number of valid strings containing "( (" is $11 \choose 3$ $= 165$ .

The total number of valid strings is $660 + 165 = 825$ .

A valid string formed

Type 1 :--- ( --- ( --- ) --- ) ---

or

Type 2 --- ( --- ) --- ( --- ) ---

Let a, b, c, d ,e is number of 1's in ---

With type 1, (a, b, c, d, e) is solution to the system above

(1) a + b + c + d + e = 9

(2) a, b, c, d >= 0

(3) c >= 1

This system have 495 solutions

With type 2, (a, b, c, d, e) is solution to the system above

(1) a + b + c + d + e = 9

(2) a, c, d >= 0

(3) b, d >= 1

This system have 330 solutions

So, number of valid strings is 495 + 330 = 825

There are two ways in which the parentheses can be ordered (leaving the ones aside): "()()" and "(())". We will consider each case separately.

In the first case, both '(' characters must be followed by a '1', so we may as well add a '1' and treat the combination as one character. We then have 11 characters, that need to be placed in order. We can freely choose on which 4 of the 11 places we put the parentheses, after which we fill up the rest with ones. The total number of combinations in this case is thus $\binom{11}{4} = 330$ .

The second case is similar, except that now only the second '(' needs to be followed by a '1'. Proceeding along similar lines, we now have 12 characters, and find a total of $\binom{12}{4} = 495$ combinations.

The total number of strings is thus $330+495 = \boxed{825}$

Ignoring the 1s, we get essentially two kinds of strings: those with $()()$ and those with $(())$ .

Since we may not create the substring $()$ , we can append a $1$ to the right of every opening bracket whose next bracket is the closing bracket. This more or less means if we let $A$ to be the string $(1$ , the strings in the first paragraph can be transformed to $A)A)$ and $(A))$ . (The first opening bracket in the second string is not converted to an $A$ , because the next bracket is still an opening bracket; $((111111111))$ is a valid string, but the first opening bracket doesn't have any $1$ to the immediate right of it.)

• Case 1: The string is in the form of $A)A)$ .

We have used two 1s, so we only have seven more 1s. Now if we let a string of 11 characters, seven of them being 1s and four of them being X's, and later replace the X's in the order $A)A)$ from the left, we create a bijection between valid strings in Case 1 and strings of 1s and X's. (An example string is $11X1XX11X11$ , which will be transformed to $11A1)A11)11$ and in turn becomes $11(11)(111)11$ .) It's easy to see why the relation is a bijection (just perform the transformations or the reverse of them to bring a kind of string to the other), so there are $\binom{11}{4} = 330$ strings in this case.

• Case 2: The string is in the form of $(A))$ .

We have used one 1, so we only have eight more 1s. We use a similar transformation, now with 12 characters instead (eight 1s and four X's), and we replace the X's in the order $(A))$ instead. (An example string is $11X1XX11X11$ , which will be transformed to $11(1A)11)11$ and in turn becomes $11(1(1)11)11$ .) There are $\binom{12}{4} = 495$ strings in this case.

In total, there are $330 + 495 = \boxed{825}$ strings.