Counting formulas

[jemidiah]

I don't think that's terribly helpful since "leftmost" and "root" are distinct. [Even rotating a tree and "hanging" it from the leftmost node is strange in this case because after rotation the tree has a different structure, i.e. it is not always a full binary tree.] A recursive count seems to be in order, though it's complicated by associativity.

Given a formula F, we can turn the binary parse tree into higher-ary parse tree to reflect the associativity of *; for instance, (a*b)*(c+d) corresponds to a*b*(c+d), which is itself a tree where the root has three branches, to a, to b, and to the subtree given by c+d. So, F can be written as F_1 * F_2 * ... * F_k where each F_i is either a singleton or has root operation +. The length k of the product is clearly unique. From commutativity the order of the F_i does not matter. Suppose S_m denotes the number of (different) formulas of the type we're interested in with m terms and + as root operation, where S_1 = 1 by definition. Actually, let's denote the formulas that S_m counts by S^m. To create a length n formula F, we can pick formulas from the sets S^m for m between 1 and n-1 [n-1 instead of n since I'll assume F has * as root operation] until the sum of their lengths is n. Note that we can pick the same formula multiple times and order is irrelevant.

One can say we must pick quantities for each of the formulas in all the S^m's, such that the sum of their lengths is n. Now we must match up variables to formulas. Order is accounted for by the S^m [eg. using m=3, a+b+c = a+c+b; a+(b*c) != b+(a*c)]. Suppose we had picked formulas F_i with multiplicity m_i >= 1 and lengths n_i. First we must divide up the variables a_1, ..., a_n into groups of size m_i * n_i; even if two groups have the same size, order matters, at least at the inter-group level--for instance, grouping (a_1, a_2) (a_3, a_4) is considered distinct from grouping (a_3, a_4) (a_1, a_2), whereas (a_2, a_1) (a_3, a_4) is the same as the first of these groupings. For the ith group, we then must divide it up into m_i groups of size n_i; here inter-group ordering does not matter--for instance, grouping (a_1, a_2) (a_3, a_4) is considered the same as grouping (a_3, a_4) (a_1, a_2). "groups" here are order-agnostic. The number of ways to perform these actions is simply S_n, since we can swap * and + everywhere. The number of formulas we're interested in is 1 for n=1, and 2*S_n for n >= 2.

In summary, the naive algorithm for computing S_n is...
1. Compute S_m for m=1 to n-1. Note that S_1 = 1.
2. Initialize variables m_i,j for i from 1 to n-1, j from 1 to S_i.
3. Loop over all choices of m_i,j that satisfy the constraint sum_i,j m_i,j * i = n.
4. Compute the number of ways to divide up n into groups of size m_i,j * i, where inter-group ordering matters.
5. For each (i,j), compute the number of ways to divide up m_i,j * i into groups of size i, where inter-group order does not matter.
6. Multiply (4) and (5) and add those products over all choices from (3); this is S_n.

Running this algorithm for n=2 gives...
1. S_1 = 1.
2. m_1,1 = 0.
3. 2 * 1 = 2 is the only solution, so m_1,1 = 2.
4. 2 can be divided up into groups of size 2 in precisely 1 way.
5. 2 can be divided up into groups of size 1 in precisely 1 way.
6. 1*1 = 1 = S_2.

Running this algorithm for n=3 gives...
1. S_1 = 1, S_2 = 1.
2. m_1,1 = 0; m_2,1 = 0.
3. m_1,1 * 1 + m_2,1 * 2 = 3 is the constraint. It has solutions for (m_1,1, m_2,1) = (3, 0), (1, 1).
4.1. 3 can be divided up into groups of size 3 in precisely 1 way.
5.1. 3 can be divided up into groups of size 1 in precisely 1 way.
4.2. 3 can be divided up into groups of size 1,2 in precisely 3 ways. [(a bc) (ab c) (ac b)]
5.2.1. 1 can be divided up into groups of size 1 in precisely 1 way.
5.2.2. 2 can be divided up into groups of size 2 in precisely 1 way.
6. 1*1 + 3*1*1 = 4 = S_3.

Running this algorithms for n=4 gives...
1. S_1 = 1, S_2 = 1, S_3 = 4.
2. m_1,1 = 0; m_2,1 = 0; m_3,1 = 0; m_3,2 = 0; m_3,3 = 0; m_3,4 = 0.
3. m_1,1 * 1 + m_2,1 * 2 + m_3,1 * 3 + m_3,2 * 3 + m_3,3 * 3 + m_3,4 * 3 = 4 is the constraint. It has solutions for
(m_1,1, m_2,1, m_3,1, m_3,2, m_3,3, m_3,4) = (4, 0, 0, 0, 0, 0), (2, 1, 0, 0, 0, 0), (0, 2, 0, 0, 0, 0), (1, 0, 1, 0, 0, 0), (1, 0, 0, 1, 0, 0), (1, 0, 0, 0, 1, 0), (1, 0, 0, 0, 0, 1).
4.1. 4 can be divided up into groups of size 4 in precisely 1 way.
5.1. 4 can be divided up into groups of size 1 in precisely 1 way.
4.2. 4 can be divided up into groups of size 2,2 in precisely 6 ways. [(ab cd) (ac bd) (ad bc) (bc ad) (bd ac) (cd ab)]
5.2.1. 2 can be divided up into groups of size 1 in precisely 1 way.
5.2.2. 2 can be divided up into groups of size 2 in precisely 1 way.
4.3. 4 can be divided up into groups of size 4 in precisely 1 way.
5.3. 4 can be divided up into groups of size 2 in precisely 3 ways, not as above since inter-group ordering does not matter.
4.4. 4 can be divided up into groups of size 1,3 in precisely 4 ways. [(abc d) (abd c) (acd b) (bcd a)]
5.4.1. 1 can be divided up into groups of size 1 in precisely 1 way.
5.4.2. 3 can be divided up into groups of size 3 in precisely 1 way.
[Repeat the last three lines 3 more times.]
6. 1*1 + 6*1*1 + 1*3 + 4*(4*1*1) = 26 = S_4. Hopefully no mistakes.

Note that S_3 = 4 implies 8 formulas with 3 terms, as I enumerated in my original example. If I remember correctly, steps 4 and 5 can be solved using the multinomial coefficients. Step 3 is difficult though. I may write a program to solve the first few S_n's by brute force, which hopefully will lead to the correct sequence in OEIS. I imagine some combinatorialist has studied this problem or an equivalent one in detail.


Edits in italics.