|
%I #30 Dec 07 2019 12:33:53
%S 1,1,3,11,39,145,514,1901,6741,24880,87791,325634,1152725,4251234,
%T 15052387,55750323,197031808,729360141,2579285955,9539017676,
%U 33822222227,124889799518,440743675148,1635528366655,5790967247863,21360573026444,75643815954959,280096917425535
%N 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.
%C Expressions contain only binary operators. Parentheses around a single variable or the entire expression are considered redundant or unnecessary.
%C 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.
%H Ben Burns, <a href="/A245390/b245390.txt">Table of n, a(n) for n = 1..98</a>
%e For n=3, the a(3)=3 different possibilities are
%e 1) x+x+x,
%e 2) (x+x)+x,
%e 3) x+(x+x).
%e For n=4, the a(4)=11 different possibilities are
%e 1) x+x+x+x,
%e 2) (x+x+x)+x,
%e 3) ((x+x)+x)+x,
%e 4) (x+(x+x))+x,
%e 5) x+(x+x+x),
%e 6) x+((x+x)+x),
%e 7) x+(x+(x+x)),
%e 8) (x+x)+x+x,
%e 9) x+(x+x)+x,
%e 10) x+x+(x+x),
%e 11) (x+x)+(x+x).
%e 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.
%o (Python)
%o import math
%o import operator as op
%o def binom(n, r):
%o ....r = min(r, n-r)
%o ....if r == 0: return 1
%o ....numer = reduce(op.mul, range(n, n-r, -1))
%o ....denom = reduce(op.mul, range(1, r+1))
%o ....return numer//denom
%o max = 100
%o seq = [0,1,1]
%o for n in range(3, max) :
%o ....sum = 0
%o ....for choose in range(2, n+1):
%o ........f = math.ceil(n/choose)
%o ........f+=1
%o ........for times in range(1, int(f)) :
%o ............if choose*times > n :
%o ................continue
%o ............if choose==n and times==1 :
%o ................sum += 1
%o ............else :
%o ................sum += binom(n - (choose*times) + times, times) * (seq[choose]**times)
%o ....seq.append(sum)
%o for (i, x) in enumerate(seq) :
%o ....if i==0:
%o ........continue
%o ....print i, x
%Y Cf. A001003
%K nonn
%O 1,3
%A _Ben Burns_, Jul 22 2014
|
