A245390 Number of ways to build an expression using non-redundant parentheses in an expression of n variables, counted in decreasing sub-partitions of equal size.

1, 1, 3, 11, 39, 145, 514, 1901, 6741, 24880, 87791, 325634, 1152725, 4251234, 15052387, 55750323, 197031808, 729360141, 2579285955, 9539017676, 33822222227, 124889799518, 440743675148, 1635528366655, 5790967247863, 21360573026444, 75643815954959, 280096917425535

Offset: 1

Author

Ben Burns, Jul 22 2014

Keywords

• nonn

Comments

Expressions contain only binary operators. Parentheses around a single variable or the entire expression are considered redundant or unnecessary.

If the number of partitions (parenthetical group) does not evenly divide the number of variables, combinations of remaining variables are counted but not divided into sub-partitions.

Examples

			For n=3, the a(3)=3 different possibilities are
1)  x+x+x,
2)  (x+x)+x,
3)  x+(x+x).
For n=4, the a(4)=11 different possibilities are
1)  x+x+x+x,
2)  (x+x+x)+x,
3)  ((x+x)+x)+x,
4)  (x+(x+x))+x,
5)  x+(x+x+x),
6)  x+((x+x)+x),
7)  x+(x+(x+x)),
8)  (x+x)+x+x,
9)  x+(x+x)+x,
10) x+x+(x+x),
11) (x+x)+(x+x).
For n=5, a(5)=39 is the first time this sequence differs from A001003. The combinations for (x+x+x)+(x+x) and (x+x)+(x+x+x) are not counted as these two partitions are not of equal size.
		

Links

• Ben Burns, Table of n, a(n) for n = 1..98

Crossrefs

Cf. A001003

Programs

Python

from functools import reduce
import math
import operator as op
def binom(n, r):
    r = min(r, n-r)
    if r == 0: return 1
    numer = reduce(op.mul, range(n, n-r, -1))
    denom = reduce(op.mul, range(1, r+1))
    return numer//denom
max = 100
seq = [0,1,1]
for n in range(3, max) :
    sum = 0
    for choose in range(2, n+1):
        f = math.ceil(n/choose)
        f+=1
        for times in range(1, int(f)) :
            if choose*times > n :
                continue
            if choose==n and times==1 :
                sum += 1
            else :
                sum += binom(n - (choose*times) + times, times) * (seq[choose]**times)
    seq.append(sum)
for (i, x) in enumerate(seq) :
    if i==0:
        continue
    print(i, x)