Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

String of N characters containing M(<N) words

  1. Sep 3, 2004 #1
    I have a string of N characters containing M(<N) words. Can you tell me how many way I can parenthize this string ? :shy:

    So so :cool: COOL not kewl
  2. jcsd
  3. Sep 3, 2004 #2
    Last edited: Sep 3, 2004
  4. Sep 3, 2004 #3


    User Avatar
    Science Advisor
    Gold Member
    Dearly Missed

    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.
  5. Sep 3, 2004 #4


    User Avatar
    Science Advisor
    Gold Member
    Dearly Missed

    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?
  6. Sep 3, 2004 #5
    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<N.

    Then possible parentheticals are
    (a) b cd
    (a b) cd
    (a b cd)
    a (b) cd
    a (b cd)
    a b (cd)

    cause you cant split "cd"

    Then you see its just what i wrote as a sum
    for the starting parenthesis in front of a you have m possibilities, which is n-1 possibilities.
    For the parenthesis in front of "b' you have 2, or m-1 possibilities, or n-2 possibilities.

    I guesss SUM(m-i,i,0,m-1) would work too.
  7. Sep 3, 2004 #6
    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 over m-i
    where i goes from 0 to m-1
  8. Sep 3, 2004 #7
    ahh, i forgot about multiple parenthesis. Theres a lot then. Im working on the formula right now.

    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).
    Last edited: Sep 3, 2004
  9. Sep 3, 2004 #8


    User Avatar
    Science Advisor
    Gold Member

    [tex]n + (n-1) + .... + 2 + 1 = \sum_{i=1}^n i = \frac{n^2 + n}{2}[/tex]
  10. Sep 5, 2004 #9
    If parenthesis cant break up words, and if parenthesis cant be nested , then the answer is:

    [tex] \#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 [/tex]

    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. :smile:
    Last edited: Sep 5, 2004
  11. Sep 6, 2004 #10

    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?
  12. Sep 7, 2004 #11
    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 ? :smile:
    Last edited: Sep 7, 2004
  13. Sep 7, 2004 #12
    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
    Last edited: Sep 7, 2004
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook