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

%I #41 Nov 05 2024 18:56:39

%S 1,2,4,8,15,28,51,92,164,286,486,808,1322,2142,3456,5571,8975,14427,

%T 23094,36766,58201,91675,143841,225045,351321,547393,851160,1320339,

%U 2042195,3147614,4831237,7380048,11213838,16942556,25447992,38000880

%N Number 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 a(n) is also the number of different possible products of nesting levels in n pairs of parentheses.

%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, there are only 15 different values.

%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 [len(set(j[0] for j in i)) for i in k]

%K nonn

%O 1,2

%A _Jack Zhang_, Sep 10 2020

%E a(31)-a(32) from _David A. Corneth_, Sep 12 2020

%E a(33)-a(36) from _Bert Dobbelaere_, Oct 19 2020