Count recursive groupings of elements in pairs

Question

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)$?

Answer 1

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