Results 1 to 11 of 11

Math Help - Find all ways of grouping five multiplied numbers

  1. #1
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1

    Find all ways of grouping five multiplied numbers

    I am working through Israel Gelfand's book "Algebra" and am stuck on the following problem:

    Find all possible ways to put parentheses in the product 2*3*4*5*6 (not changing the order of factors). Try to invent a systematic way of searching so as not to forget any possibilities.

    I calculated 16 possibilities by rote before giving up (there may be more), and the only thing I accomplished in the way of "systematic" was stating that in any sequence of five numbers there are four operations to be performed. Perhaps it's the late hour, but I can't get beyond this. Any suggestions?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Ragnarok View Post
    I am working through Israel Gelfand's book "Algebra" and am stuck on the following problem:

    Find all possible ways to put parentheses in the product 2*3*4*5*6 (not changing the order of factors). Try to invent a systematic way of searching so as not to forget any possibilities.

    I calculated 16 possibilities by rote before giving up (there may be more), and the only thing I accomplished in the way of "systematic" was stating that in any sequence of five numbers there are four operations to be performed. Perhaps it's the late hour, but I can't get beyond this. Any suggestions?

    Thanks!
    The number of ways to fully parenthesize a product is a well known result in combinatorics

    Catalan number - Wikipedia, the free encyclopedia

    But I'm not sure if this is what the question is after, since from the wording it seems a non-fully parenthsized expression such as (a)bcde would (might?) be acceptable. Anyway I'll give a shot listing out the 14 fully parenthesized expressions

    I found it much easier to list the rooted trees rather than the parenthesized expressions. I made an image, they are listed in a systematic order, and you can convert them to expressions accordingly.
    Attached Thumbnails Attached Thumbnails Find all ways of grouping five multiplied numbers-catalan4.png  
    Last edited by undefined; September 22nd 2010 at 06:05 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1
    Thank you for your reply! According to the Wikipedia page there should be 14 possibilities, and therefore I must have counted some twice. But do you know how to go about solving this without reference to the Catalan formula?

    About the wording, I think it is just poorly chosen. The problem is asking the same thing as in the Wikipedia article.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Ragnarok View Post
    Thank you for your reply! According to the Wikipedia page there should be 14 possibilities, and therefore I must have counted some twice. But do you know how to go about solving this without reference to the Catalan formula?

    About the wording, I think it is just poorly chosen. The problem is asking the same thing as in the Wikipedia article.
    Edited my first post! Took a while to make it look (relatively) pretty in MS paint after doing it on paper. The system I used was to try to left-associate as much as possible, then keep the first three branchings fixed while changing the last branching until exhausting the possibilities, then going up a level and doing it again until everything is right-associated (kind of hard to explain, but if you look at it enough or try reproducing it you should see it).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,659
    Thanks
    600
    Hello, Ragnarok!

    I have a broader interpreation of this problem.
    If I'm right, the problem is quite complex.


    \text{Find all possible ways to put parentheses in the product }2\cdot3\cdot4\cdot5\cdot6
    \text{without changing the order of the factors.}

    \text{Try to invent a systematic way of searching to find }all\text{ possibilities.}

    \begin{array}{cccc}\text{Divide the factors into 5 groups:} &<br />
(a)(b)(c)(d)(e) \end{array}\quad \text{1 way}


    \text{Divide the factors into 4 groups: }\;\begin{array}{c}<br />
(ab)(c)(d)(e) \\(a)(bc)(d)(e) \\ (a)(b)(cd)(e) \\ (a)(b)(c)(de) \end{array}\quad \text{ 4 ways}


    \text{Divide the factors into 3 groups: }\;\begin{array}{c}<br />
(abc)(d)(e) \\ (ab)(cd)(e) \\ (ab)(c)(de) \\ (a)(bcd)(e) \\ (a)(bc)(de) \\ (a)(b)(cde) \end{array}\quad \text{ 6 ways}


    \text{Divide the factors into 2 groups: }\;\begin{array}{c}<br />
