cp's OEIS Frontend

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.

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