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,2

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.

Links

Table of n, a(n) for n=1..22.

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

Example

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.

Prog

(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]

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).

Sequence in context: A074517 A251658 A330047 * A007178 A173990 A276924

Adjacent sequences: A334634 A334635 A334636 * A334638 A334639 A334640

Keyword

nonn

Author

Jack Zhang, Sep 10 2020

Status

approved