(a)(bcde) \\ (ab)(cde) \\ (abc)(de) \\ (abcd)(e) \end{array} \quad \text{ 4 ways}


    \text{Divide the factors into 1 group: }\;\;\;\begin{array}{c}(abcde)\end{array} \quad \text{ 1 way}


    . . There are: . 1 + 4 + 6 + 4 + 1 \:=\:16 ways.


    \text}For }\,n\text{ factors, there are }2^{n-1}\text{ ways to insert parentheses.}


    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~


    However, my interpretation opens the door to another realm,
    . . one I do not want to explore . . .


    Are we to consider groupings like these?

    . . \bigg((ab)(c)\bigg)(d)(e)

    . .  (ab)\bigg((c)(d)\bigg)(e)

    . .  (ab)(c)\bigg((d)(e)\bigg)


    I hope not . . . Brrr . . .
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Soroban View Post

    However, my interpretation opens the door to another realm,
    . . one I do not want to explore . . .
    That could be an interesting problem in recursion. There are other interpretations as well, such as

    1) Allow only expressions gotten from fully parenthesized expressions, but removing some number (possibly 0) of matched parentheses, e.g. (ab)cde is valid but (a)bcde is not.

    2) Allow any expression that does not have double-parentheses, e.g. ((a))bcde is not allowed but (a)bcde is.

    Of course it's not very interesting with no restrictions since we get infinite a, (a), ((a)), (((a))), etc.
    Last edited by undefined; September 22nd 2010 at 10:06 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1
    Undefined, thank you so much for going to the trouble to create the picture! That helped me a ton. So, with problems like the one Soroban mentioned, is there not a relatively simple mathematical way of calculating the possibilities without resorting to a whole lot of graph-making?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Ragnarok View Post
    Undefined, thank you so much for going to the trouble to create the picture! That helped me a ton. So, with problems like the one Soroban mentioned, is there not a relatively simple mathematical way of calculating the possibilities without resorting to a whole lot of graph-making?
    I think it depends largely on the particular problem, also whether we want merely to count the possibilities, or enumerate them. For example we can derive the formula for the number of possibilities in Soroban's first interpretation by writing

    a | b | c | d | e

    notice there are n-1 vertical bars, each bar can be "on" or "off" and there is a bijection between the configurations of bars and the grouping by parentheses, thus we get 2^(n-1). To generate, we could write a computer program that iterates through all integers in the range {0, 1, ... , 2^(n-1)-1} and converts the integer to binary, then converts the binary string to the corresponding parentheses grouping.

    In other cases we can find a recursion, for example notice the recursive formula given here for Catalan numbers

    Catalan number - Wikipedia, the free encyclopedia

    which corresponds to looking at binary trees with n+2 leaves (thus n+1 internal nodes) as split into two subtrees, one to the left of the root with i internal nodes and the other to the right of the root with n-i internal nodes, where i ranges from 0 to n. A computer program could be written to do this relatively quickly. (Counting would of course be faster than enumerating.)

    Some of the other possible variations seem more difficult than these two examples, nevertheless it might be possible to find some relatively simple recursive/combinatoric solution if one looks hard enough.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Apr 2010
    Posts
    116
    Thanks
    1
    Ah, I see. It is more complicated than I expected, given the level of the book. I just wanted to make sure that I wasn't missing anything obvious (which I tend to do). Nevertheless, it is an interesting problem.

    Thank you again!!!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Ragnarok View Post
    Ah, I see. It is more complicated than I expected, given the level of the book. I just wanted to make sure that I wasn't missing anything obvious (which I tend to do). Nevertheless, it is an interesting problem.

    Thank you again!!!
    You're welcome! Might be worth mentioning there is also a straightforward recursion for Soroban's first interpretation. Fix the first group as (a) and then view bcde as another instance of the original problem (with different n). Then fix the first group as (ab) and view cde as an instance of the problem, etc. The right group is allowed to be empty, but the left is not.

    Hope I didn't make it seem more complicated than it really is. I think in a way recursions can be both simple and complex simultaneously. (Of course I'm being pretty loose with semantics.)
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member DIOGYK's Avatar
    Joined
    Aug 2012
    From
    Norway
    Posts
    39

    Re: Find all ways of grouping five multiplied numbers

    Quote Originally Posted by Soroban View Post
    Hello, Ragnarok!

    I have a broader interpreation of this problem.
    If I'm right, the problem is quite complex.



    \begin{array}{cccc}\text{Divide the factors into 5 groups:} &<br />
(a)(b)(c)(d)(e) \end{array}\quad \text{1 way}


    \text{Divide the factors into 4 groups: }\;\begin{array}{c}<br />
(ab)(c)(d)(e) \\(a)(bc)(d)(e) \\ (a)(b)(cd)(e) \\ (a)(b)(c)(de) \end{array}\quad \text{ 4 ways}


    \text{Divide the factors into 3 groups: }\;\begin{array}{c}<br />
(abc)(d)(e) \\ (ab)(cd)(e) \\ (ab)(c)(de) \\ (a)(bcd)(e) \\ (a)(bc)(de) \\ (a)(b)(cde) \end{array}\quad \text{ 6 ways}


    \text{Divide the factors into 2 groups: }\;\begin{array}{c}<br />
(a)(bcde) \\ (ab)(cde) \\ (abc)(de) \\ (abcd)(e) \end{array} \quad \text{ 4 ways}


    \text{Divide the factors into 1 group: }\;\;\;\begin{array}{c}(abcde)\end{array} \quad \text{ 1 way}


    . . There are: . 1 + 4 + 6 + 4 + 1 \:=\:16 ways.


    \text}For }\,n\text{ factors, there are }2^{n-1}\text{ ways to insert parentheses.}


    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~


    However, my interpretation opens the door to another realm,
    . . one I do not want to explore . . .


    Are we to consider groupings like these?

    . . \bigg((ab)(c)\bigg)(d)(e)

    . .  (ab)\bigg((c)(d)\bigg)(e)

    . .  (ab)(c)\bigg((d)(e)\bigg)


    I hope not . . . Brrr . . .
    I think you are correct in this one, I am also kind of stuck with this problem in Gelfand's book and I think I counted every possibility for 2*3*4*5*6 and I always get 16 an result which can also be calculated by 2n-1. So thank you for helping.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Grouping natural numbers.
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 23rd 2011, 11:35 AM
  2. Replies: 9
    Last Post: July 12th 2011, 11:08 AM
  3. Replies: 1
    Last Post: November 6th 2010, 12:33 PM
  4. Grouping numbers
    Posted in the Statistics Forum
    Replies: 1
    Last Post: May 7th 2010, 04:38 PM
  5. [SOLVED] [SOLVED] Grouping numbers
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 13th 2007, 05:38 PM

Search Tags


/mathhelpforum @mathhelpforum