Combinatorial Madness

A Follow-Up Post can be found here: Combinatorial Madness Follow-Up.

I've gone mad. Here I am on a Friday night, absolutely consumed by a combinatorial problem that I came up with to challenge myself a while back. Only tonight have I begun thinking about it more seriously. And, either it's quite difficult or I'm just not getting it. If anyone wants to give it a go, please do, then teach me how you were able solve it if you figure it out. Because, I think I'm kind of stuck.

This is long, but if you like numbers, you may enjoy this.

Here's the problem.

There are N potions. Combining any two potions will form a completely new potion. Thus, (A+B)+C does not equal A+(B+C), as A+B forms something completely new, call it E, and B+C forms something completely new, call it F. So the former is E+C which is completely different than A+F.

In a single iteration, two potions are combined. After N-1 iterations, there is a single final potion. The question is, how many different final products can be created starting with the N potions?

This is much more difficult than the trivial question, which is how many possible paths are there from N potions down to a final product. The total number of possible paths is clearly (N choose 2)*(N-1 choose 2)*(N-2 choose 2)*...*(2 choose 2). The total possible paths will overcount the total number of possible final products, as some paths will lead to the exact same potion.

Here's what my friend Duke and I have come up with...

N=2, clearly it's 1 possible final product.
N=3, clearly there are 3 possible final products.

For N=4, it starts getting a bit more interesting. Here's a way I came up with that helps us count the number of final products possible. If you think about it some, you will realize that with N=4, there are only 2 possible forms in which a final product can be created.

Here they are:

Form 1 = ((A+B)+C)+D
Form 2 = (A+B)+(C+D)

It should be clear that (A+(B+C))+D is an isomorphism, and doesn't give us a new final product.

Now, there are 4! ways in which we can arrange A, B, C, and D. But, we also notice that the order of A and B does not matter. Thus, we overcount by a factor of two. So, there are actually 4!/2 = 12 final products of Form 1.

For Form 2, we notice that we overcount by a factor of 2 three times (once for A/B, once for C/D, and once for AB/CD). So, we have 4!/(2^3) = 3 final products of Form 2.

So, for N=4, we have a total of 12+3 = 15 possible final products.

Following the same counting strategy for N=5, here are the possible forms.

Form 1: (((A+B)+C)+D)+E
Form 2: ((A+B)+C)+(D+E)
Form 3: ((A+B)+(C+D))+E

For Form 1, again we have overcounting by a factor of 2, so we get 5!/2 = 60 for N=5.
For Form 2, we overcount by a factor of 2 twice (2^2). So, this gives us 5!/4 = 30. Note that the order of (A+B) and (D+E) does matter, which is why we only overcount for (A,B) and (D,E) and not for (AB,DE).
For Form 3, we notice that (A+B) and (C+D) order does not matter, so we have an additional factor of 2 overcounting compared with Form 2. This gives us 5!/8 = 15.

So, for N=5, there are a total of 105 possible final products.

Since, I'm a real glutton for punishment, here's my attempt at N=6. I came up with 6 possible forms, hopefully I'm not missing any.

Here are the six forms I came up with for N=6:

(((A+B)+(C+D))+(E+F)) – I think this overcounts by factor of 2^3 (A/B, C/D, AB/CD) [Note: This is incorrect -- see the Edit at bottom.]
(((((A+B)+C)+D)+E)+F) – overcounts by factor of 2 (A/B)
((((A+B)+C)+(D+E))+F) – overcounts by factor of 2^2 (A/B, D/E)
((((A+B)+C)+D)+(E+F)) – overcounts by factor of 2^2 (A/B, E/F)
((((A+B)+(C+D))+E)+F) – overcounts by factor of 2^3 (A/B, C/D, AB/CD)
(((A+B)+C)+((D+E)+F)) – overcounts by factor of 2^3 (A/B, D/E, ABC/DEF)

This gives us 6!/2 = 360, 6!/4 = 180 (twice), 6!/8 = 90 (three times), which is 990 total possible final products.

I was really hoping that I would have come up with 945 total possible final products, but I just don't see where I've gone wrong above. Maybe I did, so if you spot a mistake, please let me know.

If it had been 945, then we have a double factorial pattern for odd values... 1*3*5*7*...*(2n-1). 1, 3, 15, 105, 945, 10395, etc.

But, since I can't convince myself that it's 945, I am officially stuck.

Anyone?


Edit:

(((A+B)+(C+D))+(E+F)) – I think this overcounts by factor of 2^3 (A/B, C/D, AB/CD) -- I neglected the E/F. This makes the overcounting factor 2^4, and that brings us to 945 possible final products for N=6. So, the solution is pretty much double factorial, but I do not have an actual proof. Will think about it, but maybe leave it to others, hehe.