0
$\begingroup$

I am trying to find formula which would calculate the number of possible unique combinations which I can later write in programming language. Please excuse my choice of words or terms (and lack of proper math formulas) as my math skills are somewhat limited.

General description and rules:

  • you have "n" items which can be "merged" together
  • you need at least 2 items to "merge" new one
  • if you merge items the original ones are consumed and can't be reused for further "merge"
  • at each step you can "merge" only 2 items at once
  • it doesn't matter if you merge "a+b" or "b+a" as the resulting new item will be same
  • you can continue "merging" the items until you are left with only 1 item

My analyses:

  • it's should be calculated using combinations without repetition (order in pair doesn't matter) and maybe permutation?
  • there is probably one formula which is valid for any number of "n"

What I have now:

  • main part of the formula is combin(n,k) where k=2
  • I don't know how to make general formula, so I will write down examples and specific formulas

Examples:

n=1: n<2, result is 0
n=2: combin(n,2)=1
n=3: combin(n,2)+(combin(n,2)*(n-2))=3+3=6
n=4: combin(n,2)+(combin(n,2)*(n-2))+(combin(n,2)*(n-2)*(n-3))=6+12+12=30
n=5: following same logic..

At this stage I have thought that I have covered all combinations, so I have tried to manually list them for verification. For n<=3 it worked fine, but for n=>4 I have realised that I am missing what I internally called "inner" combinations. Here is my try to represent all n=4 combinations, where the "inner" ones are the last 3:

a+b
a+c
a+d
b+c
b+d
c+d
ab+c
ab+d
ac+b
ac+d
ad+b
ad+c
bc+a
bc+d
bd+a
bd+c
cd+a
cd+b
abc+d
abd+c
acb+d
acd+b
adb+c
adc+b
bca+d
bcd+a
bda+c
bdc+a
cda+b
cdb+a
ab+cd
ac+bd
bc+ad

This gave me 33 combinations whereas I was expecting only 30, so my assumption is that either the formula is wrong (more complicated) or some of the combinations listed above are in fact duplicate although it doesn't seems so.

Conclusion:

I was trying to wrap my head around this, googling many examples of combinations and trying to fit them to my problem, but without any luck. Also I was trying to consult it with some friends of mine, but none offered any real insight, so I am trying my luck here as my knowledge in this field of math is limited.

Programming thoughts:

I have currently implemented version with above formula, but it's not very effective solution as I am running out of memory at certain number of items and "depth". Depth is my internal term and parameter which I am using to limit the number of combinations the program is checking. I guess it can be considered as number of iterations? The reason why I am running out of memory is that I am storing the result of previous "depth" and calculating next one. I know there should be a better way how to do it and after reading some more articles about combinatorics I am starting to think about it as a tree structure. This should give me possibility to reduce the memory footprint to minimum and be going through the combinations like through branches. This in theory should also allow me to implement some multi-threading and take advantage of multi core processors.

Questions:

  1. Is the formula correct or not?
  2. If it's correct how it can be simplified?
  3. If it's wrong how should look correct one?
  4. Any general idea how to program it?

I would be grateful for any help regarding this problem and if something is unclear or missing please let me know.

Thanks

$\endgroup$
  • $\begingroup$ So you never explicitly stated what you're trying to count. It sounds like you're starting with n basic objects, and want to know how many composite objects are possible, where composite objects are considered distinct iff their components are distinct. Is that correct? $\endgroup$ – Gabriel Burns Sep 12 '16 at 19:20
  • $\begingroup$ I am trying to count all possible "merges" until there's only 1 final item left. $\endgroup$ – Stileth Sep 13 '16 at 6:05
0
$\begingroup$

If I understood correctly, you are looking for the number of ways to "bracket" n elements, while each bracket stands for one merge.

Take $n=3$ for example: Then $(a+b)+c$ would be the same as $(b+a)+c$ or $c+(a+b)$, but not the same as $a+(b+c)$.

If that is what you mean, consider this recursive formula: Let $a_n$ be the number of ways to bracket n elements. Then $a_0 =0,$ $a_1=1,$ and for $n \geq 2$ $$2 a_n = \sum_{k=1}^{n-1} {n \choose k} a_k a_{n-k} = \sum_{k=0}^{n} {n \choose k} a_k a_{n-k}$$ For the recursion consider the last addition you would compute: it divides the n elements into two subsets of size $k$ and $n-k$ that are bracketed separately. The factor 2 is due to each possibility being counted twice as you can switch the two subsets. The second equality holds because $a_0=0$.

To solve this recursion, look at the exponential generating function $A(z)=\sum_{n\geq 0}\frac{a_n}{n!}z^n$. Then $$A(z)^2=\sum_{n \geq 0} \left( \sum_{k=0}^n \frac{a_k}{k!} \frac{a_{n-k}}{(n-k)!}\right) z^n = \sum_{n \geq 0} \frac{1}{n!} \left( \sum_{k=0}^n {n \choose k}a_k a_{n-k}\right) z^n$$ Since $a_0=0$, you can start the sum at 2, and use the recursion: $$A(z)^2=\sum _{n\geq 2} \frac{2 a_n}{n!} z^n= 2\left( A(z) - z\right)$$ Now, with $A(0)=a_0=0$ you can conclude that $$A(z)=1 - \sqrt{1-2z}$$ To get to our coefficients $a_n$, you can look at the Taylor series at $z=0$: $$\sum_{n \geq 0} \frac{a_n}{n!} z^n = A(z) = \sum_{n \geq 0} \frac{A^{(n)}(0)}{n!}z^n$$ And thus $$a_n = \frac{d^n}{dz^n}\left(1-\sqrt{1-2z}\right) \Bigr|_{z=0}$$ For $n\gt 1$ this yields $$a_n = (1-2z)^{-\frac{2n-1}{2}}\cdot \prod_{k=1}^{n-1}(2k-1)\Bigr|_{z=0} = \prod_{k=1}^{n-1}(2k-1)=1\cdot 3 \cdot \ldots \cdot 2n-3$$ (Seeing this result, I suppose there must be an easier combinatorial argument.)

Lastly, one thing I noticed after writing this up: In your example, you have counted those cases in which not all elements are used - for that number $b_n$, just calculate $$b_n = \sum_{k=2}^n {n \choose k} a_k$$ Here, $k$ is the amount of elements used - for each $k$, there would be $n \choose k$ possibilities to choose them and $a_k$ possibilities to bracket them.

$\endgroup$
  • $\begingroup$ First of all, thank you very much for your input. Maybe I should have stressed it before, but my math is sort of limited :) I was trying in past days to understand what you wrote, but majority of it is beyond my knowledge. I will continue to work on understanding it, but maybe if I can ask for some clear output for me. What is the final formula I should use? Did you try to verify it with the example above? And yes, you have understood it correctly. $\endgroup$ – Stileth Sep 20 '16 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.