login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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,n-1) 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).

From Bradley Klee, Jun 01 2015 (Start):

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 "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)

LINKS

Alois P. Heinz, Rows n = 1..16, flattened

Bradley Klee, Plot 1

Bradley Klee, Plot 2

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(n-1, n-1))) 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))+j-1], j)), v=g(n-i*j, i-1)), 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);

CROSSREFS

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

Main diagonal gives (conjectured): A000081.

Cf. A000108, A215703.

Sequence in context: A066201 A303273 A193820 * A123956 A331953 A113594

Adjacent sequences:  A216365 A216366 A216367 * A216369 A216370 A216371

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Sep 05 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 23 22:23 EDT 2020. Contains 337315 sequences. (Running on oeis4.)