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
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

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.

LINKS

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

EXAMPLE

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.

PROG

(Python)

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

CROSSREFS

Cf. A001003

Sequence in context: A257290 A281482 A132889 * A149061 A149062 A066979

Adjacent sequences:  A245387 A245388 A245389 * A245391 A245392 A245393

KEYWORD

nonn

AUTHOR

Ben Burns, Jul 22 2014

STATUS

approved

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 July 8 20:50 EDT 2020. Contains 335535 sequences. (Running on oeis4.)