## Parenthize

I have a string of N characters containing M(<N) words. Can you tell me how many way I can parenthize this string ?

So so COOL not kewl
 PhysOrg.com science news on PhysOrg.com >> King Richard III found in 'untidy lozenge-shaped grave'>> Google Drive sports new view and scan enhancements>> Researcher admits mistakes in stem cell study
 Sum(n-i,i,1,n-1)

Recognitions:
Gold Member
 Quote by Vance I have a string of N characters containing M(
Do we use ordinary rules of pu(nctua)tion?

Parenth(eses are not allo)wed to break( up (words), or be) nested?

If one cannot break up words, then I think the number N of characters does not matter, only the number M of words matters.

It does seem to matter whether or not you want to allow nesting parens.

Recognitions:
Gold Member

## Parenthize

 Quote by Healey01 Sum(n-i,i,1,n-1)
hi Healey, I dont know this notation, can you give an example
or explain it simply?
If there were just 4 words, how would your formula work to give
the number of different ways to parenthesize?
 I assumed that you cannot parenthesize throughout words, like splitting them up. He states that there are M words, with M < N. So the maximum amount of words would be N-2 single characters, then a double character word. like a 4 letter max would be : a b cd in order to have M
 is this allowed ? (a) (b) (cd) and this a (b) (cd) Also we may have a bcd can't we?  on healey's notation sum(m-i,i,0,m-1) means sum over m-i where i goes from 0 to m-1 [/edit]
 ahh, i forgot about multiple parenthesis. Theres a lot then. Im working on the formula right now. PS: Is there a mathematical operator "$"(ill call it arbitrarily) such that 6$ = 6+5+4+3+2+1+0 ? sort of like 6! = 6*5*4.... but with addition? I hate writing out the sums everytime. PPS : Oh, and im assuming he's looking for the maximum allowed given that you cant split words. So just ignore the character number. UNLESS (crazy hard) everytime you add a parenthesis it counts as a character, so you can have that many less characters in your string... Oh and is this allowable? (The (swift) red) (fox).
 Recognitions: Gold Member Science Advisor $$n + (n-1) + .... + 2 + 1 = \sum_{i=1}^n i = \frac{n^2 + n}{2}$$

 Quote by Vance I have a string of N characters containing M(
If parenthesis cant break up words, and if parenthesis cant be nested , then the answer is:

$$\#ways(M) = \left(\frac{5+\sqrt{5}}{10}\right) \left(\frac{3+\sqrt{5}} {2}\right)^M + \left(\frac{5-\sqrt{5}}{10}\right) \left(\frac{3-\sqrt{5}} {2}\right)^M -1$$

I'm not counting the 'no parenthesis at all' case. So, if M=1 then #ways=1, for instance .
But, of course you may remove the '- 1' at the end.
 Rogerio, Brilliantè!! Your formula seems to be agreeing with my calculations for a first few terms .... may/can i have a hint for the method u have taken? -- AI P.S : By the look of the formula, u seem to have got some recursive equation is it?
 Wow, thanks TenaliRaman ! You are right, it was a 'recurrence' approach...:-) A little bit more in white: Consider all the combinations with the initial words: a b...f When you add a new word, you get: combinations with the new last word free (not enclosed in parentheses) : thee old '...f' becomes '...f x' combinations with the new the last word enclosed in parentheses and alone: the old '...f' becomes '...f (x)' combinations with the new last word enclosed in parentheses but not alone: the old '...f)' becomes '...f x)' Hmmm... is it enough ?
 But Ofcourse! F(m) = 2*F(m-1)+ [\sum_{i=1}^{m-2} F(i)] .. * F(m-1) = 2*F(m-2) + [\sum_{i=1}^{m-3} F(i)] .. ** Simplifying with * and **, we get F(m) = 3*F(m-1) - F(m-2) and the rest is ofcourse mechanical. Good Job! -- AI