cp's OEIS Frontend

A216368 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.

%I A216368 #37 Feb 08 2021 17:41:01
%S A216368 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 A216368 20,50,92,113,115,115,1,8,26,77,182,262,283,286,286,1,9,32,113,342,
%U A216368 591,691,717,719,719,1,10,39,156,601,1263,1681,1815,1838,1842,1842
%N A216368 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 A216368 T(n,k) <= A000081(n) because there are only A000081(n) different functions that can be represented with n x's.
%C A216368 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 A216368 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 A216368 From _Bradley Klee_, Jun 01 2015 (Start):
%C A216368 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 A216368     1
%C A216368     1 1
%C A216368     1 2  2
%C A216368     1 3  4  4
%C A216368     1 4  7  9  9
%C A216368     1 5 11 88 20 20
%C A216368     1 6 16 34 46 48 48
%C A216368 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 A216368 Alois P. Heinz, <a href="/A216368/b216368.txt">Rows n = 1..16, flattened</a>
%H A216368 Bradley Klee, <a href="/A216368/a216368.png">Plot 1</a>
%H A216368 Bradley Klee, <a href="/A216368/a216368_1.png">Plot 2</a>
%e A216368 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 A216368 Triangle T(n,k) begins:
%e A216368   1;
%e A216368   1, 1;
%e A216368   1, 2,  2;
%e A216368   1, 3,  4,  4;
%e A216368   1, 4,  7,  9,  9;
%e A216368   1, 5, 11, 17, 20,  20;
%e A216368   1, 6, 15, 30, 45,  48,  48;
%e A216368   1, 7, 20, 50, 92, 113, 115, 115;
%e A216368   ...
%p A216368 with(combinat):
%p A216368 F:= proc(n) F(n):=`if`(n<2, [(x+1)$n], map(h->(x+1)^h, g(n-1, n-1))) end:
%p A216368 g:= proc(n, i) option remember; `if`(n=0 or i=1, [(x+1)^n],
%p A216368      `if`(i<1, [], [seq(seq(seq(mul(F(i)[w[t]-t+1], t=1..j)*v,
%p A216368       w=choose([$1..nops(F(i))+j-1], j)), v=g(n-i*j, i-1)), j=0..n/i)]))
%p A216368     end:
%p A216368 T:= proc(n) local i, l;
%p A216368       l:= map(f->[seq(i!*coeff(series(f, x, n+1), x, i), i=1..n)], F(n));
%p A216368       seq(nops({map(x->x[i], l)[]}), i=1..n)
%p A216368     end:
%p A216368 seq(T(n), n=1..10);
%t A216368 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 A216368 T[n_] := T[n] = If[n==1, {x}, x^#& /@ g[n-1, n-1]];
%t A216368 T[n_, k_] := Union[k! (SeriesCoefficient[#, {x, 0, k}]& /@ (T[n] /. x -> x+1))] // Length;
%t A216368 Table[T[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Feb 08 2021, after _Alois P. Heinz_ *)
%Y A216368 Columns k=1-10 give: A000012, A028310, A199085, A199205, A199296, A199883, A215796, A215971, A216062, A216403.
%Y A216368 Main diagonal gives (conjectured): A000081.
%Y A216368 Cf. A000108, A215703.
%K A216368 nonn,tabl
%O A216368 1,5
%A A216368 _Alois P. Heinz_, Sep 05 2012