%I #37 Feb 08 2021 17:41:01

%S 1,1,1,1,2,2,1,3,4,4,1,4,7,9,9,1,5,11,17,20,20,1,6,15,30,45,48,48,1,7,

%T 20,50,92,113,115,115,1,8,26,77,182,262,283,286,286,1,9,32,113,342,

%U 591,691,717,719,719,1,10,39,156,601,1263,1681,1815,1838,1842,1842

%N Number T(n,k) of distinct values taken by k-th derivative of x^x^...^x (with n x's and parentheses inserted in all possible ways) at x=1; triangle T(n,k), n>=1, 1<=k<=n, read by rows.

%C T(n,k) <= A000081(n) because there are only A000081(n) different functions that can be represented with n x's.

%C It is not true that T(n,n) = T(n,n-1) for all n>1: T(13,13) - T(13,12) = 12486 - 12485 = 1.

%C Conjecture: T(n,n) = A000081(n) for n>=1. It would be nice to have a proof (or a disproof if the conjecture is wrong).

%C From _Bradley Klee_, Jun 01 2015 (Start):

%C I made a descendant graph (Plot 1) that shows how each derivative relates to the next. In this picture the number of nodes in row k gives the value T(n,k). You can see at n=6 collisions begin to occur, and at n=7 the situation is even worse. I then computed a new triangle with collisions removed (Plot 2) and values:

%C 1

%C 1 1

%C 1 2 2

%C 1 3 4 4

%C 1 4 7 9 9

%C 1 5 11 88 20 20

%C 1 6 16 34 46 48 48

%C I suspect that Plot 2 will admit a recursive construction more readily than the graphs with collisions. You can already see that each graph "n-1" is a subgraph of graph "n" and that the remainder of graph "n" is similar to graph "n-1" with additional branches. (End)

%H Alois P. Heinz, <a href="/A216368/b216368.txt">Rows n = 1..16, flattened</a>

%H Bradley Klee, <a href="/A216368/a216368.png">Plot 1</a>

%H Bradley Klee, <a href="/A216368/a216368_1.png">Plot 2</a>

%e For n = 4 there are A000108(3) = 5 possible parenthesizations of x^x^x^x: [x^(x^(x^x)), x^((x^x)^x), (x^(x^x))^x, (x^x)^(x^x), ((x^x)^x)^x]. The first, second, third, fourth derivatives at x=1 are [1,1,1,1,1], [2,2,4,4,6], [9,15,18,18,27], [56,80,100,100,156] => row 4 = [1,3,4,4].

%e Triangle T(n,k) begins:

%e 1;

%e 1, 1;

%e 1, 2, 2;

%e 1, 3, 4, 4;

%e 1, 4, 7, 9, 9;

%e 1, 5, 11, 17, 20, 20;

%e 1, 6, 15, 30, 45, 48, 48;

%e 1, 7, 20, 50, 92, 113, 115, 115;

%e ...

%p with(combinat):

%p F:= proc(n) F(n):=`if`(n<2, [(x+1)$n], map(h->(x+1)^h, g(n-1, n-1))) end:

%p g:= proc(n, i) option remember; `if`(n=0 or i=1, [(x+1)^n],

%p `if`(i<1, [], [seq(seq(seq(mul(F(i)[w[t]-t+1], t=1..j)*v,

%p w=choose([$1..nops(F(i))+j-1], j)), v=g(n-i*j, i-1)), j=0..n/i)]))

%p end:

%p T:= proc(n) local i, l;

%p l:= map(f->[seq(i!*coeff(series(f, x, n+1), x, i), i=1..n)], F(n));

%p seq(nops({map(x->x[i], l)[]}), i=1..n)

%p end:

%p seq(T(n), n=1..10);

%t g[n_, i_] := g[n, i] = If[i==1, {x^n}, Flatten@Table[Table[Table[Product[ T[i][[w[[t]] - t+1]], {t, 1, j}]*v, {v, g[n - i*j, i-1]}], {w, Subsets[ Range[Length[T[i]] + j - 1], {j}]}], {j, 0, n/i}]];

%t T[n_] := T[n] = If[n==1, {x}, x^#& /@ g[n-1, n-1]];

%t T[n_, k_] := Union[k! (SeriesCoefficient[#, {x, 0, k}]& /@ (T[n] /. x -> x+1))] // Length;

%t Table[T[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Feb 08 2021, after _Alois P. Heinz_ *)

%Y Columns k=1-10 give: A000012, A028310, A199085, A199205, A199296, A199883, A215796, A215971, A216062, A216403.

%Y Main diagonal gives (conjectured): A000081.

%Y Cf. A000108, A215703.

%K nonn,tabl

%O 1,5

%A _Alois P. Heinz_, Sep 05 2012