1
$\begingroup$

For a given set of elements lets say $s=\{A,B,C,D\}$ I want to compute how many unique elements can be obtained converting the initial set in subsets of size two (pairs). Pairs can be made taking two elements or one element and two elements previously grouped, all the elements of the set must be used and the order of the pairs doesn't matter. For example $(((A,B), C), D)$ would be an answer and $((A, B), (C, D))$ another valid one for the previous set. As the order doesn't matter I can use the next formula ($h$ is the length of the set):

$$ \sum\limits_{i=3}^h \binom {i} {2} $$

This formula can be used as recursively in every step one element is removed and the subsets of size $2$ are computed for the new length. The problem is that when $h >= 4$ it includes duplicates. For example for $h = 5$ it gives $180$ but there are only $105$ unique solutions. For example The solution $( ((A,B), C), (D, E) )$ is counted twice. Is there any way to count the duplicates and therefore express a formula for unique values given the length of the set $(h)$?

$\endgroup$
7
  • $\begingroup$ To make sure that we get the problem right: what is the correct answer for h=4 ? $\endgroup$ Commented Jan 31, 2014 at 16:53
  • $\begingroup$ The correct answer for h=4 is 18 $$\binom {4} {2} * \binom {3} {2}$$. I can enumerate all the answers if it helps $\endgroup$ Commented Jan 31, 2014 at 16:57
  • $\begingroup$ Mmm I count 12 of the form (A,(B,(C,D))) and 3 of the form ((A,B),(C,D)). What I'm missing? $\endgroup$ Commented Jan 31, 2014 at 17:03
  • $\begingroup$ Sorry you are right, the formula counts the pairs of the form ((A,B), (C,D)) twice there are 15 uniques and the formula counts 18. I have updated the question to reflect that duplicates start at h=4 $\endgroup$ Commented Jan 31, 2014 at 17:11
  • $\begingroup$ For $h=5$ I get 135... $\endgroup$ Commented Jan 31, 2014 at 17:23

1 Answer 1

Reset to default
1
$\begingroup$

I didn't get a formula or algorithm, but in case this helps:

Consider all full rooted binary trees with $h$ leaves. Restrict them to the unbalanced ones, such that each right inner node has at least as descendants as its left sibling. Call that set of trees $I_h$. For each tree $i \in I_h$, let $e_i$ be the count of its balanced inner nodes: those nodes that have equal number on descendants on each branch. Then the number we want is given by

$$S(h)= \sum_{i\in I_h}\frac{h! }{2^{e_i}}$$

For example, for $h=4$ we have two trees (one fully balanced, with $e_1=3$, fully unbalanced with $e_2$=2) so

$$S(4) = \frac{4!}{2^3}+\frac{4!}{2} = 3+12=15$$

For $h=5$ I count three trees and

$$S(5) = \frac{5!}{2^2}+\frac{5!}{2^3}+\frac{5!}{2} = 30 + 15 + 60=105$$

For $h=6$ I get (if didn't miss anything)

$$S(h) = 6! \left(\frac{1}{2^3} +\frac{1}{2^4} +\frac{1}{2^2}+\frac{1}{2^1}+\frac{1}{2^3}+\frac{1}{2^2}\right)=945$$

Update: Looking for the sequence in OEIS, it seems that the answer is given by A001147

$$S(h) =(2h-3)!! = 1 \times 3 \times 5 \cdots (2h-3)$$

Update: Here's a Java efficient code

public class CountPairings { int MAX_H = 20; long[][] trees = new long[MAX_H + 1][]; /** * index: amount of internal balanced nodes (from 1), value: how many trees */ public long[] computeTrees(int h) { if (trees[h] == null) { if (h == 1) trees[h] = new long[] { 1, 0 }; else if (h == 2) trees[h] = new long[] { 0, 1 }; else { long[] t = new long[h]; for (int h1 = 1, h2 = h - 1; h1 <= h2; h1++, h2--) { long[] t1 = computeTrees(h1); long[] t2 = computeTrees(h2); // cartesian product for (int i1 = 0; i1 < t1.length; i1++) { if (t1[i1] == 0) continue; for (int i2 = 0; i2 < t2.length; i2++) { if (t2[i2] == 0) continue; int ix = i1 + i2; if (h1 == h2) ix++; t[ix] += t1[i1] * t2[i2]; } } } trees[h] = t; } } return trees[h]; } public long countCombinations(int h) { long c = 0, fact = 1, pow2 = 1; for (int i = 2; i <= h; i++) fact *= i; long[] t = computeTrees(h); for (int i = 1; i < t.length; i++) { pow2 *= 2; c += fact * t[i] / pow2; } return c; } public static void main(String[] args) { CountPairings cp = new CountPairings(); for (int h = 2; h <= 12; h++) { long c = cp.countCombinations(h); System.out.printf("%2d %d\n", h, c); } } }

Output:

 2 1 3 3 4 15 5 105 6 945 7 10395 8 135135 9 2027025 10 34459425 11 654729075 12 13749310575
$\endgroup$
5
  • $\begingroup$ Thanks for accepting the answer, but perhaps you'd prefer to un-accept it (there is no hurry) to attract other answers. $\endgroup$ Commented Jan 31, 2014 at 18:31
  • $\begingroup$ Ok! although your answer is not a formula is a valid answer. Thank you for that! Also the discussion with you helped me to get a deeper understanding of the problem and to code an efficient algorithm to enumerate the unique answers. Thanks!! $\endgroup$ Commented Feb 1, 2014 at 1:47
  • $\begingroup$ You're welcome. You have an afficient algorithm for arbitrary $h$? $\endgroup$ Commented Feb 1, 2014 at 2:05
  • $\begingroup$ Yes, basically is based on the original formula I gave but adding tabling to avoid the expansion of the duplicated tuples $\endgroup$ Commented Feb 1, 2014 at 2:39
  • $\begingroup$ Now you really deserve the best answer! Muchas gracias $\endgroup$ Commented Feb 1, 2014 at 3:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.