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$ – leonbloy Jan 31 '14 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$ – user125237 Jan 31 '14 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$ – leonbloy Jan 31 '14 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$ – user125237 Jan 31 '14 at 17:11
  • $\begingroup$ For $h=5$ I get 135... $\endgroup$ – leonbloy Jan 31 '14 at 17:23
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$ – leonbloy Jan 31 '14 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$ – user125237 Feb 1 '14 at 1:47
  • $\begingroup$ You're welcome. You have an afficient algorithm for arbitrary $h$? $\endgroup$ – leonbloy Feb 1 '14 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$ – user125237 Feb 1 '14 at 2:39
  • $\begingroup$ Now you really deserve the best answer! Muchas gracias $\endgroup$ – user125237 Feb 1 '14 at 3:18

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.