|
%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
|
