A199205 Number of distinct values taken by 4th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1.

1, 1, 2, 4, 9, 17, 30, 50, 77, 113, 156, 212, 279, 355, 447, 560, 684, 822, 985, 1171, 1375, 1599, 1856, 2134, 2445, 2769, 3125, 3519, 3939, 4376, 4857, 5372, 5914, 6484, 7083, 7717, 8411, 9130, 9882, 10683, 11524, 12393

Offset: 1

Author

Alois P. Heinz, Nov 03 2011

Keywords

• nonn

Examples

			a(5) = 9 because the A000108(4) = 14 possible parenthesizations of x^x^x^x^x lead to 9 different values of the 4th derivative at x=1: (x^(x^(x^(x^x)))) -> 56; (x^(x^((x^x)^x))) -> 80; (x^((x^(x^x))^x)), (x^((x^x)^(x^x))) -> 104; ((x^x)^(x^(x^x))), ((x^(x^(x^x)))^x) -> 124; ((x^(x^x))^(x^x)) -> 148; (x^(((x^x)^x)^x)) -> 152; ((x^x)^((x^x)^x)), ((x^((x^x)^x))^x) -> 172; (((x^x)^x)^(x^x)), (((x^(x^x))^x)^x), (((x^x)^(x^x))^x) -> 228; ((((x^x)^x)^x)^x) -> 344.
		

Crossrefs

Cf. A000081 (distinct functions), A000108 (parenthesizations), A000012 (first derivatives), A028310 (2nd derivatives), A199085 (3rd derivatives), A199296 (5th derivatives), A002845, A003018, A003019, A145545, A145546, A145547, A145548, A145549, A145550, A082499, A196244, A198683, A215703, A215834. Column k=4 of A216368.

Programs

Maple

f:= proc(n) option remember;
      `if`(n=1, {[0, 0, 0]},
                {seq(seq(seq( [2+g[1], 3*(1 +g[1] +h[1]) +g[2],
                 8 +12*g[1] +6*h[1]*(1+g[1]) +4*(g[2]+h[2])+g[3]],
                 h=f(n-j)), g=f(j)), j=1..n-1)})
    end:
a:= n-> nops(map(x-> x[3], f(n))):
seq(a(n), n=1..20);

Mathematica

f[n_] := f[n] = If[n == 1, {{0, 0, 0}}, Union @ Flatten[#, 3]& @ {Table[ Table[Table[{2 + g[[1]], 3*(1 + g[[1]] + h[[1]]) + g[[2]], 8 + 12*g[[1]] + 6*h[[1]]*(1 + g[[1]]) + 4*(g[[2]] + h[[2]]) + g[[3]]}, {h, f[n - j]}], {g, f[j]}], {j, 1, n - 1}]}];
a[n_] := Length @ Union @ (#[[3]]& /@ f[n]);
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 32}] (* Jean-François Alcover, Jun 08 2018, after Alois P. Heinz *)

Extensions

a(41)-a(42) from Alois P. Heinz, Jun 01 2015