A307900 Number of functions constructed from n instances of variable x using operators + (add), * (multiply), and parentheses.

1, 2, 4, 10, 24, 61, 150, 382, 964, 2452, 6307, 16379, 42989, 113965, 305035, 823632, 2241814, 6145670, 16956972, 47059076, 131279567

Offset

1,2

Comments

Structurally different expressions that represent the same function of x are only counted once. So, a(n) <= A052701(n).

Links

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

Example

For n = 1, we have only one function {x}, so a(1) = 1.
For n = 2, we have {x*x, x + x} = {x^2, 2*x}, so a(2) = 2.
For n = 3, we have {x^2*x, 2*x*x, x^2 + x, 2*x + x} = {x^3, 2*x^2, x^2 + x, 3*x}, so a(3) = 4.
For n = 4, we have {x^4, 2*x^3, x^3 + x^2, x^3 + x, 4*x^2, 3*x^2, 2*x^2 + x, 2*x^2, x^2 + 2*x, 4*x}, so a(4) = 10.

Maple

b:= proc(n) option remember; `if`(n=1, {x}, {seq(seq(seq([f+g,
        expand(f*g)][], g=b(n-i)), f=b(i)), i=1..iquo(n, 2))})
    end:
a:= n-> nops(b(n)):
seq(a(n), n=1..12);  # Alois P. Heinz, May 04 2019

Mathematica

ClearAll[a, f, x, n, k]; f[1] = {x}; f[n_Integer] := f[n] = DeleteDuplicates[Expand[Flatten[Table[Outer[#1[#2, #3] &, {Times, Plus}, f[k], f[n - k]], {k, n/2}]]]]; a[n_Integer] := Length[f[n]]; Table[a[n], {n, 15}]

Crossrefs

Cf. A048249, A052701.

Sequence in context: A329673 A055919 A006575 * A230551 A246566 A230553

Adjacent sequences: A307897 A307898 A307899 * A307901 A307902 A307903

Keyword

nonn,more

Author

Vladimir Reshetnikov, May 04 2019

Extensions

a(19)-a(20) from Alois P. Heinz, May 04 2019

a(21) from Vladimir Reshetnikov, May 05 2019

Status

approved