login
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.
0

%I #41 Nov 05 2024 18:57:06

%S 1,3,13,75,517,4443,43093,486315,6082117,81407163,1184034613,

%T 19251200715,342825926437,6604284459483,136398242877973,

%U 2984396941441515,68215762130020357,1627134074774283003,40749275946991321333,1079215210446044648715,30311064871950344936677,897713839789350372765723

%N 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.

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

%C 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.

%H Using your Head is Permitted, <a href="https://www.brand.site.co.il/riddles/201311q.html">Parenthesis Values</a>, November 2013 riddle.

%e 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.

%o (Python)

%o k=[{(1, 1)}]

%o for i in range(20):

%o 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]]))

%o [sum(set(j[0] for j in i)) for i in k]

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

%K nonn

%O 1,2

%A _Jack Zhang_, Sep 10 2020