

A216368


Number T(n,k) of distinct values taken by kth 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.


10



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, 20, 50, 92, 113, 115, 115, 1, 8, 26, 77, 182, 262, 283, 286, 286, 1, 9, 32, 113, 342, 591, 691, 717, 719, 719, 1, 10, 39, 156, 601, 1263, 1681, 1815, 1838, 1842, 1842
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

T(n,k) <= A000081(n) because there are only A000081(n) different functions that can be represented with n x's.
It is not true that T(n,n) = T(n,n1) for all n>1: T(13,13)  T(13,12) = 12486  12485 = 1.
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).
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:
1
1 1
1 2 2
1 3 4 4
1 4 7 9 9
1 5 11 88 20 20
1 6 16 34 46 48 48
I suspect that Plot 2 will admit a recursive construction more readily than the graphs with collisions. You can already see that each graph "n1" is a subgraph of graph "n" and that the remainder of graph "n" is similar to graph "n1" with additional branches. (End)


LINKS



EXAMPLE

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].
Triangle T(n,k) begins:
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, 20, 50, 92, 113, 115, 115;
...


MAPLE

with(combinat):
F:= proc(n) F(n):=`if`(n<2, [(x+1)$n], map(h>(x+1)^h, g(n1, n1))) end:
g:= proc(n, i) option remember; `if`(n=0 or i=1, [(x+1)^n],
`if`(i<1, [], [seq(seq(seq(mul(F(i)[w[t]t+1], t=1..j)*v,
w=choose([$1..nops(F(i))+j1], j)), v=g(ni*j, i1)), j=0..n/i)]))
end:
T:= proc(n) local i, l;
l:= map(f>[seq(i!*coeff(series(f, x, n+1), x, i), i=1..n)], F(n));
seq(nops({map(x>x[i], l)[]}), i=1..n)
end:
seq(T(n), n=1..10);


MATHEMATICA

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, i1]}], {w, Subsets[ Range[Length[T[i]] + j  1], {j}]}], {j, 0, n/i}]];
T[n_] := T[n] = If[n==1, {x}, x^#& /@ g[n1, n1]];
T[n_, k_] := Union[k! (SeriesCoefficient[#, {x, 0, k}]& /@ (T[n] /. x > x+1))] // Length;


CROSSREFS

Main diagonal gives (conjectured): A000081.


KEYWORD



AUTHOR



STATUS

approved



