Counting formulas

[jemidiah]

Motivating example: consider the eight formulas (a+b)*c, (a+c)*b, (b+c)*a, (a*b)+c, (a*c)+b, (b*c)+a, (a+b)+c, (a*b)*c. Each can produce a different output, eg. as when a=5, b=7, c=2 which gives, respectively, 24, 49, 45, 37, 17, 19, 14, 70. There are no other formulas involving *, +, exactly three inputs a, b, c used once each, and parentheses--at least none that will ever produce a value not produced by the above eight. For instance, (b+a)*c is not on the list, but it's not fundamentally different from (a+b)*c because + is commutative. Similarly (a*c)*b is essentially captured by (a*b)*c.

The question is, given a fixed number n of inputs a_1, ..., a_n; two commutative, associative, binary operators (call them + and *); and parentheses, how many fundamentally different formulas can you construct, using each input precisely once? Formulas are considered equal if no matter what the inputs and operators are they always evaluate to the same thing. For instance, a+(b*c) and (a+b)*c are considered different formulas even though 0+(1*2) = 2 = (0+1)*2 since for other inputs they produce different values. Note that (a+b)*c and (a+c)*b are considered different even though they have the same structure since they produce different values for some choices of a, b, and c.

I may post my own workings at some point, or maybe this will languish forever. I do not yet know the answer.

[Lenggries]

One interesting feature is that, given strictly commutative operators, the variable a will appear at the left most position at least once in ever set of equivalent formulas. Alternatively, given a list of n variables, the n'th could always appear in the same spot. That may provide an anchor, or a root node, so to speak, from which a tree of unique formulas could branch out from.

[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.

[Logophobic]

Hopefully no mistakes.

Unfortunately...


You have 1+6+6+16 = 29 (58)
Here it is 1+6+3+16= 26 (52)

a+b+c+d  : abcd

a+b+cd   : ab(c+d)
a+c+bd   : ac(b+d)
a+d+bc   : ad(b+c)
b+c+ad   : bc(a+d)
b+d+ac   : bd(a+c)
c+d+ab   : cd(a+b)

ab+cd    : (a+b)(c+d)
ac+bd    : (a+c)(b+d)
ad+bc    : (a+d)(b+c)

a+bcd    : a(b+c+d)
b+acd    : b(a+c+d)
c+abd    : c(a+b+d)
d+abc    : d(a+b+c)

a+b(c+d) : a(b+cd)
a+c(b+d) : a(c+bd)
a+d(b+c) : a(d+bc)
b+a(c+d) : b(a+cd)
b+c(a+d) : b(c+ad)
b+d(a+c) : b(d+ac)
c+a(b+d) : c(a+bd)
c+b(a+d) : c(b+ad)
c+d(a+b) : c(d+ab)
d+a(b+c) : d(a+bc)
d+b(a+c) : d(b+ac)
d+c(a+b) : d(c+ab)

[jemidiah]

Ah thank you. I was sloppy. Order matters in step 4 [so one counts both (ab cd) and (cd ab)] while order does not matter in step 5 [so one counts only (ab cd)]. I've edited my calculation to note the necessary changes, which indeed gives S_4 = 26. Ideally S_5 could be computed by hand and compared to the result of my algorithm, but I don't think I have the patience for it myself. I may come back to my algorithm though, optimizing it a little and implementing it....

[Logophobic]

Here's a quick count for S_5: 12 formulae and the number of combinations for each.

a+b+c+d+e    :   1
a+b+c+de     :  10
a+b+c(d+e)   :  30
a+b+cde      :  10
a+bc+de      :  15
ab+c(d+e)    :  30
ab+cde       :  10
a+bc(d+e)    :  30
a+bcde       :   5
a+b(c+d+e)   :  20
a+b(c+de)    :  60
a+(b+c)(d+e) :  15
-------------: 236 (472)

[jemidiah]

This Python script computes S_n for n from 1 to 4 correctly using my algorithm. It was somewhat fun to fiddle with higher order iteration, but the extremely naive method I've used becomes too inefficient for larger values, since it does a very poor job of brute forcing Step 3. I had hoped to use it to compute the next few terms, though I'll need to modify that section to make it complete in a reasonable amount of time. Without doing that at the moment, using Logophobic's number for S_5, we seem to have found this sequence with several combinatorial interpretations. That page lists several formulas for computing this series, including...

S_1=1
S_n = -(n-1) * S_(n-1) + Sum_{k=1..n-1} binomial(n, k) * S_k * S_(n-k)

In any case, this allows us to easily compute (what almost certainly is) our sequence. The original context of this problem was to compare the number of unique formulas of the above type (including subtraction, actually) to n!. Computing the n=2 to 20 terms, the ratio of 2*S_n to n! is (rounded to two significant figures):
1.0, 1.3, 2.2, 3.9, 7.6, 45, 16, 33, 71, 160, 350, 790, 1800, 4200, 9700, 23000, 54000, 130000, 300000, 730000

Obviously the number of formulas greatly exceeds n! for large n; the original question involving even more general formulas is certainly hopeless without a better accounting of equivalences in the particular modular arithmetic case in question. Incidentally, the ratio of these fractions is relatively constant and seems to stabilize under 3, likely to a constant that I cannot identify. In any case this thread's question has been answered to my satisfaction and the potential proof technique that started this one has been basically disproved, so I'm satisfied. My thirst for combinatorial explorations is also temporarily satisified.

Thanks Logo! You should be "Logophilic".