Eclectic Enumeration

Define $[n]$ to be a arbitrary way to group $n$ numbers in the shown way and define $s(n)$ to be the number of ways to group $n$ numbers in the shown way.

Clearly, $s(1)=1$ and $s(2)=1$ .

Now note that $[3]=([1]+[2])\text{ or } ([2]+[1])$ so $s(3)=s(1)s(2)+s(2)s(1)=2$

In general, since $[n]=([1]+[n-1]), ([2]+[n-2]), \ldots , ([n-1]+[1])$ we have $s_n=\sum_{k=1}^{n-1}s(k)s(n-k)$

Applying this recursion, we attain $s(8)=\boxed{429}$ .

Note: these numbers are known as Catalan Numbers .

These are the famous Catalan Numbers. So the number of ways of inserting n pairs of parenthesis in n+1 letters is given by

C(n)= $\frac{^(2n^) C_n}{(n+1)}$ = $\frac{2n!}{(n!*(n+1)!)}$

Thus for n+1 letters=8, we have n=7 $\frac{(14)!}{(7!*(7+1)!)}$ solving which gives 429.

Let $N_{i}$ be the number of ways to group $i$ numbers in parenthesis.

Let's see the way to group 5 numbers

5 numbers can be grouped in two ways

$1.$ extreme parenthesis contains group of 1 and 4

$(a_{1})+(a_{2}+a_{3}+a_{4}+a_{5})$

No of permutations can be two .

The no of ways are $2 \times N_{1} \times N_{4} = 2 \times 1 \times 5 = 10$

$2.$ extreme parenthesis contains group of 2 and 3 $(a_{1}+a_{2})+(a_{3}+a_{4}+a_{5})$

No of permutations can be two .

The no of ways are $2 \times N_{2} \times N_{3} = 2 \times 1 \times 2 = 4$

Therefore the total number of ways are $N_{5}=10+4=14$ .

Similarly $N_{6}=42$

$N_{7}=132$

$N_{8}=429$

This can be solved also by a way of generating the expression of parentheses until some point of the string of numbers in some organized manner.

The way the parentheses will be introduced should start in this manner from the second term and finish with the n-1th term of the string where for each element there will be expressed the relation it has with the one which are anterior to it where this relation is of either accepting the anterior terms , that is summing up with them or their expressions before a summing with the ones after it or refusing it , that is not summing up with them. Now , observe that if one of the elements refuses to sum up with the other which is anterior the one which will come up next will have the possibility of accepting not just the one which is immediately anterior to it but also others anterior to it that have been refused therefore the number of possibilities for one term depending on the number of refuses until it. Considering this observe that if it is to count the elements this would imply a rule of counting which is not completely determined linearly and therefore would imply some sort of more complicated expression since for the choices that some element will take it will determine the number of ways the elements after it will get implying therefore that I can not make abstraction completely of this anterior choices to count everything correctly. To get rid of this difficulty while still making a constructive approach it might be useful to consider a way of generating them. For this consider then that the way of counting will be done by starting from a string of 2 elements from which then will be generated the solutions for strings of more elements but this based on a counting which would fit on the purposes of the constructive approach which is so by taking the elements one after the other. Explicitly what is going to be counted is the number of possible refusals that are taking place in the string , that is it will be tried to calculate how many expressions have 0 refusals , how many 1 , etc in a string until the n-1th term of the string and as I said starting from the second element in the string. To calculate this it can be observed that because the n-1th element of the string can accept the entire elements which have been refused until it for all the possible expressions that are generated until that point the number of elements that have 0 refusals until that n-1th term of expression and therefore in the entire string will be equal with the total number of expressions until it since it can generate for all those expressions 0 refusals , that for a number of 1 refusal it can generate also all the possible expressions until it and that since it can just put only one refusal in the expression all the expressions which will have 2 refusals will be resulted from all the other expressions which have at least 1 refusal (or all other with the exception of the expressions which have a number of 0 refusals) , next for2 refusal all the expression which have at least 2 refusal and so on. In order to count this number of expressions before one element it can be started from the simplest expression and move on. On this way the number of possible expressions by this generating rule and listing all of them from the least number of refusals to the maximum will be 1, 2 2 1 , 5 5 3 1 , 14 14 9 4 1 , 42 42 28 14 5 1 , 132 132 90 48 20 6 1 where the last listing of expressions corresponds to a string of 8 elements and they add to 429. There also might be a way of deriving this without listing but I was lazy thinking at it. This solution isn't complete and rigorous enough until it doesn't show that the way of deciding how the parenthesis are put , therefore the way of introducing them is correct based on the method considered but that would take a little bit more writing and maybe on things which can be grasped pretty easily so I didn't wrote that too.