Thread: 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!

Originally Posted by Ragnarok

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.

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.

Originally Posted by Ragnarok

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).

Hello, Ragnarok!

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

. . There are: . ways.





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


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


Are we to consider groupings like these?

. .

. .

. .


I hope not . . . Brrr . . .

Originally Posted by Soroban

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.

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?

Originally Posted by Ragnarok

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.

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!!!

Originally Posted by Ragnarok

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.)

Originally Posted by Soroban

Hello, Ragnarok!

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

















. . There are: . ways.





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


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


Are we to consider groupings like these?

. .

. .

. .


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 2^n-1. So thank you for helping.