Number of proper algebraic expressions

by luimichael, Oct 25, 2007, 7:15 AM

Given the set of digits {1,2,3,4,5,6,7,8,9}, the set of symbols {+, -, *, /, ^} and also a maximum number of 9 pairs of parentheses, find the number of all possible proper algebraic expressions.

Example
123 + 4^(98-7)*6
(1 * 2 * ( 3 + 4 - 5 ) ^78) / 9
*******************************************************************************
http://en.wikipedia.org/wiki/Catalan_number/
$ C_n$ is the number of different ways n + 1 factors can be completely parenthesized (or the number of ways of associating n applications of a binary operator). For n = 3 for example, we have the following five different parenthesizations of four factors:

((ab)c)d , (a(bc))d , (ab)(cd) , a((bc)d) , a(b(cd))

So, we can can conclude that the number of proper expressions with 8 operations and 9 digits is
$ C_8 * 5^8 *9!$ , because it is a complete parenthesization of 9 digits and 8 operations.
*******************************************************************************
Next, consider 7 operations and 8 operands:
Exactly 1 concatenation must be applied.
Example
1 # 2 # 3 & 4 # 5 # 6 # 7 # 8 # 9 <
> 1 # 2 # 34 # 5 # 6 # 7 # 8 # 9, where # is any one of the operations allowed in the question.
The number of proper expressions should be $ 8*(C_7*5^7*9!)$.
......

The total number of proper expressions should be
$ \sum_{k = 0}^8( C_k *5^k*9!)* C_{8 - k}^8$, where $ C_k$ represents the Catalan number and $ C_k^8$ represents the binomial coefficient.

Comment

0 Comments

a