A334637 Sum of different values of x_1*x_2*...*x_n where x_1=1 and x_i-x_{i-1} is 0 or 1.

1, 3, 13, 75, 517, 4443, 43093, 486315, 6082117, 81407163, 1184034613, 19251200715, 342825926437, 6604284459483, 136398242877973, 2984396941441515, 68215762130020357, 1627134074774283003, 40749275946991321333, 1079215210446044648715, 30311064871950344936677, 897713839789350372765723

Offset: 1

Author

Jack Zhang, Sep 10 2020

Keywords

• nonn

Comments

Equals to: sum of different possible product of nesting levels in n pairs of parentheses.

For example, there are A000108(3)=5 ways to insert 3 pair of parentheses: ()()(), (())(), ()(()), (()()), ((())), the product of nesting levels are 1, 2, 2, 4, 6, and A001147(3)=1+2+2+4+6=15, but a(3)=1+2+4+6=13.

Examples

			n=5: possible values are 1*1*1*1*1, 1*1*1*1*2, 1*1*1*2*2, 1*1*1*2*3, 1*1*2*2*2, 1*1*2*2*3, 1*1*2*3*3, 1*1*2*3*4, 1*2*2*2*2, 1*2*2*2*3, 1*2*2*3*3, 1*2*2*3*4, 1*2*3*3*3, 1*2*3*3*4, 1*2*3*4*4, 1*2*3*4*5, but since 1*1*2*3*4=1*2*2*2*3, the sum of other values is A000670(5)-1*1*2*3*4=517.
		

Links

• Using your Head is Permitted, Parenthesis Values, November 2013 riddle.

Crossrefs

Cf. A334635 (number of different values), A000670 (sum if the values are not deduplicated), A001147 (sum of products of nesting levels in n pairs of parentheses if not deduplicated).

Programs

Python

k=[{(1, 1)}]
for i in range(20):
    k.append(set([(i[0]*i[1], i[1]) for i in k[-1]])|set([(i[0]*(i[1]+1), i[1]+1) for i in k[-1]]))
[sum(set(j[0] for j in i)) for i in k]