login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

%I

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 4 08:25 EDT 2020. Contains 336201 sequences. (Running on oeis4.)